Description

在火星的第一城市有 $N$ 个公交车站，这些车站都排成一条直线，总长度为 $N-1$ 千米。市长喜欢简洁，所以他将公交车站编号为 $1$ 到 $N$，相邻车站之间的距离恰好为 $1$ 千米。

城市里还有 $K$ 辆公交车。市长需要制定公交车的运行计划，他想知道有多少种不同的安排方式。这个数字可能非常大。幸运的是，有一些限制条件：

• 一天开始时，所有公交车都在前 $K$ 个车站（每个车站一辆公交车）。
• 公交车只能从左向右移动（$1$ 号为最左侧车站）。
• 一天结束时，所有公交车都必须在最后 $K$ 个车站（每个车站一辆公交车）。
• 每个车站恰好有一辆公交车停靠。
• 对于同一辆公交车，任意两次连续停靠的车站之间的距离最多为 $P$ 千米。

请帮助市长计算有多少种安排公交车运行计划的方式。由于答案可能很大，只需输出该数字对 $30031$ 取模的结果。

Input Format

输入文件的第一行为测试用例数 $T$。

接下来的 $T$ 行，每行包含 $3$ 个用空格分隔的整数：$N$、$K$ 和 $P$。

Output Format

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

3
10 3 3
5 2 3
40 4 8

Case #1: 1
Case #2: 3
Case #3: 7380

Hint

样例解释

我们将公交车命名为 $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 翻译