From a permutation \(P\) of length \(N\), Alice constructs an array \(A\) of length \(N\) such that \(A_i = \max(P_1, P_2,\dots, P_i)\). For example, if \(P = [2, 1, 3, 5,4 ]\), then Alice constructs the array \(A = [2, 2, 3, 5,5 ]\).

You are given an array \(A\) containing \(N\) integers. Find the number of permutations of length \(N\) from which Alice can construct the given array \(A\). Since the answer can be very large, print it modulo \((10^9+7) \).

Input format

• The first line contains \(T\) denoting the number of test cases. The description of \(T\) test cases is as follows:
• For each test case:
  • The first line contains a single integer \(N\) denoting the size of array \(A\).
  • The second line contains \(N\) integers \(A_1, A_2, \dots, A_N\) denoting the elements of \(A\).

Output format
For each test case, print the number of permutations, modulo \((10^9+7) \) of length \(N\) from which the given array \(A\) can be constructed.

Constraints