CF2159C.Twin Polynomials

A polynomial $f(x) = a_0 + a_1x + a_2x^2 + \ldots + a_nx^n$ is called a valid polynomial of degree $n$ if and only if $a_i$ is a non-negative integer for all $0 \le i \le n$ and $a_n$ is not $0$.

For a valid polynomial $f(x) = a_0 + a_1x + a_2x^2 + \ldots + a_nx^n$ of degree $n$, its twin polynomial $g(x)$ is defined as: $$ g(x) = \sum_{i=0}^n i \cdot x^{a_i} $$ For example, for $f(x) = 1 + 2x + 2x^3$, its twin polynomial is:

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

A valid polynomial $f(x)$ of degree $n$ is called cool if and only if $f(x) = g(x)$. In other words, a valid polynomial of degree $n$ is cool if and only if its twin polynomial equals itself.

You are given an incomplete valid polynomial $f(x) = a_0 + a_1x + a_2x^2 + \ldots + a_nx^n$ of degree $n$. Some of $a_i$ have been determined, while others have not been determined. Additionally, it is guaranteed that $a_0$ and $a_n$ are not determined.

Please count the number of cool valid polynomials of degree $n$ that can be found by determining all undetermined $a_i$'s. Since the answer may be large, you need to output it modulo $1\,000\,000\,007$.

一个多项式 $f(x) = a_0 + a_1x + a_2x^2 + \ldots + a_nx^n$ 被称为合法的 $n$ 次多项式，当且仅当对所有 $0 \le i \le n$，系数 $a_i$ 均为非负整数，且首项系数 $a_n \neq 0$。

对于一个合法的 $n$ 次多项式 $f(x) = a_0 + a_1x + a_2x^2 + \ldots + a_nx^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$$

一个合法的 $n$ 次多项式 $f(x)$ 被称为酷多项式（cool polynomial），当且仅当 $f(x) = g(x)$。换言之，一个合法的 $n$ 次多项式是酷多项式，当且仅当它的孪生多项式等于它自身。

现给出一个不完整的合法 $n$ 次多项式 $f(x) = a_0 + a_1x + a_2x^2 + \ldots + a_nx^n$，其中部分系数 $a_i$ 已确定，其余未确定。此外，保证 $a_0$ 和 $a_n$ 均未确定。

请计算：通过为所有未确定的 $a_i$ 赋值，能够得到多少个酷的合法 $n$ 次多项式。由于答案可能很大，请输出其对 $1\,000\,000\,007$ 取模的结果。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

For each test case, the first line contains an integer $n$ ($1 \leq n \leq 4 \cdot 10^5$).

The second line contains $n+1$ integers $a_0, a_1, \ldots, a_n$ ($-1 \leq a_i \leq 10^9$). Here, $a_i=-1$ means $a_i$ has not been determined, while $a_i \neq -1$ means $a_i$ has been determined as its value.

It is guaranteed that $a_0$ and $a_n$ are always $-1$ in the input.

It is guaranteed that the sum of $n$ over all test cases does not exceed $4 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output the number of cool valid polynomials of degree $n$ found by determining the undetermined $a_i$'s, modulo $1\,000\,000\,007$.

对于每个测试用例，输出通过确定未定系数 $a_i$ 所找到的次数为 $n$ 的“酷”有效多项式的数量，结果对 $1\,000\,000\,007$ 取模。

In the first test case, only $f(x) = x$ satisfies the condition above.

In the second test case, only $f(x) = x^2 + 2x$ satisfies the condition above.

In the third test case, $f(x) = 2x^2 + x$, $f(x) = x^2 + 2x$, and $f(x) = 2x^2 + 1$ satisfy the condition above.

在第一个测试用例中，只有 $f(x) = x$ 满足上述条件。

在第二个测试用例中，只有 $f(x) = x^2 + 2x$ 满足上述条件。

在第三个测试用例中，$f(x) = 2x^2 + x$、$f(x) = x^2 + 2x$ 和 $f(x) = 2x^2 + 1$ 满足上述条件。