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$.

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$.