CF1699C.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$.

Since the total number of such permutations can be very large, you will have to print its remainder modulo $10^9+7$.

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.

给你一个由 $0$ 到 $n-1$ 的整数构成的排列 $a_1,a_2,\ldots,a_n$。你的任务是求出有多少个排列 $b_1,b_2,\ldots,b_n$ 与排列 $a$ 相似。

对于大小为 $n$ 的两个排列 $a$ 和 $b$，若对所有区间 $[l,r]$（其中 $1 \le l \le r \le n$），均满足以下条件，则称它们相似：

$$\operatorname{MEX}([a_l,a_{l+1},\ldots,a_r])=\operatorname{MEX}([b_l,b_{l+1},\ldots,b_r]),$$

其中，集合 $c_1,c_2,\ldots,c_k$ 的 $\operatorname{MEX}$ 定义为未出现在该集合中的最小非负整数 $x$。例如，$\operatorname{MEX}([1,2,3,4,5])=0$，而 $\operatorname{MEX}([0,1,2,4,5])=3$。

由于满足条件的排列总数可能非常大，你只需输出其对 $10^9+7$ 取模的结果。

在本题中，大小为 $n$ 的排列是指由 $0$ 到 $n-1$ 的 $n$ 个互不相同的整数组成的任意顺序的数组。例如，$[1,0,2,4,3]$ 是一个排列，而 $[0,1,1]$ 不是，因为 $1$ 在数组中出现了两次；$[0,1,3]$ 也不是排列，因为此时 $n=3$，但数组中包含了 $3$（超出了 $0$ 到 $n-1$ 的范围）。

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$.

每个测试包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来的行包含各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示排列 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个互不相同的整数 $a_1,a_2,\ldots,a_n$（$0 \le a_i \lt n$），即排列 $a$ 的元素。

保证所有测试用例的 $n$ 值之和不超过 $10^5$。

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

对于每个测试用例，输出一个整数，表示与排列 $a$ 相似的排列的数量，结果对 $10^9+7$ 取模。

For the first test case, the only permutations similar to $a=[4,0,3,2,1]$ are $[4,0,3,2,1]$ and $[4,0,2,3,1]$.

For the second and third test cases, the given permutations are only similar to themselves.

For the fourth test case, there are $4$ permutations similar to $a=[1,2,4,0,5,3]$:

• $[1,2,4,0,5,3]$;
• $[1,2,5,0,4,3]$;
• $[1,4,2,0,5,3]$;
• $[1,5,2,0,4,3]$.

对于第一个测试用例，唯一与 $a=[4,0,3,2,1]$ 相似的排列是 $[4,0,3,2,1]$ 和 $[4,0,2,3,1]$。

对于第二个和第三个测试用例，给定的排列仅与自身相似。

对于第四个测试用例，共有 $4$ 个排列与 $a=[1,2,4,0,5,3]$ 相似：

• $[1,2,4,0,5,3]$；
• $[1,2,5,0,4,3]$；
• $[1,4,2,0,5,3]$；
• $[1,5,2,0,4,3]$。