e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Dynamic Programming - Linear

Лампіони

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

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

Вхідні дані

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

Вихідні дані

Кількість способів увімкнути освітлення дороги щоб вона була безпечною.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3 3
Вихідні дані #1
7
Автор Сандро Барнабишвили