在火星的第一城市有 $N$ 个公交车站，它们排列在一条长为 $N-1$ 公里的直线上。市长喜欢简单，所以他将公交车站从 1 到 $N$ 编号，相邻车站之间的距离恰好为 1 公里。

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

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

请帮助市长计算时刻表的数量。由于结果可能非常大，请输出结果对 30031 取模后的值。

输入格式

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

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

输出格式

对于每个测试用例，输出公交时刻表的规划方案数（对 30031 取模），格式为 "Case #$t$: [方案数对 30031 取模的结果]"，其中 $t$ 是测试用例的编号，从 1 开始。

数据范围

$1 < T \le 30$

$1 < P \le 10$

$K < N$

$1 < K \le P$

小数据集（测试集 1 - 可见；8 分）

$1 < N < 1000$

大数据集（测试集 2 - 隐藏；26 分）

$1 < N < 10^9$

样例

样例输入 1

3
10 3 3
5 2 3
40 4 8

样例输出 1

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

说明

我们将公交车命名为：A, B, C...

对于第一个样例，只有一种可能的时刻表规划方式： A $\to$ 1, 4, 7, 10。B $\to$ 2, 5, 8。C $\to$ 3, 6, 9。

对于第二个样例，可能的规划方式有：

(A $\to$ 1, 3, 5. B $\to$ 2, 4),

(A $\to$ 1, 3, 4. B $\to$ 2, 5),

(A $\to$ 1, 4. B $\to$ 2, 3, 5)。