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

题目背景

一台机器拥有 $k$ 个能量槽，每个能量槽都必须设置一个正整数能级。总能量需要恰好分配为 $n$，同时满足机器稳定运行的约束条件。

题目描述

设 $k$ 个能量槽的能级依次为 $a_1, a_2, \dots, a_k$，需要满足：

1. 每个能级均为正整数；
2. 能级单调不下降：$a_1 \le a_2 \le \dots \le a_k$；
3. 相邻能级之差不超过 $d$：$0 \le a_{i+1} - a_i \le d$；
4. 所有能级之和恰好等于 $n$。

两种分配方案不同，当且仅当存在某个能量槽的能级不同。

请输出合法分配方案数对 $1\,000\,000\,007$ 取模后的结果。

输入格式

输入一行三个整数 $n, k, d$。

输出格式

输出一行一个整数，表示方案数对 $1\,000\,000\,007$ 取模后的结果。

样例输入 #1

8 3 2

样例输出 #1

3

样例说明 #1

合法方案为 $(1, 3, 4)$、$(2, 2, 4)$、$(2, 3, 3)$，共 $3$ 种。其中 $(1, 1, 6)$ 的相邻差为 $5$，$(1, 2, 5)$ 的相邻差为 $3$，均不满足相邻差不超过 $2$ 的条件。

样例输入 #2

5 2 100

样例输出 #2

2

样例说明 #2

合法方案为 $(1, 4)$、$(2, 3)$，共 $2$ 种。由于能级必须单调不下降，$(3, 2)$ 不计入。

提示

【数据范围】

对于全部测试数据，$1 \le n \le 2000$，$1 \le k \le 2000$，$0 \le d \le 2000$。

各子任务如下：