You are given an array $A$ of length $N$. Your task is to find the number of permutations of length $N$ from which you can construct the given array $A$ using the following rule:

• For each element $A[i]$ in the array $A$, it must be equal to the minimum value among the elements in positions 1 through $i$ of the permutation $P$ i.e. $A[i] = min(P[1], P[2], ..., P[i])$.

Since the answer could be a large number, you need to compute it modulo $10^9+7$.

A permutation is a sequence of integers from $1$ to $N$ of length $N$ containing each number exactly once. For example, $[1], [4, 3, 5, 1, 2], [2, 3, 1]$ are permutations and $[1, 1], [4, 3, 1], [2, 3, 4]$ are not.

Input format

• The first line contains an integer $T$, denoting the number of test cases.
• The first line of each test casecontains an integer $N$.
• The next line of each test case contains $N$ space-separated integers, elements of array $A$.

Output format

For each test case, print the number of permutations of length $N$ from which you can construct the given array $A$. Since the answer could be very large, print it modulo $10^9+7$.

Constraints

$1 \leq T \leq 10 \\ 1 \leq N \leq 10^5 \\ 1 \leq A[i] \leq N$