题目描述

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

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

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

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

输入格式

仅一行包含三个正整数 $n, k, p$，分别表示公交车站数，公交车数，相邻站台的距离限制。

输出格式

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

10 3 3

1

样例说明 1

可行方案如下：$(1,4,7,10), (2,5,8), (3,6,9)$。

5 2 3

3

样例说明 2

可行方案如下：$(1,3,5), (2,4)\quad(1,3,4), (2,5)\quad(1,4), (2,3,5)$。

10 2 4

81

数据规模与约定

对于 $100\%$ 的数据，$3 \leq n \leq 10^9$，$1 < p \leq 10$，$1 \leq k < \min(n-1,p,8)$。