k-Дерево

Нещодавно Барт відвідав лекцію про дерева, яка його дуже надихнула. Після цього він придумав власний тип дерева, який назвав k-деревом.

k-дерево — це нескінченне кореневе дерево, яке має такі властивості:

• кожна вершина має рівно k нащадків;

• кожне ребро має певну вагу;

• якщо розглянути ребра, що ведуть від будь-якої вершини до її нащадків (рівно k ребер), то їх ваги становлять 1, 2, 3, ..., k.

На малюнку нижче зображена частина 3-дерева.

Як тільки Мілгауз, добрий друг Барта, дізнався про це дерево, він одразу зацікавився: "Скільки існує шляхів із загальною вагою n (сума всіх ваг на ребрах шляху), які починаються в корені k-дерева і містять принаймні одне ребро з вагою не менше d?".

Допоможіть Мілгаузу знайти відповідь на це питання. Оскільки кількість шляхів може бути дуже великою, виведіть її за модулем 1000000007 (10^9 + 7).

Вхідні дані

В одному рядку містяться три цілі числа: n, k і d (1 ≤ n, k ≤ 100, 1 ≤ d ≤ k).

Вихідні дані

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

Приклади