Как мне добавить это условие в это и сделать его оптимальным?

Ссылка на вопрос: http://codeforces.com/problemset/problem/431/C

Совсем недавно творческая ученица Леша провела лекцию по деревьям. После
лекция леша была вдохновлена ​​и придумала собственное дерево
который он назвал к-деревом.

K-дерево — это бесконечное корневое дерево, где:

• каждая вершина имеет ровно k детей;
• каждый край имеет некоторый вес;
• если мы посмотрим на ребра, идущие от некоторой вершины к ее дочерним элементам (точно
  k ребер), то их веса будут равны 1, 2, 3, …, k.

На рисунке ниже показана часть 3-х деревьев.

Как только Дима, хороший друг Леши, узнал о дереве, он
Сразу задумался: «Сколько дорожек общего веса n (сумма
все веса ребер в пути), начиная с
корень k-дерева, а также содержащий по крайней мере один край веса в
хотя бы д? ». Помогите Диме найти ответ на свой вопрос. По количеству
пути могут быть довольно большими, выведите его по модулю 1000000007 (10 ^ 9 + 7). (Открыто
ссылка на вопрос выше для картины упомянутого дерева)

вход
Одна строка содержит три целых числа через пробел: n, k и
d (1 ≤ n, k ≤ 100; 1 ≤ d ≤ k).

Выход
Выведите одно целое число — ответ на задачу по модулю
1000000007 (10 ^ 9 + 7).

Итак, я попытался разработать рекурсивное решение для того же. Тем не менее, я не могу добавить ограничение, чтобы убедиться, что край веса по крайней мере d должен присутствовать. Как я могу это сделать? Вот моя рекурсивная функция:

void calc(int present, int total,int k) // Here, present is initialised to 0.
// total is equal to n that is reqd.
// k is the value in the question
{
if (total == present)
{
ans++;
ans = ans%val;
return;
}
else
{
for ( int i = 1; i <= k; i++ )
{
if (present+i <= total)
return calc(present+i,total,k);
}
}
}