There are $N$ bus stops in the city where Xiao Z lives, arranged in a straight line of length $N-1$ kilometers. They are numbered $1$ to $N$ from left to right, and the distance between adjacent bus stops is $1$ kilometer.

As a bus route planner, Xiao Z has surveyed the needs of the citizens and decided to design the routes according to the following rules:

1. Suppose there are $K$ buses in total. Then stations $1$ to $K$ serve as starting stations, and stations $N-K+1$ to $N$ serve as terminal stations.
2. Each station must be stopped at by exactly one bus (starting and terminal stations are also considered stops).
3. Buses can only travel from a station with a smaller number to a station with a larger number.
4. The distance between any two adjacent stops for a single bus must not exceed $P$ kilometers.

Note that "stopping at" means passing through and stopping; since passing through does not necessarily mean stopping, "stopping at" and "passing through" are two different concepts.

Before finalizing the routes, Xiao Z wants to know how many schemes satisfy these requirements. Since the answer may be very large, you only need to output the answer modulo $30031$.

Input

The input consists of a single line containing three space-separated positive integers $N, K, P$, representing the number of bus stops, the number of buses, and the maximum distance between adjacent stops for a bus, respectively.

It is guaranteed that $40\%$ of the data satisfies $N \le 1000$. For $100\%$ of the data, $1 < N < 10^9$, $1 < P \le 10$, $K < N$, and $1 < K \le P$.

Output

Output a single integer representing the number of valid schemes modulo $30031$.

Examples

Input 1

10 3 3

Output 1

1

Input 2

5 2 3

Output 2

3

Input 3

10 2 4

Output 3

81

Note

In Example 1, there is only $1$ valid scheme: $(1,4,7,10)$, $(2,5,8)$, $(3,6,9)$.

In Example 2, there are $3$ valid schemes: $(1,3,5)$, $(2,4)$; $(1,3,4)$, $(2,5)$ and $(1,4)$, $(2,3,5)$.