小 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$，分别表示公交车站数、公交车数、一辆公交车经停的相邻两个车站间的最大距离。

输入的数据保证 $40\%$ 的数据满足 $N \le 1000$。$100\%$ 的数据满足 $1 < N < 10^9$，$1 < P \le 10$，$K < N$，$1 < K \le P$。

输出格式

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

样例数据

样例 1 输入

10 3 3

样例 1 输出

1

样例 2 输入

5 2 3

样例 2 输出

3

样例 3 输入

10 2 4

样例 3 输出

81

样例解释

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

样例二满足要求的方案有 $3$ 种，即：$(1,3,5)$，$(2,4)$；$(1,3,4)$，$(2,5)$ 和 $(1,4)$，$(2,3,5)$。