A8524.相似排列

普及+/提高

官方

通过率:0%

题目描述

Yuilice 会给定一个由从 00n1n - 1 的整数组成的排列 a1,a2,,ana_1,a_2,\ldots,a_n。你的任务是找出有多少个排列 b1,b2,,bnb_1,b_2,\ldots,b_n 与排列 aa 相似

如果在所有区间 [l,r][l,r](1lrn1 \le l \le r \le n) 中,如果可以找到以下条件,那么大小为 nn 的两个排列 aabb 就可以被认为是 相似 排列:

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

其中整数集合 c1,c2,,ckc_1,c_2,\ldots,c_kMEX\operatorname{MEX} 定义为集合 cc 中不出现的最小非负整数 xx
例如:MEX([1,2,3,4,5])=0\operatorname{MEX}([1,2,3,4,5])=0MEX([0,1,2,4,5])=3\operatorname{MEX}([0,1,2,4,5])=3

由于最后的结果可能过大,请将答案对 109+710^9 + 7 取模后输出

注意:大小为 nn 的排列是由 00n1n-1 之间的 nn 个不同整数按任意顺序排列而成的数组。

例如:

[2,0,1,4,3][2,0,1,4,3]可以被称之为是一个排列,但是[2,3,3][2,3,3]不可以,因为33出现了两次。

假若 n=3n = 3,那么 [1,2,3][1,2,3] 不是一个合法排列,因为数字 33 存在于数组当中。

输入格式

每个测试点包含多个测试用例。第一行输入包含一个整数 tt (1t1041 \le t \le 10^4) - 代表测试用例的数量。下面几行包含测试用例的描述。

每个测试用例的第一行都包含一个整数 nn (1n1051 \le n \le 10^5) 代表排列 aa 的大小。

每个测试用例的第二行包含 nn 个不同的整数 a1,a2,,ana_1,a_2,\ldots,a_n (0ai<n0 \le a_i \lt n) - 排列 aa 的元素。

保证所有测试用例中 nn 的总和不超过 10510^5

输出格式

对于每个测试用例,打印一个整数,即与 排列 aa 相似的 排列 的数量,请取模 109+710^9+7 后进行输出

输入输出样例

  • 输入#1

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

    输出#1

    2
    1
    1
    6
    24

说明/提示

  • a=[4,0,3,2,1]a = [4,0,3,2,1] 时,与其相似的序列为[4,0,3,2,1][4,0,3,2,1][4,0,2,3,1][4,0,2,3,1]
  • 第二组样例与第三组样例相似序列都为他本身。
首页