← 返回题目列表

Codeforces · 431/C

C. k 树

中文机器翻译题面 查看原题

最近,一位富有创造力的学生 Lesha 进行了一场关于树木的讲座。讲座结束后,Lesha 受到启发,提出了自己的树,他称之为 k 树。

k 树是无限根树,其中:

- 每个顶点恰好有 k 个子顶点;
- 每条边都有一定的权重;
- 如果我们查看从某个顶点到其子节点的边(正好 k 条边),那么它们的权重将等于 1, 2, 3, ..., k。

下图显示了三叉树的一部分。

帮助迪马找到问题的答案。由于路数可能相当大,因此打印它对 1000000007 (109 + 7) 取模。

输入

单行包含三个空格分隔的整数:n、k 和 d(1 ≤ n,k ≤ 100;1 ≤ d ≤ k)。

输出

打印一个整数——问题的答案以 1000000007 (109 + 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