CFCF2159C.Twin Polynomials

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

一个多项式 $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$ 取模。

输入#1

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

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

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

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