У Поликарпа есть три целых числа 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
