C. k-дерево
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

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

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

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

На рисунке ниже представлен фрагмент 3-дерева.

Как только Дима, хороший друг Леши, узнал про это дерево, его сразу заинтересовал вопрос: «Сколько существует путей с суммарным весом ребер равным n, которые начинаются в корне k-дерева, а также содержат хотя бы одно ребро веса не меньше d?».

Помогите Диме узнать ответ на его вопрос. Так как количество путей может быть достаточно большим, найдите остаток от деления ответа на 1000000007 (109 + 7).

Входные данные

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

Выходные данные

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

Примеры
Входные данные
3 3 2
Выходные данные
3
Входные данные
3 3 3
Выходные данные
1
Входные данные
4 3 2
Выходные данные
6
Входные данные
4 5 2
Выходные данные
7