CF2066D2 Club of Young Aircraft Builders (hard version)

这是该问题的困难版本。各版本间的区别在于此版本中不要求所有 $a_i = 0$。只有当您解决了该问题的所有版本时才能进行 hack。 有一栋 $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. $[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$ 层的居民发射——从他们的视角看，当时已有 $c = 2$ 架飞机被发射。 同样地，数组 $[1, 1, 2, 3]$ 也不是有效方案，因为从第 $3$ 层居民的视角看，仅发射了 $1$ 架飞机，而 $c = 2$。 翻译由 DeepSeek R1 完成