文件输入输出

本题采用文件输入输出。

• 输入文件：rabbit.in
• 输出文件：rabbit.out

题目描述

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

它每次跳跃可以选择跳 $1,2,\ldots,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 3 2

样例输出 1

3

样例说明 1

合格方案共有 $3$ 种：2,1、1,2、3。

样例输入 2

4 3 2

样例输出 2

6

样例输入 3

10000 100 60

样例输出 3

20640995

数据范围

对于所有测试数据：

• $1\le n\le 100000$；
• $1\le m\le 100$；
• $1\le k\le m$。