B"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 <= t <= 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 <= n <= 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 <= p_i <= 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 . 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"...