这是问题的简单版本。版本之间的区别在于,在这个版本中,所有$$$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$$$ 表示间隙。
在此版本的问题中,保证所有 $$$a_i = 0$$$。
保证所有测试用例的 $$$m$$$ 值的总和不超过 $$$10^4$$$。
输出
对于每个测试用例,输出从 $$$1$$$ 到 $$$n$$$ 的数字来填补空白的方法数量,以便飞机发射的时间顺序是可信的,以 $$$10^9 + 7$$$ 为模。
示例
输入 #1
2 3 2 4 0 0 0 0 5 5 7 0 0 0 0 0 0 0
输出 #1
6 190
注意
在第一个测试示例中,填补空白的所有六种可能的方法如下:
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$$$。