Problem Description

In the city where Xiao Z lives, there are N bus stops arranged in a straight line over a length of (N-1) km, numbered from 1 to N from left to right, with each adjacent bus stop being 1 km apart. As the planner of the bus routes, Xiao Z has investigated the needs of the citizens and decided to design the routes according to the following rules:

1. There are K buses in total, with stops 1 to K serving as the starting points and stops N-K+1 to N as the ending points.
2. Each stop must be passed by exactly one bus (including starting and ending stops).
3. Buses can only travel from stops with a smaller number to stops with a larger number.
4. The distance between any two consecutive stops passed by a single bus must not exceed P km.

Before finalizing the route design, Xiao Z wants to know how many valid route plans exist. Since the answer could be very large, you only need to output the result modulo 30031.

Input Format

A single line containing three positive integers N, K, and P, representing the number of bus stops, the number of buses, and the distance limit between adjacent stops, respectively. N <= 10^9, 1 < P <= 10, K < N, 1 < K <= P.

Output Format

A single integer representing the number of valid route plans modulo 30031.

Sample Input and Output

Input Sample #1

10 3 3

Output Sample #1

1

Input Sample #2

5 2 3

Output Sample #2

3

Input Sample #3

10 2 4

Output Sample #3

81

Notes

For the first sample, the feasible plans are: (1,4,7,10), (2,5,8), (3,6,9).

For the second sample, the feasible plans are: (1,3,5), (2,4); (1,3,4), (2,5); (1,4), (2,3,5).

P <= 10, K <= 8.

见题面 Input 部分

见题面 Output 部分