[Hnoi2010]Bus 公交线路

小 Z 所在的城市有 $N$ 个公交车站，它们排列在一条长为 $(N-1)\ \mathrm{km}$ 的直线上，从左到右依次编号为 $1$ 到 $N$。任意两个编号相邻的公交车站之间的距离均为 $1\ \mathrm{km}$。

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

• 共有 $K$ 辆公交车，编号为 $1$ 到 $K$ 的车站作为始发站，编号为 $N-K+1$ 到 $N$ 的车站作为终点站。
• 每个车站必须被一辆且仅一辆公交车经过，始发站和终点站也视为被经过。
• 公交车只能从编号较小的车站驶向编号较大的车站。
• 同一辆公交车依次经过的两个车站之间的距离不得超过 $P\ \mathrm{km}$。

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

输入格式

输入仅一行，包含三个正整数 $N$、$K$、$P$，分别表示公交车站数、公交车数以及同一辆公交车依次经过的两个车站之间的距离限制。

输出格式

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

样例输入

10 3 3

样例输出

1

样例解释

样例中唯一的可行方案为：

• 第一辆公交车依次经过车站 $(1,4,7,10)$；
• 第二辆公交车依次经过车站 $(2,5,8)$；
• 第三辆公交车依次经过车站 $(3,6,9)$。

数据范围

• $N\le 10^9$；
• $1<P\le 10$；
• $K<N$；
• $1<K\le P$；
• $K\le 8$。

来源与许可

本题为 HNOI 2010 试题「Bus 公交线路」，题面与测试数据整理自 BZOJ。

样例 1

输入

10 3 3

输出

1