k-树

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

$k$-树是一棵无限有根树，满足以下性质：

• 每个顶点恰有 $k$ 个子节点；
• 每条边都有权值；
• 从任意顶点连向它的 $k$ 个子节点的边权分别为 $1,2,\ldots,k$。

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

求从根出发、路径权值之和恰为 $n$，且路径上至少包含一条权值不小于 $d$ 的边的路径数。答案对 $10^9+7$ 取模。

输入格式

一行包含三个整数 $n,k,d$。

输出格式

输出一个整数，表示满足条件的路径数对 $10^9+7$ 取模后的结果。

样例输入 1

3 3 2

样例输出 1

3

样例输入 2

3 3 3

样例输出 2

1

样例输入 3

4 3 2

样例输出 3

6

样例输入 4

4 5 2

样例输出 4

7

数据范围

对于全部数据，$1\le n,k\le 100$，$1\le d\le k$。