题目描述

本题中，我们定义一棵k叉树为一棵包含无穷个节点的树，其中：

• 每个节点都包含恰好 $k$ 个子节点；
• 树上的每条边都有一个权值；
• 对于树上的任意一个节点来说，它连上它的子节点的 $k$ 条边的权值恰好为 $1, 2, 3, \ldots, k$。

下图展示了一棵3叉树的一部分：

你需要求解的是：对于一棵k叉树，存在多少以根节点为起点的简单路径的权值为 $n$ 且至少包含一条权值 $\ge d$ 的边？（本题中，我们规定路径的权值为路径上所有边的权值之和）

注意：为了方便大家理解，再次声明一下你需要寻找的路径需同时满足如下条件：

• 路径的权值为 $n$
• 路径中至少包含一条权值 $\ge d$ 的边

由于方案数可能很大，所以你只需要输出答案除以 $1000000007$ 的余数即可。

输入格式

一行，三个整数 $n$、$k$ 和 $d$，两两之间以一个空格分隔（$1 \le n,k \le 1000, 1 \le d \le k$）。

输出格式

输出一个整数，表示权值为 $n$ 且至少包含一条权值 $\ge d$ 的边的路径数量除以 $1000000007$ 的余数。

3 3 2

3

3 3 3

1

4 3 2

6

4 5 2

7

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n,k \le 10$
• 对于 $60\%$ 的数据，$n,k \le 100$
• 对于 $100\%$ 的数据，$1 \le n,k \le 1000, 1 \le d \le k$