← 返回题目列表

Codeforces · 2066/D2

D2. 青年飞机制造商俱乐部(硬版)

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

这是问题的困难版本。版本之间的区别在于,在此版本中,不需要 $$$a_i = 0$$$。只有解决了该问题的所有版本,您才能破解。

有一栋大楼,共有$$$n$$$层,从下到上编号为$$$1$$$到$$$n$$$。每层楼正好住一个人。

今天,大楼里的所有居民都有一个重要目标:集体发射至少 $$$c$$$ 纸飞机。居民们将依次发射飞机。当来自 $$$i$$$ 层的人发射飞机时,$$$1$$$ 到 $$$i$$$ 楼​​层的所有居民都可以看到飞机降落到地面。如果从$$$i$$$层的居民的角度来看,至少已经起飞了$$$c$$$架飞机,他们将不再自己起飞飞机。另据了解,到当天结束时,从楼内每位住户的角度来看,至少已升空$$$c$$$架飞机,总共抛出了$$$m$$$架飞机。

您一直在仔细监控这个快闪族,对于每架飞机,您都记录了哪个居民从哪个楼层扔了它。不幸的是,有关谁扔掉一些飞机的信息已经丢失。找出填补空白的方法,使信息可信。由于答案可能相当大,因此输出它对 $$$10^9 + 7$$$ 取模。

也有可能您在记录中犯了错误,并且无法恢复间隙。在这种情况下,答案被认为是 $$$0$$$。

输入

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

每个测试用例的第一行包含三个整数 $$$n, c, m$$$ ($$$1 \le n \le 100$$$, $$$1 \le c \le 100$$$, $$$c \le m \le n \cdot c$$$) — 建筑物的楼层数、最低要求的飞机数量以及实际起飞的飞机数量。

每个测试用例的第二行包含 $$$m$$$ 整数 $$$a_1, a_2, \ldots, a_m$$$ ($$$0 \le a_i \le n$$$) — $$$a_i$$$ 表示居民从哪个楼层发射了第 $$$i$$$ 架飞机; $$$a_i = 0$$$ 表示间隙。

保证所有测试用例的 $$$m$$$ 值的总和不超过 $$$10^4$$$。

输出

对于每个测试用例,输出从 $$$1$$$ 到 $$$n$$$ 之间的数字来填补空白的方法数量,以便飞机发射的时间顺序可信,以 $$$10^9 + 7$$$ 为模。

示例

输入 #1

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

输出 #1

6
190
3
2
0
0
1
14

注意

在第一个测试示例中,填补空白的所有六种可能的方法如下:

1. $$$[1, 1, 3, 3]$$$
2. $$$[1, 2, 3, 3]$$$
3. $$$[1, 3, 2, 3]$$$
4. $$$[2, 1, 3, 3]$$$
5. $$$[2, 2, 3, 3]$$$
6. $$$[3, 1, 2, 3]$$$

请注意,数组 $$$[2, 3, 1, 3]$$$ 不是填补空白的有效方法,因为第三架飞机不可能由 $$$1$$$st 层的人发射,因为从他们的角度来看,$$$c = 2$$$ 飞机已经发射。

另外,数组 $$$[1, 1, 2, 3]$$$ 不是填补空白的有效方法,因为从 $$$3$$$rd 楼的人的角度来看,只有 $$$1$$$ 飞机已启动,而 $$$c = 2$$$。