题目描述

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

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

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

其中，$\text{MEX}$ 表示一组整数 $c_1, c_2, \dots, c_k$ 中未出现的最小非负整数。例如，$\text{MEX}([1, 2, 3, 4, 5]) = 0$，$\text{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$。

输入格式

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

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

第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \dots, a_n$（$0 \le a_i < n$）——排列 $a$ 的元素。

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

输出格式

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

输入输出样例

输入 #1

5
5
4 0 3 2 1
1
0
4
0 1 2 3
6
1 2 4 0 5 3
8
1 3 7 2 5 0 6 4

输出 #1

2
1
1
4
72

说明/提示

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

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

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

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