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$$$.

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]$$$.

Anti-median (Hard Version)

Examples