Bus Stops (Large)

The First City of Mars has $N$ bus stops standing on one straight line of length $N-1$ km. The mayor likes to keep things simple, so the stops are numbered 1 to $N$ from the left, and two adjacent stops are exactly 1 km apart.

The city also runs $K$ buses. The mayor has to plan the bus schedule and wants to know how many ways there are to do it. That number can get very large. Luckily there are a few constraints:

• At the start of the day every bus sits on one of the first $K$ stops, one bus per stop.
• A bus only moves from left to right. Stop 1 is the leftmost stop.
• At the end of the day every bus must sit on one of the last $K$ stops, one bus per stop.
• Exactly one bus stops at each bus stop.
• For one bus, the distance between two stops it makes in a row is at most $P$ km.

Count the schedules for the mayor. To avoid giving him very bad news (a lot of schedules), print the real number modulo 30031.

The first line holds the number of cases $T$. Each of the next $T$ lines holds three integers separated by one space: $N$, $K$, and $P$.

Limits:

• $1 < T \le 30$
• $1 < P \le 10$
• $K < N$
• $1 < K \le P$
• $1 < N < 10^9$

For each case print one line in the format Case #t: x, where $t$ is the case number starting from 1 and $x$ is the number of schedules modulo 30031.

Name the buses A, B, C and so on, so that A starts on stop 1, B on stop 2, and so on.

For $N = 10$, $K = 3$, $P = 3$ there is exactly one schedule. A stops at 1, 4, 7, 10. B stops at 2, 5, 8. C stops at 3, 6, 9.

For $N = 5$, $K = 2$, $P = 3$ there are three schedules:

• A at 1, 3, 5 and B at 2, 4
• A at 1, 3, 4 and B at 2, 5
• A at 1, 4 and B at 2, 3, 5