F2. Анти-медианный (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное различие между двумя версиями  — ограничение на $$$n$$$. Вы можете делать взломы, только если все версии задачи решены.

Назовем массив $$$a$$$ нечетной длины $$$2m+1$$$ (при $$$m \ge 1$$$) плохим, если элемент $$$a_{m+1}$$$ равен медиане этого массива. Другими словами, массив является плохим, если после его сортировки элемент на $$$m+1$$$-й позиции остается неизменным.

Назовем перестановку $$$p$$$ целых чисел от $$$1$$$ до $$$n$$$ анти-медианной, если каждый ее подмассив нечетной длины $$$\ge 3$$$ не является плохим.

Вам уже даны значения некоторых элементов перестановки. Найдите количество способов задать неизвестные значения, чтобы получить анти-медианную перестановку. Поскольку это число может быть очень большим, найдите его по модулю $$$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$$$.

Пример
Входные данные
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
Выходные данные
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]$$$.