#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 nn. You can make hacks only if all versions of the problem are solved.

Let's call an array aa of odd length 2m+12m+1 (with m1m \ge 1) bad, if element am+1a_{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+1m+1-st position remains the same.

Let's call a permutation pp of integers from 11 to nn anti-median, if every its subarray of odd length 3\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 109+710^9+7.

The first line contains a single integer tt (1t1041 \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 nn (2n106)(2 \le n \le 10^6)  — the length of the permutation.

The second line of each test case contains nn integers p1,p2,,pnp_1, p_2, \ldots, p_n (1pin1 \le p_i \le n, or pi=1p_i = -1)  — the elements of the permutation. If pi1p_i \neq -1, it's given, else it's unknown. It's guaranteed that if for some iji \neq j holds pi1,pj1p_i \neq -1, p_j \neq -1, then pipjp_i \neq p_j.

It is guaranteed that the sum of nn over all test cases does not exceed 10610^6.

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

Input

The first line contains a single integer tt (1t1041 \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 nn (2n106)(2 \le n \le 10^6)  — the length of the permutation.

The second line of each test case contains nn integers p1,p2,,pnp_1, p_2, \ldots, p_n (1pin1 \le p_i \le n, or pi=1p_i = -1)  — the elements of the permutation. If pi1p_i \neq -1, it's given, else it's unknown. It's guaranteed that if for some iji \neq j holds pi1,pj1p_i \neq -1, p_j \neq -1, then pipjp_i \neq p_j.

It is guaranteed that the sum of nn over all test cases does not exceed 10610^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 109+710^9+7.

样例输入 1

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

样例输出 1

2
4
0
1
316

Note

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

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

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

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