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

• The first line contains a single integer \(T\), which denotes the number of test cases.
• For each test case:
  • The first line contains \(N\) denoting the size of array \(A\).
  • The second line contains \(N\) space-separated integers, denoting the elements of \(A\).

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