该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

小兔子爬楼梯

题目描述

森林学校里有一座 $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$ 取模）。

样例

3 3 2

3

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

4 3 2

6

10000 100 60

20640995

数据范围

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