A15242 | The Third Problem

You are given a permutation $a_1,a_2,\ldots,a_n$ of integers from $0$ to $n - 1$ . Your task is to find how many permutations $b_1,b_2,\ldots,b_n$ are similar to permutation $a$ .

Two permutations $a$ and $b$ of size $n$ are considered similar if for all intervals $[l,r]$ ( $1 \le l \le r \le n$ ), the following condition is satisfied: $$$$\operatorname{MEX}([a_l,a_{l+1},\ldots,a_r])=\operatorname{MEX}([b_l,b_{l+1},\ldots,b_r]), $$ where the $\\operatorname{MEX}$ of a collection of integers $c\_1,c\_2,\\ldots,c\_k$ is defined as the smallest non-negative integer $x$ which does not occur in collection $c$ . For example, $\\operatorname{MEX}(\[1,2,3,4,5\])=0$ , and $\\operatorname{MEX}(\[0,1,2,4,5\])=3$ .</p><p>Since the total number of such permutations can be very large, you will have to print its remainder modulo $10^9+7$ .</p><p>In this problem, a permutation of size $n$ is an array consisting of $n$ distinct integers from $0$ to $n-1$ in arbitrary order. For example, $\[1,0,2,4,3\]$ is a permutation, while $\[0,1,1\]$ is not, since $1$ appears twice in the array. $\[0,1,3\]$ is also not a permutation, since $n=3$ and there is a $3$$$ in the array.

Each test contains multiple test cases. The first line of input contains one integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases. The following lines contain the descriptions of the test cases.

The first line of each test case contains a single integer $n$ ( $1 \le n \le 10^5$ ) — the size of permutation $a$ .

The second line of each test case contains $n$ distinct integers $a_1,a_2,\ldots,a_n$ ( $0 \le a_i \lt n$ ) — the elements of permutation $a$ .

It is guaranteed that the sum of $n$ across all test cases does not exceed $10^5$ .

For each test case, print a single integer, the number of permutations similar to permutation $a$ , taken modulo $10^9+7$ .