题目描述

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

4 3 2

6

10000 100 60

20640995

提示

【样例 $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$
$10\sim 20$		$\le m$