#P3204. [HNOI2010] 公交线路
[HNOI2010] 公交线路
题目描述
小 Z 所在的城市有 个公交车站,排列在一条长 的直线上,从左到右依次编号为 到 ,相邻公交车站间的距离均为 。作为公交车线路的规划者,小 Z 调查了市民的需求,决定按下述规则设计线路:
- 设共 辆公交车,则 到 号站作为始发站, 到 号台作为终点站。
- 每个车站必须被一辆且仅一辆公交车经过(始发站和终点站也算被经过)。
- 公交车只能从编号较小的站台驶往编号较大的站台。
- 一辆公交车经过的相邻两个站台间距离不得超过 。
在最终设计线路之前,小 Z 想知道有多少种满足要求的方案。由于答案可能很大,你只需求出答案对 取模的结果。
输入格式
仅一行包含三个正整数 、、,分别表示公交车站数、公交车数、相邻站台的距离限制。
输出格式
仅包含一个整数,表示满足要求的方案数对 取模的结果。
10 3 3
1
5 2 3
3
10 2 4
81
提示
【样例说明】
样例一的可行方案如下:,,。
样例二的可行方案如下:,,,。
对于 的数据,,,,。