时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小 Z 所在的城市有 N 个公交车站，排列在一条长为 N-1 公里的直线上，从左到右依次编号为 1 到 N，相邻公交车站间的距离均为 1 公里。

　　作为公交车线路的规划者，小 Z 调查了市民的需求，决定按以下规则设计线路：

　　1．设共有 K 辆公交车，则 1 到 K 号车站作为始发站， N-K+1 到 N 号车站作为终点站。
　　2．每个车站必须被一辆且仅一辆公交车经停（始发站和终点站也算被经停）。
　　3．公交车只能从编号较小的车站驶向编号较大的车站。
　　4．一辆公交车经停的相邻两个车站间的距离不得超过 P 公里。

　　注意“经停”是指经过并停车， 因经过不一定会停车，故经停与经过是两个不同的概念。

　　在最终确定线路之前，小 Z 想知道有多少种满足要求的方案。由于答案可能很大，你只需求出答案对 30031 取模的结果。

【输入格式】

　　　只有一行，其中包含用空格隔开的三个正整数N， K，P， 分别表示公交车站数，公交车数， 一辆公交车经停的相邻两个车站间的最大距离。

【输出格式】

　　仅包含一个整数，表示满足要求的方案数对 30031 取模的结果。

【输入输出样例1】

　Input

10 3 3

　Output

1

【输入输出样例2】

　Input

5 2 3

　Output

3

【输入输出样例3】

　Input

10 2 4

　Output

81

样例一满足要求的方案只有1种，即： (1,4,7,10)， (2,5,8)， (3,6,9)。<br>
　　样例二满足要求的方案有3种，即： (1,3,5)， (2,4)； (1,3,4)， (2,5)和(1,4)， (2,3,5)。

【数据限制】

　　40%的数据满足N≤1000。
100%的数据满足1<N<10^9， 1<P≤10， K<N， 1<K≤P
bzoj 2004

【来源】

　　Mr.he