P13485 [GCJ 2008 EMEA SemiFinal] Bus Stops

在火星的第一城市有 $N$ 个公交车站，这些车站都排成一条直线，总长度为 $N-1$ 千米。市长喜欢简洁，所以他将公交车站编号为 $1$ 到 $N$，相邻车站之间的距离恰好为 $1$ 千米。 城市里还有 $K$ 辆公交车。市长需要制定公交车的运行计划，他想知道有多少种不同的安排方式。这个数字可能非常大。幸运的是，有一些限制条件： - 一天开始时，所有公交车都在前 $K$ 个车站（每个车站一辆公交车）。 - 公交车只能从左向右移动（$1$ 号为最左侧车站）。 - 一天结束时，所有公交车都必须在最后 $K$ 个车站（每个车站一辆公交车）。 - 每个车站恰好有一辆公交车停靠。 - 对于同一辆公交车，任意两次连续停靠的车站之间的距离最多为 $P$ 千米。 请帮助市长计算有多少种安排公交车运行计划的方式。由于答案可能很大，只需输出该数字对 $30031$ 取模的结果。

输入文件的第一行为测试用例数 $T$。 接下来的 $T$ 行，每行包含 $3$ 个用空格分隔的整数：$N$、$K$ 和 $P$。

对于每个测试用例，输出一种格式为 “Case #$t$: [number of ways modulo $30031$]” 的结果，其中 $t$ 表示测试用例编号，从 $1$ 开始。

**样例解释** 我们将公交车命名为 $A$、$B$、$C$…… 对于第一个样例，只有一种可能的安排方式：$A \rightarrow 1, 4, 7, 10$。$B \rightarrow 2, 5, 8$。$C \rightarrow 3, 6, 9$。 对于第二个样例，可能的安排方式有： - $(A \rightarrow 1,3,5. B \rightarrow 2,4)$， - $(A \rightarrow 1,3,4. B \rightarrow 2,5)$， - $(A \rightarrow 1,4. B \rightarrow 2,3,5)$。 **数据范围** - $1 < T \leq 30$ - $1 < P \leq 10$ - $K < N$ - $1 < K \leq P$ **小数据范围（8 分，测试点 1 - 可见）** - $1 < N < 1000$ **大数据范围（26 分，测试点 2 - 隐藏）** - $1 < N < 10^9$ 由 ChatGPT 4.1 翻译