Description

There are $N$ bus stops in Xiao Z’s city, arranged on a straight line of length $(N-1)\ \rm km$, numbered from left to right as $1$ to $N$. The distance between any two adjacent bus stops is $1 \ \rm km$. As the planner of bus routes, Xiao Z decides to design the routes according to the following rules:

1. Suppose there are $K$ buses. Then stops $1$ to $K$ serve as the starting stops, and stops $N-K+1$ to $N$ serve as the terminal stops.
2. Each stop must be visited by exactly one bus (starting and terminal stops are also considered visited).
3. A bus may only travel from a lower-numbered stop to a higher-numbered stop.
4. For any single bus, the distance between two consecutive stops it visits must not exceed $P \ \rm km$.

Before finalizing the design, Xiao Z wants to know how many valid plans satisfy the rules. Since the answer can be large, output the result modulo $30031$.

Input Format

A single line contains three positive integers $N$, $K$, and $P$, representing the number of bus stops, the number of buses, and the distance limit between consecutive stops, respectively.

Output Format

Output a single integer: the number of valid plans modulo $30031$.

10 3 3

1

5 2 3

3

10 2 4

81

Hint

Sample explanation:

• Sample 1 has the following valid plan: $(1,4,7,10)$, $(2,5,8)$, $(3,6,9)$.
• Sample 2 has the following valid plans: $(1,3,5)$, $(2,4)$; $(1,3,4)$, $(2,5)$; $(1,4)$, $(2,3,5)$.

Constraints:

For $100\%$ of the testdata, $1 \le N \le 10^9$, $1 < P \le 10$, $K < N$, $1 < K \le P$.

Translated by ChatGPT 5