题号：NC20080
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
小Z所在的城市有N个公交车站，排列在一条长(N-1)km的直线上，从左到右依次编号为1到N，相邻公交车站间的距离均为1km。 作为公交车线路的规划者，小Z调查了市民的需求，决定按下述规则设计线路：
- 设共K辆公交车，则1到K号站作为始发站，N-K+1到N号台作为终点站。
- 每个车站必须被一辆且仅一辆公交车经过（始发站和终点站也算被经过）。
- 公交车只能从编号较小的站台驶往编号较大的站台。
- 一辆公交车经过的相邻两个站台间距离不得超过Pkm。
在最终设计线路之前，小Z想知道有多少种满足要求的方案。由于答案可能很大，你只需求出答案对30031取模的结果。
输入描述:
仅一行包含三个正整数N K P，分别表示公交车站数，公交车数，相邻站台的距离限制。
N ≤ 10^9，1 < P ≤ 10，K < N，1 < K ≤ P
输出描述:
仅包含一个整数，表示满足要求的方案数对30031取模的结果。
备注:
样例一的可行方案如下： (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)