You are given N distinct numbers in the form of an array \(Arr_i\). You can form a Binary Search Tree(BST) by inserting them in the order they are given.Now find the number of different permutations of the array, so that the BST formed in each permutation is same as that of the given array(including the given permutation). As the number can be large, output modulo \((10^9+7)\).

Constraints:

• \(1 ≤ T ≤ 10\)
• \(1 ≤ N ≤ 1000\)
• \(1 ≤ Arr_i ≤ 1000000000\)

Format of the input file:
First line : T i.e Number of testcases.
For each testcase :
First line : N.
Second line : N space separated integers denoting the array .

Format of the output file:
Output the answer to each testcase in a separate line.