这是问题的困难版本。版本之间的区别在于,在此版本中,不需要 $$$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$$$。