D. Singhal and Permutations
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Singhal has a array of integers $$$a_1,a_2,\ldots,a_n$$$.

Definition of an awesome array —

If $$$K$$$ is the maximum element in the array, then the elements before $$$K$$$ in the array should be in the strictly ascending order and the elements after $$$K$$$ in the array should be in the strictly descending order.

Examples of awesome array are — $$$(1,2,3,1) , (1,2,3) , (3,2,1) , (1,2,1), (2,3,2,1) $$$ , but not $$$ (1,2,2) , (2,2,1) , (1,2,2,3) , (1,3,2,2). $$$

He wants to know that how many distinct awesome arrays he will get after reordering the sequence.

Reorder of array $$$ (1,3,3,4) $$$ can results $$$(1,4,3,3) , (3,4,3,1) ,(4,3,1,3) $$$, but not $$$ (1,3,3,3) , (1,3,3) , (1,3,3,4,4) $$$. You are not allowed to change the value, insert or delete.

Notice that the answer might be large, please output the desired value modulo $$$10^9+7$$$.

Input

The first line contains a single integer $$$t (1 \le t \le 10^5)$$$ — the number of test cases in the input. Then $$$t$$$ test cases follow.

Each query contains two lines. The first line contains one integer $$$n (1 \le n \le 10^5)$$$: the number of integers in the sequence, and the second line contains $$$n$$$ integers $$$a_1, \ldots ,a_n (1\le a_i \le 10^9)$$$.

It is guaranteed that the total sum of $$$n$$$ is at most $$$10^5$$$.

Output

Print $$$t$$$ answers to the test cases. Each answer must be consisting of single integer — the number of awesome arrays modulo $$$10^9+7$$$

Example
Input
4
3
1 1 2
3
1 2 3
2
1 2
3
2 1 2
Output
1
4
2
0
Note

In the first query,

There are a total of 3 possible array after reordering the given array $$$(1, 1, 2)$$$. They are: $$$(1,1,2)$$$, $$$(1,2,1)$$$ and $$$(2,1,1)$$$.

Out of the above, only $$$(1, 2, 1)$$$ is the awesome array.

In the second query,

There are a total of $$$6$$$ possible array after reordering. They are: $$$({1, 2, 3}), ({1, 3, 2}), ({2, 1, 3}), ({2, 3, 1}), ({3, 1, 2})$$$ and $$$ ({3, 2, 1})$$$.

Out of the above $$$4$$$ are awesome arrays.

In the last query ,

No awesome array we can formed after reordering the given array.