Problem Description

小兔子爬楼梯（rabbit）

【题目描述】

森林学校里有一座 $n$ 级的台阶，小兔子要跳上去。

它每一次跳跃，可以选择跳 $1$ 级、$2$ 级、...... $m$ 级（每次跳的级数必须是整数，且在 $1$ 到 $m$ 之间）。

小兔子体力无限，他想尝试各种跳跃方案（跳完 $n$ 级台阶的跳跃序列）。

但是，小兔子的老师说："每一种跳跃方案中，至少要有一次跳的级数不少于 $k$（$\le m$）级（称为"逆天一跳"），才算一种合格的跳跃方案"。

比如：$n=7, m=5, k=3$，在以下跳跃方案中：

• 跳跃序列：1,2,2,2 不是合格的跳跃方案；
• 跳跃序列：1,3,3 是合格的跳跃方案；
• 跳跃序列：1,4,2 与 1,5,1 都是合格的跳跃方案。

现在，小兔子想知道：一共有多少种不同的合格的跳跃方案，能恰好跳完 $n$ 级台阶。

注意：跳跃序列顺序不同算不同的跳跃方案。比如 1,1,5 与 1,5,1 是两种不同的跳跃方案。

因为合格的跳跃方案可能太多了，答案要对 $10^9+7$ 取模。

【输入格式】

一行三个整数：$n, m, k$。

【输出格式】

输出一个整数，表示符合条件的合格跳跃方案总数（对 $10^9+7$ 取模）。

【样例1输入】

3 3 2

【样例1输出】

3

【样例1说明】

合格的跳跃方案有 3 种：2,1；1,2；3。

【样例2输入】

4 3 2

【样例2输出】

6

【样例3输入】

10000 100 60

【样例3输出】

120640995

【数据范围】

所有数据满足：$1 \le n \le 100000$，$1 \le m \le 100$，$1 \le k \le m$。

测试点编号	$m$	$k$	特殊性质
1~3	$=2$	$=1$	无
4~9	$\le 100$
10~20		$\le m$

3 3 2

3

4 3 2

6

Source

2026年山东省信息学体验营