B. Подсчет размещений
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Поликарпа есть три целых числа N, K и D. Он хочет посчитать число различных размещений из чисел 1, 2, ... , N по K по модулю 1000000007. Размещение — это некоторый набор чисел. Размещения являются одинаковыми, если они содержат одни и те же числа в одном и том же порядке.

Все числа в размещении должны образовывать неубывающую последовательность, при этом каждое следующее число должно отличаться от предыдущего не более, чем на D.

Помогите Поликарпу решить задачу.

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

Даны три целых числа: N, K, D. 1 ≤ N ≤ 1000, 1 ≤ K, D ≤ N. Числа разделены пробелами.

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

Вывести число различных размещений по модулю 1000000007.

Примеры
Входные данные
5 3 1
Выходные данные
3
Входные данные
5 3 2
Выходные данные
8
Входные данные
1000 500 1000
Выходные данные
159835829