A15502 | Anti-median (Hard Version)

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

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

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