3325. [HNOI 2010]公交线路

【题目描述】

小$ 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 ≤ 1,000 $。$ 100\% $的数据满足$ 1 < N < 1×10^9 $ ，$ 1 < P ≤ 10 $，$ K < N ， 1 < K ≤ 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) $。