Bus Stops (Small)

The First City of Mars has $N$ bus stops, all placed on one straight road of length $N-1$ km. The mayor likes simple things, so he numbered the stops from 1 to $N$ starting at the left end and put adjacent stops exactly 1 km apart.

The city has $K$ buses. The mayor wants to know how many ways there are to plan one day of service. A plan has to satisfy all of the following conditions.

• At the beginning of the day the $K$ buses stand at the first $K$ stops, one bus per stop.
• Buses only move to the right. Stop 1 is the leftmost stop.
• At the end of the day the $K$ buses must stand at the last $K$ stops, one bus per stop.
• Exactly one bus stops at every bus stop.
• For a single bus, the distance between two consecutive stops it serves is at most $P$ km.

The route of a bus is the list of stops it serves, ordered by increasing stop number. Two plans are different if some stop is served by a different bus. The number of plans can be very large, so print it modulo 30031.

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

Limits

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

For each test case, print the number of plans modulo 30031 on its own line, in the format Case #t: X, where $t$ is the test case number starting from 1 and X is the remainder.

For $N = 10$, $K = 3$, $P = 3$ there is only one plan. Name the buses A, B and C. Then A serves stops 1, 4, 7, 10, bus B serves 2, 5, 8, and bus C serves 3, 6, 9.

For $N = 5$, $K = 2$, $P = 3$ there are three plans.

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