In the city CCO, there are ~N~ bus stations in a line, which are numbered from left to right as station ~1~ to station ~N~. The distance between two adjacent stations is exactly ~1~ km. Bruce is planning the bus routes. He needs to guarantee that the designed bus routes satisfy the following rules.

1. Suppose that there are ~K~ buses in total. The stations ~1~ to ~K~ must be the initial stations, while the stations ~N-K+1~ to ~N~ must be the terminal stations.
2. For each station (including initial station and terminal station), exactly one bus stops at that station.
3. Every bus only drives from left to right.
4. For each bus, the two adjacent stops cannot be greater than ~P~ km.

Given the above rules, Bruce wants to know the total number of ways to design the bus routes. Since the number may be large, please compute it modulo ~30\,031~.

Input Specification

One line input, ~N~, ~K~, ~P~, represent the number of bus stations, the number of buses, and the distance limit between two adjacent bus stops, respectively. (~N \le 10^9~, ~1 < P \le 10~, ~K < N~, ~1 < K \le P~).

Output Specification

One integer, the number of ways to design the bus routes mod ~30\,031~.

Sample Input 1

10 3 3

Sample Output 1

1

Sample Input 2

5 2 3

Sample Output 2

3

Sample Explanation

In sample input 1, there is only ~1~ valid plan ~\{(1,4,7,10),(2,5,8),(3,6,9)\}~.

In sample input 2, there are ~3~ valid plans ~\{(1,3,5),(2,4)\}~, ~\{(1,3,4),(2,5)\}~, ~\{(1,4),(2,3,5)\}~.