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$$$.
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$$$.
Print $$$t$$$ answers to the test cases. Each answer must be consisting of single integer — the number of awesome arrays modulo $$$10^9+7$$$
4 3 1 1 2 3 1 2 3 2 1 2 3 2 1 2
1 4 2 0
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.
Name |
---|