题目描述

不久之前，一位有创意的学生 Lesha 上了一堂有关树的课程。课堂结束后，Lesha 受到启发，想出了自己的一种树，这种树他称为 $k$-树。

$k$-树是一种无限的有根树，具有以下特性：

• 每个顶点恰好有 $k$ 个子节点；
• 每条边都有一个权值；
• 对于从某个顶点出发连向其各个子节点的 $k$ 条边，它们的权值分别为 $1,2,3,\ldots,k$。

下图展示了 $3$-树的一部分。

当 Lesha 的好朋友 Dima 得知这种树后，马上产生了疑问：“从 $k$-树的根出发，路径权值之和为 $n$，且路径上至少包含一条权值不少于 $d$ 的边，这样的路径有多少条？”请帮助 Dima 求出答案。由于方案数可能非常大，请输出对 $1000000007$（$10^9+7$）取模后的结果。

输入格式

一行包含三个用空格分隔的整数 $n$、$k$ 和 $d$（$1 \leq n, k \leq 100$；$1 \leq d \leq k$）。

输出格式

输出一个整数，表示满足条件的路径数对 $1000000007$ 取模的结果。

说明/提示

由 ChatGPT 5 翻译

样例

3 3 2

3

3 3 3

1

4 3 2

6

4 5 2

7