问题 CD: E-k-Tree
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:9
解决:6
题目描述
最近有一个富有创造力的学生Lesha听了一个关于树的讲座。在听完讲座之后,Lesha受到了启发,并且他有一个关于k-tree(k叉树)的想法。
k-tree都是无根树,并且满足:
(1)每一个非叶子节点都有k个孩子节点;
(2)每一条边都有一个边权;
(3)每一个非叶子节点指向其k个孩子节点的k条边的权值分别为1,2,3,…,k。
当Lesha的好朋友Dima看到这种树时,Dima马上想到了一个问题:“有多少条从k-tree的根节点出发的路上的边权之和等于n,并且经过的这些边中至少有一条边的边权大于等于d呢?”
现在你需要帮助Dima解决这个问题。考虑到路径总数可能会非常大,所以只需输出路径总数 mod 1000000007 即可。(1000000007=10^9+7)
k-tree都是无根树,并且满足:
(1)每一个非叶子节点都有k个孩子节点;
(2)每一条边都有一个边权;
(3)每一个非叶子节点指向其k个孩子节点的k条边的权值分别为1,2,3,…,k。
当Lesha的好朋友Dima看到这种树时,Dima马上想到了一个问题:“有多少条从k-tree的根节点出发的路上的边权之和等于n,并且经过的这些边中至少有一条边的边权大于等于d呢?”
现在你需要帮助Dima解决这个问题。考虑到路径总数可能会非常大,所以只需输出路径总数 mod 1000000007 即可。(1000000007=10^9+7)
输入
在一行内输入3个整数,分别为n,k,d(1<=n,k<=100;1<=d<=k)。
输出
一个整数,整数为不同路径的总数对1000000007取余(1e9+7)。
样例输入 复制
3 3 2
样例输出 复制
3