题目描述

In the First City of Mars there are $N$ bus stops, all aligned in a straight line of length $N-1$ km. The mayor likes to keeps things simple, so he gave the bus stops numbers from $1$ to $N$, and separated adjacent stops by exactly $1$ km.

There are also $K$ buses in the city. The mayor has to plan the bus schedule and he would like to know in how many ways that can be done. This number can be very large. Luckily there are a few constraints:

• In the beginning of the day all the buses are in the first $K$ bus stops (one bus per stop)
• Buses only move from the left to the right ($1$ is the leftmost bus stop)
• At the end of the day all the buses must be in the last $K$ bus stops (one bus per stop)
• In each bus station exactly one bus has to stop
• For the same bus the distance between any two consecutive stops is at most $P$ km

Help the mayor evaluate the number of schedules. However try not to give him very bad news (a lot of schedules) so just output the real number modulo $30031$.

输入格式

The first line in the input file is the number of cases $T$.

Each of the next $T$ lines contains $3$ integers separated by one space: $N$, $K$ and $P$.

输出格式

For each case output the number of ways to plan the bus schedules (modulo $30031$) in the format "Case #$t$: [number of ways modulo $30031$]" where $t$ is the number of the test case, starting from $1$.

3
10 3 3
5 2 3
40 4 8

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

提示

Sample Explanation

Let's name the buses: $A$, $B$, $C$...

For the first case there is only one possible way of planning the schedule: $A \rightarrow 1, 4, 7, 10$. $B \rightarrow 2, 5, 8$. $C \rightarrow 3, 6, 9$.

For the second case the possible ways of planning are:

• $(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)$.

Limits

• $1 < T \leq 30$
• $1 < P \leq 10$
• $K < N$
• $1 < K \leq P$

Small dataset (8 Pts, Test set 1 - Visible)

• $1 < N < 1000$

Large dataset (26 Pts, Test set 2 - Hidden)

• $1 < N < 10^9$