B4564 [山东省小学组体验营 2026] 小兔子爬楼梯

森林学校里有一座 $n$ 级的台阶，小兔子要跳上去。 它每一次跳跃，可以选择跳 $1$ 级、$2$ 级、……、$m$ 级（每次跳的级数必须是整数，且在 $1$ 到 $m$ 之间）。 小兔子体力无限，他想尝试各种跳跃方案（跳完 $n$ 级台阶的跳跃序列）。 但是，小兔子的老师说：“每一种跳跃方案中，至少要有一次跳的级数不少于 $k$（$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$ 种：$2,1$；$1,2$；$3$。 ### 【数据范围】 所有数据满足：$1\le n\le 100000$，$1\le m\le 100$，$1\le k\le m$。 | 测试点编号 | $m$ | $k$ | 特殊性质 | |:-:|:-:|:-:|:-:| | $1\sim 3$ | $=2$ | $=1$ | 无 | | $4\sim 9$ | $\le 100$ | $=1$ | 无 | | $10\sim 20$ | $\le 100$ | $\le m$ | 无 |