最近，一个有创造力的学生莱莎参加了一个有关树木的讲座。讲座结束后，莱莎受到启发后提出了他自己的树，称之为k树。
k-树是有无限根的树，其中：
l 每个顶点正好有k个子节点；
l 每条边都有权重；
l 如果我们观察从某个顶点到其子节点的边（正好k条边），那么他们的权重为1，2. 3. ..., k。
下图显示了3-树的一部分。
当莱莎的好朋友迪玛发现这棵树时，他立即想知道:“有多少条总权重为n(路径中所有边的权重之和)的路径，从k-树的根开始，并且至少包含一条权重为d的边？”。请帮助迪玛找到答案。由于路径的数量可能相当大，所以打印模100000007 (109+7)后的结果。