多项式 $$$f(x) = a_0 + a_1x + a_2x^2 + \ldots + a_nx^n$$$ 称为有效次数为 $$$n$$$ 的多项式当且仅当 $$$a_i$$$ 是所有 $$$0 \le i \le n$$$ 的非负整数且 $$$a_n$$$ 不是$$$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)$$$ 被称为 酷 当且仅当$$$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$$$。
输出
对于每个测试用例,输出 酷 通过确定未定的 $$$a_i$$$ 模 $$$1\,000\,000\,007$$$ 找到 $$$n$$$ 次的有效多项式。
示例
输入复制
61-1 -12-1 2 -12-1 -1 -13-1 -1 3 -13-1 2 3 -15-1 -1 -1 1 0 -1
输出复制
113203
注意
在第一个测试用例中,只有 $$$f(x) = x$$$ 满足上述条件。
在第二个测试用例中,只有 $$$f(x) = x^2 + 2x$$$ 满足上述条件。
在第三个测试用例中,$$$f(x) = 2x^2 + x$$$、$$$f(x) = x^2 + 2x$$$ 和 $$$f(x) = 2x^2 + 1$$$ 满足上述条件。