7.7 The Tortoise of Bandra's Polynomial Gardens
Jash lives in Bandra, Mumbai, where he runs a unique pet sanctuary specializing in tortoises. One day, a mysterious elderly mathematician visits his sanctuary with an ancient tortoise named Polynomius. The tortoise has peculiar shell patterns that form polynomial sequences!
The mathematician explains that Polynomius is no ordinary tortoise - he's a "twin polynomial tortoise" whose shell segments represent coefficients of polynomials. The tortoise will only eat lettuce if the polynomial formed by his shell pattern is "cool" (meaning the polynomial equals its twin polynomial).
Jash needs to determine how many different ways he can feed Polynomius by filling in the missing shell segments (undetermined coefficients) to make cool polynomials. Some shell segments are already fixed, while others can be chosen. The mathematician warns that the first and last segments (a₀ and aₙ) are always missing and must be filled in.
A polynomial f(x) = a₀ + a₁x + a₂x² + ... + aₙxⁿ is called a valid polynomial of degree n if and only if aᵢ is a non-negative integer for all 0 ≤ i ≤ n and aₙ is not 0.
For a valid polynomial f(x) = a₀ + a₁x + a₂x² + ... + aₙxⁿ of degree n, its twin polynomial g(x) is defined as:
g(x) = Σ(i=0 to n) i · xᵃⁱ
For example, for f(x) = 1 + 2x + 2x³, its twin polynomial is:
g(x) = 0·x¹ + 1·x² + 2·x⁰ + 3·x² = 0 + x² + 2 + 3x² = 2 + 4x²
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₀ + a₁x + a₂x² + ... + aₙxⁿ of degree n. Some of aᵢ have been determined, while others have not been determined. Additionally, it is guaranteed that a₀ and aₙ are not determined.
Please count the number of cool valid polynomials of degree n that can be found by determining all undetermined aᵢ's. Since the answer may be large, you need to output it modulo 1 000 000 007.
Constraints
1 ≤ t ≤ 10⁴
1 ≤ n ≤ 4·10⁵
−1 ≤ aᵢ ≤ 10⁹
It is guaranteed that a₀ and aₙ are always −1 in the input.
It is guaranteed that the sum of n over all test cases does not exceed 4·10⁵.
Input Format
Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10⁴). The description of the test cases follows.
For each test case, the first line contains an integer n (1 ≤ n ≤ 4·10⁵).
The second line contains n + 1 integers a₀, a₁, ..., aₙ (−1 ≤ aᵢ ≤ 10⁹). Here, aᵢ = −1 means aᵢ has not been determined, while aᵢ ≠ −1 means aᵢ has been determined as its value.
Output Format
For each test case, output the number of cool valid polynomials of degree n found by determining the undetermined aᵢ's, modulo 1 000 000 007.
Example 1
Input:
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
Output:
1
1
2
2
0
3
Explanation:
In the first test case, only 𝑓(𝑥)=𝑥 satisfies the condition above.
In the second test case, only 𝑓(𝑥)=𝑥^2+2𝑥 satisfies the condition above.
In the third test case, 𝑓(𝑥)=2𝑥^2+𝑥, 𝑓(𝑥)=𝑥^2+2𝑥 , and 𝑓(𝑥)=2𝑥^2+1 satisfy the condition above.
Log In to solve the Question