P3204 [HNOI2010] Bus Routes

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$.

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 a single integer: the number of valid plans modulo $30031$.

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