← 返回题目列表

Codeforces · 2207/E2

E2. N-MEX(计数版)

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

建造者基础攻击(第 2 阶段)— Supercell、《部落冲突》

这是问题的计数版本。版本之间的区别在于,在这个版本中,您需要计算 $$$0 \leq b_i \leq n$$$ 的构造数量。只有解决了该问题的所有版本,您才能破解。

建造大师不喜欢重复性任务——修复基地、升级市政厅十五次,以及做更多关于 MEX 的编程问题。所以,这不会是普通的 MEX 问题。

对于任何正整数 $$$k$$$,定义 $$$k$$$-墨西哥 整数集合 $$$S$$$ 的 是 $$$k$$$ 中不存在于 $$$S$$$ 中的第 $$$k$$$ 个最小非负整数。例如,$$$[1, 2, 1]$$$ 的 $$$1$$$-mex 和 $$$2$$$-mex 分别是 $$$0$$$ 和 $$$3$$$。

设 $$$n$$$ 为正整数,并考虑非负整数数组 $$$[a_1, \ldots, a_n]$$$。计算非负整数数组 $$$[b_1, \ldots, b_n]$$$ 的数量,使得:

  • 对于所有 $$$1 \leq i \leq n$$$,$$$[b_1, \ldots, b_i]$$$ 的 $$$(n-i+1)$$$-mex 为 $$$a_i$$$。
  • 此外,对于所有 $$$1 \leq i \leq n$$$,$$$0 \leq b_i \leq n$$$。
由于此类数组的数量可能很大,因此输出对 $$$10^9 + 7$$$ 取模的答案。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$)。

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

输出

对于每个测试用例,输出一个整数 - 满足数组 $$$b$$$ 模 $$$10^9 + 7$$$ 的数量。

示例

输入
复制

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

输出
复制

6
0
1
0
0
360

注意

在第一个测试用例中,数组 $$$a = [3, 3, 1]$$$。正好存在六个这样的有效数组$$$b$$$。其中一个示例是数组 $$$b = [2, 0, 2]$$$,它满足条件,因为:

  • $$$[b_1] = [2]$$$ 的 $$$3$$$-mex 为 $$$a_1 = 3$$$,
  • $$$[b_1, b_2] = [2, 0]$$$ 的 $$$2$$$-mex 为 $$$a_2 = 3$$$,
  • $$$[b_1, b_2, b_3] = [2, 0, 2]$$$ 的 $$$1$$$-mex 为 $$$a_3 = 1$$$。

在第二个测试用例中,数组 $$$a = [2, 1, 3]$$$。可以看出不存在合适的数组$$$b$$$。