CF2159C Twin Polynomials

一个多项式 $f(x) = a_0 + a_1x + a_2x^2 + \ldots + a_nx^n$ 当且仅当对于所有 $0 \le i \le n$，$a_i$ 都是非负整数且 $a_n \neq 0$ 时，被称为一个合法的 $n$ 次多项式。 对于一个 $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”，当且仅当 $f(x) = g(x)$。换句话说，$f(x)$ 的孪生多项式恰好等于它自身时，该多项式是 cool 的。 你现在有一个不完整的 $n$ 次合法多项式 $f(x) = a_0 + a_1x + a_2x^2 + \ldots + a_nx^n$，其中部分 $a_i$ 的值已知，部分未知。此外，保证 $a_0$ 和 $a_n$ 的值均未知。 请你统计，所有可能填补未知项 $a_i$ 的方式中，使得该多项式成为 cool 多项式的合法 $n$ 次多项式的个数。由于答案可能很大，请输出对 $1\,000\,000\,007$ 取模的结果。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 对于每组测试用例，第一行包含一个整数 $n$（$1 \leq n \leq 4 \times 10^5$）。 第二行包含 $n+1$ 个整数 $a_0, a_1, \ldots, a_n$（$-1 \leq a_i \leq 10^9$）。其中，$a_i = -1$ 表示该项的值未知，$a_i \neq -1$ 表示该项的值已知。 保证输入中 $a_0$ 和 $a_n$ 始终为 $-1$。 保证所有测试用例中 $n$ 的总和不超过 $4 \times 10^5$。

对于每组测试用例，输出通过确定所有未知 $a_i$ 后能得到的 cool 合法 $n$ 次多项式的个数，对 $1\,000\,000\,007$ 取模。

在第一个测试用例中，只有 $f(x) = x$ 满足条件。 在第二个测试用例中，只有 $f(x) = x^2 + 2x$ 满足条件。 在第三个测试用例中，$f(x) = 2x^2 + x$、$f(x) = x^2 + 2x$ 和 $f(x) = 2x^2 + 1$ 满足条件。 由 ChatGPT 5 翻译