← 返回题目列表

Codeforces · 1699/C

C. 第三个问题

中文机器翻译题面 查看原题

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

如果对于所有区间 $$$[l,r]$$$ ($$$1 \le l \le r \le n$$$),满足以下条件,则大小为 $$$n$$$ 的两个排列 $$$a$$$ 和 $$$b$$$ 被视为相似: $$$$$$\operatorname{MEX}([a_l,a_{l+1},\ldots,a_r])=\operatorname{MEX}([b_l,b_{l+1},\ldots,b_r]),$$$$$$ 其中 $$$\operatorname{MEX}$$$ 是整数集合$$$c_1,c_2,\ldots,c_k$$$ 被定义为集合 $$$c$$$ 中不出现的最小非负整数 $$$x$$$。例如,$$$\operatorname{MEX}([1,2,3,4,5])=0$$$,$$$\operatorname{MEX}([0,1,2,4,5])=3$$$。

由于此类排列的总数可能非常大,因此您必须打印其对 $$$10^9+7$$$ 取模的余数。

在此问题中,大小 $$$n$$$ 的排列是一个由 $$$n$$$ 个不同整数组成的数组,从 $$$0$$$ 到 $$$n-1$$$ 的任意顺序。例如,$$$[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,\ldots,a_n$$$ ($$$0 \le a_i \lt 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]$$$.