E. Vlad, Misha and Two Arrays
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Vlad thought of a permutation $$$p$$$ of length $$$n$$$. After that, for each $$$i$$$ from $$$1$$$ to $$$n$$$, he counted the number of pairs $$$l, r$$$ such that $$$1 \leq l \leq r \leq n$$$ and the minimum number among $$$p_l, p_{l+1}, \ldots, p_r$$$ is equal to $$$p_i$$$, and wrote this number into $$$a_i$$$.

Now he gave Misha the numbers $$$a_1, a_2, \ldots, a_n$$$ and asked him to guess the permutation $$$p$$$. However, Misha quickly realized that it is not always possible to uniquely restore the permutation $$$p$$$. Therefore, he decided to surprise Vlad and tell him the number of suitable permutations $$$p$$$ modulo $$$10^9+7$$$. Help him with this. Note that Vlad could have made a mistake, and there may be no such permutations.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

In the first line of each test case, a natural number $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) is given — the size of the permutation.

In the second line of each test case, $$$n$$$ numbers $$$a_1, a_2, \ldots a_n$$$ ($$$1 \leq a_i \leq 10^{12}$$$) are given — the array $$$a$$$ that Vlad gave to Misha.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, output the number of suitable permutations modulo $$$10^9+7$$$.

Example
Input
4
3
1 4 1
4
1 2 3 4
4
1 6 1 2
3
3 3 3
Output
2
1
3
0
Note

In the first test case, there exist exactly two suitable permutations: $$$p = [2, 1, 3]$$$ and $$$p = [3, 1, 2]$$$.

In the second test case, the only suitable permutation is $$$p = [4, 3, 2, 1]$$$.

In the fourth test case, it can be shown that no permutation $$$p$$$ corresponds to the array $$$a$$$.