Non‐Intersecting Bus Routes

There is a city with (N) bus stops arranged in a straight line. The stops are numbered from (1) to (N) in increasing order. Consecutive stops are exactly (1) km apart so that the total length of the line is ((N-1)) km. As the planner for the bus routes, Little Z has decided to use exactly (K) buses with the following rules:

1. The starting stops of the buses are fixed: bus (i) must start from stop (i) for (1 \le i \le K).
2. The ending stops are fixed: bus (i) must terminate at stop (N-K+i) for (1 \le i \le K).
3. Each bus runs from a lower‐numbered stop to a higher numbered stop (i.e. its route is strictly increasing) and each bus stop is covered by exactly one bus (including the starting and ending stops).
4. For every bus, if its route visits stops (s_0, s_1, \dots, s_r) in order (with (s_0) the starting stop and (s_r) the ending stop), then the distance between any two consecutive stops must not exceed (P) km; that is, for every (j = 0, 1, \dots, r-1), we have (s_{j+1} - s_j \le P).

Note that besides the mandatory stops (stop (i) for bus (i) and stop (N-K+i) as its terminal), all other stops can be assigned to one of the buses provided that every stop is covered exactly once and the route of each bus (i.e. the increasing sequence of stops it visits) satisfies the gap constraint.

Your task is to compute the number of valid ways to design the bus routes satisfying all the above conditions. Since the answer might be very large, output it modulo (30031).

Input Format: Three integers \(N, K, P\) separated by spaces.

Output Format: A single integer – the number of valid schemes modulo \(30031\).

Explanation: For example, when N = 4, K = 2 and P = 2, the mandatory stops are fixed: bus 1 must take stops 1 and 3, and bus 2 takes stops 2 and 4. Each bus has a single gap of 2 km which is acceptable when \(P = 2\); hence there is exactly 1 scheme. (Other examples are described in the sample test cases.)

inputFormat

The input consists of a single line containing three space‐separated integers \(N\) (the number of stops), \(K\) (the number of buses) and \(P\) (the maximum allowed gap in km for consecutive stops in a bus route).

outputFormat

Output one integer – the number of valid bus route schemes modulo \(30031\).

sample

4 2 2

1