最近,一位富有创造力的学生 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