这是问题的困难版本。两个版本之间的唯一区别是对 $$$n$$$ 的约束。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。
如果元素 $$$a_{m+1}$$$ 等于该数组的中位数,我们称奇数长度 $$$2m+1$$$($$$m \ge 1$$$)的数组 $$$a$$$ 为坏数组。换句话说,如果在排序后,$$$m+1$$$-st 位置的元素保持不变,则该数组是坏的。
如果每个奇数长度 $$$\ge 3$$$ 的子数组都不错,那么我们称从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$p$$$ 为反中位数。
您已经获得了排列中某些元素的值。找出设置未知值以获得反中值排列的方法数。由于这个数字可能非常大,请对 $$$10^9+7$$$ 求模。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ $$$(2 \le n \le 10^6)$$$ — 排列的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, 或 $$$p_i = -1$$$) — 排列的元素。如果 $$$p_i \neq -1$$$ 则给出,否则未知。保证如果对于某些 $$$i \neq j$$$ 持有 $$$p_i \neq -1, p_j \neq -1$$$,则 $$$p_i \neq p_j$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。
输出
对于每个测试用例,输出一个整数 - 设置未知值以获得反中值排列的方法数量,以 $$$10^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
注意
在第一个测试用例中,$$$[1, 2]$$$ 和 $$$[2, 1]$$$ 都是反中值。
在第二个测试用例中,排列 $$$[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]$$$ 是反中值。其余两个排列 $$$[1, 2, 3]$$$、$$$[3, 2, 1]$$$ 本身就是坏数组,因为它们的中位数 $$$2$$$ 位于它们的中间。
在第三个测试用例中,$$$[1, 2, 3, 4]$$$ 不是反中位数,因为它包含错误的子数组 $$$[1, 2, 3]$$$。
在第四个测试用例中,您可以获得的唯一反中值数组是 $$$[5, 6, 3, 4, 1, 2]$$$。