F2. Anti-median (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The only difference between the two versions is the constraint on $$$n$$$. You can make hacks only if all versions of the problem are solved.

Let's call an array $$$a$$$ of odd length $$$2m+1$$$ (with $$$m \ge 1$$$) bad, if element $$$a_{m+1}$$$ is equal to the median of this array. In other words, the array is bad if, after sorting it, the element at $$$m+1$$$-st position remains the same.

Let's call a permutation $$$p$$$ of integers from $$$1$$$ to $$$n$$$ anti-median, if every its subarray of odd length $$$\ge 3$$$ 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 $$$10^9+7$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$)  — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(2 \le n \le 10^6)$$$  — the length of the permutation.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, or $$$p_i = -1$$$)  — the elements of the permutation. If $$$p_i \neq -1$$$, it's given, else it's unknown. It's guaranteed that if for some $$$i \neq j$$$ holds $$$p_i \neq -1, p_j \neq -1$$$, then $$$p_i \neq p_j$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output a single integer  — the number of ways to set unknown values to obtain an anti-median permutation, modulo $$$10^9+7$$$.

Example
Input
5
2
-1 -1
3
-1 -1 -1
4
1 2 3 4
6
-1 -1 3 4 -1 -1
8
-1 -1 -1 -1 -1 -1 -1 -1
Output
2
4
0
1
316
Note

In the first test case, both $$$[1, 2]$$$ and $$$[2, 1]$$$ are anti-median.

In the second test case, permutations $$$[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]$$$ are anti-median. The remaining two permutations, $$$[1, 2, 3]$$$, $$$[3, 2, 1]$$$, are bad arrays on their own, as their median, $$$2$$$, is in their middle.

In the third test case, $$$[1, 2, 3, 4]$$$ isn't anti-median, as it contains bad subarray $$$[1, 2, 3]$$$.

In the fourth test case, the only anti-median array you can get is $$$[5, 6, 3, 4, 1, 2]$$$.