C. Полиномы-близнецы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Полином $$$f(x) = a_0 + a_1x + a_2x^2 + \ldots + a_nx^n$$$ называется корректным полиномом степени $$$n$$$, если и только если $$$a_i$$$ является целым неотрицательным числом для всех $$$0 \le i \le n$$$ и $$$a_n$$$ не равно $$$0$$$.

Для корректного полинома $$$f(x) = a_0 + a_1x + a_2x^2 + \ldots + a_nx^n$$$ степени $$$n$$$ его полином-близнец $$$g(x)$$$ определяется как: $$$$$$ g(x) = \sum_{i=0}^n i \cdot x^{a_i} $$$$$$ Например, для $$$f(x) = 1 + 2x + 2x^3$$$ его полином-близнец будет:

$$$$$$ g(x) = 0 \cdot x^{1} + 1 \cdot x^{2} + 2 \cdot x^{0} + 3 \cdot x^{2} = 0+x^2+2+3x^2= 2 + 4x^2 $$$$$$

Корректный полином $$$f(x)$$$ степени $$$n$$$ называется крутым, если и только если $$$f(x) = g(x)$$$. Другими словами, корректный полином степени $$$n$$$ является крутым, если и только если его полином-близнец равен ему самому.

Вам дан неполный допустимый полином $$$f(x) = a_0 + a_1x + a_2x^2 + \ldots + a_nx^n$$$ степени $$$n$$$. Некоторые из $$$a_i$$$ были определены, в то время как другие не были определены. Кроме того, гарантируется, что $$$a_0$$$ и $$$a_n$$$ не определены.

Пожалуйста, посчитайте количество крутых допустимых полиномов степени $$$n$$$, которые можно найти, определив все неопределенные $$$a_i$$$. Поскольку ответ может быть большим, вам нужно вывести его по модулю $$$1\,000\,000\,007$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 4 \cdot 10^5$$$).

Вторая строка содержит $$$n+1$$$ целых числа $$$a_0, a_1, \ldots, a_n$$$ ($$$-1 \leq a_i \leq 10^9$$$). Здесь $$$a_i=-1$$$ означает, что $$$a_i$$$ не было определено, в то время как $$$a_i \neq -1$$$ означает, что $$$a_i$$$ было определено как его значение.

Гарантируется, что $$$a_0$$$ и $$$a_n$$$ всегда равны $$$-1$$$ во входных данных.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$4 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите количество крутых допустимых полиномов степени $$$n$$$, которые можно получить путём определения неопределенных $$$a_i$$$, по модулю $$$1\,000\,000\,007$$$.

Пример
Входные данные
6
1
-1 -1
2
-1 2 -1
2
-1 -1 -1
3
-1 -1 3 -1
3
-1 2 3 -1
5
-1 -1 -1 1 0 -1
Выходные данные
1
1
3
2
0
3
Примечание

В первом наборе входных данных только $$$f(x) = x$$$ удовлетворяет вышеуказанному условию.

Во втором наборе входных данных только $$$f(x) = x^2 + 2x$$$ удовлетворяет вышеуказанному условию.

В третьем наборе входных данных $$$f(x) = 2x^2 + x$$$, $$$f(x) = x^2 + 2x$$$ и $$$f(x) = 2x^2 + 1$$$ удовлетворяют вышеуказанному условию.