Совсем недавно креативный студент Леша прослушал лекцию по деревьям. После лекции Леша был вдохновлен и придумал собственное дерево, которое он назвал k-дерево.
k-дерево — это бесконечное корневое дерево, в котором:
- каждая вершина имеет ровно k сыновей;
- каждое ребро имеет некоторый вес;
- если рассмотреть ребра из некоторой вершины в ее сыновей (ровно k ребер), то их веса будут равны 1, 2, 3, ..., k.
На рисунке ниже представлен фрагмент 3-дерева.
Как только Дима, хороший друг Леши, узнал про это дерево, его сразу заинтересовал вопрос: «Сколько существует путей с суммарным весом ребер равным
n, которые начинаются в корне
k-дерева, а также содержат хотя бы одно ребро веса не меньше
d?».
Помогите Диме узнать ответ на его вопрос. Так как количество путей может быть достаточно большим, найдите остаток от деления ответа на 1000000007 (109 + 7).