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\)