In a land where numbers hold the key to order, there exists an array of size \(N\). This array contains numbers ranging from \(0\) to \( 10^6\).
The challenge is to replace all the zeros in this array with positive integers while ensuring that every subsequence of the final modified array is strictly increasing.
If there are an infinite number of ways to replace all the zeros with positive integers such that the aforementioned condition is met, you must print \(-1\), and if there are a finite number of ways to do so, you must print the total number of such ways modulo \(1000000007\).
Note: Two ways of replacing zeros are different if the final array obtained after all replacements are different.
Input format
Output format
For each test case, print in a new line the number of ways to replace all the zeros with positive integers in such a way that the above condition is satisfied, modulo \(1000000007\), and \(-1\) if there are infinite ways to do so.
Constraints
\(1 \leq T \leq 10^5 \\ 1 \leq N \leq 10^6 \\ 0≤A[i]≤10^6\ ∀\ i∈[1,N] \\ \text{The sum of all values of N over all test cases doesn't exceed } 10^6\)
For test case \(1\):
The following are the final modified arrays that can be obtained by replacing 0's with positive integers such that every subsequence of the final modified array is strictly increasing:
Thus, the answer is 3.