[HNOI2010] 公交线路

题目描述

小Z所在的城市有 $N$ 个公交车站，排列在一条长 $(N-1)$ km的直线上，从左到右依次编号为1到N，相邻公交车站间的距离均为1km。 作为公交车线路的规划者，小Z调查了市民的需求，决定按下述规则设计线路：

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

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

输入格式

仅一行包含三个正整数 $N, K, P$，分别表示公交车站数，公交车数，相邻站台的距离限制。$N\leq 10^9，1< P\leq 10，K< N，1< K\leq P$

输出格式

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

样例 #1

样例输入 #1

10 3 3

样例输出 #1

1

样例 #2

样例输入 #2

5 2 3

样例输出 #2

3

样例 #3

样例输入 #3

10 2 4

样例输出 #3

81

提示

【样例说明】

样例一的可行方案如下： (1,4,7,10)，(2,5,8)，(3,6,9)

样例二的可行方案如下： (1,3,5)，(2,4) (1,3,4)，(2,5) (1,4)，(2,3,5)

$P\leq 10 , K \leq 8$