e-olymp
Соревнования

January 19,20. One-dimentional Dynamic Programming

Лампионы

На дороге необходимо установить ночное освещение. Рабочая бригада уже установила n лампионов, осталось только их включить. Для экономии средств было решено включить столько лампионов, чтобы ездить по этой дороге стало безопасно. Безопасной дорога считается только тогда, когда ни на одном из участков дороги не встречается k соседних выключенных лампиона.

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

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

Два целых числа n (1n106) и k (1kn).

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

Количество способов включить освещение дороги чтобы она была безопасной.

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
3 3
Выходные данные #1
7
Автор Сандро Барнабишвили