#P1761F2. Anti-median (Hard Version)
Anti-median (Hard Version)
Description
This is the hard version of the problem. The only difference between the two versions is the constraint on . You can make hacks only if all versions of the problem are solved.
Let's call an array of odd length (with ) bad, if element is equal to the median of this array. In other words, the array is bad if, after sorting it, the element at -st position remains the same.
Let's call a permutation of integers from to anti-median, if every its subarray of odd length is not bad.
You are already given values of some elements of the permutation. Find the number of ways to set unknown values to obtain an anti-median permutation. As this number can be very large, find it modulo .
The first line contains a single integer () — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer — the length of the permutation.
The second line of each test case contains integers (, or ) — the elements of the permutation. If , it's given, else it's unknown. It's guaranteed that if for some holds , then .
It is guaranteed that the sum of over all test cases does not exceed .
For each test case, output a single integer — the number of ways to set unknown values to obtain an anti-median permutation, modulo .
Input
The first line contains a single integer () — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer — the length of the permutation.
The second line of each test case contains integers (, or ) — the elements of the permutation. If , it's given, else it's unknown. It's guaranteed that if for some holds , then .
It is guaranteed that the sum of over all test cases does not exceed .
Output
For each test case, output a single integer — the number of ways to set unknown values to obtain an anti-median permutation, modulo .
Note
In the first test case, both and are anti-median.
In the second test case, permutations are anti-median. The remaining two permutations, , , are bad arrays on their own, as their median, , is in their middle.
In the third test case, isn't anti-median, as it contains bad subarray .
In the fourth test case, the only anti-median array you can get is .