eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Лампіони

Лампіони

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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

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

Вхідні дані

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

Вихідні дані

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

Приклад

Вхідні дані #1
3 3
Вихідні дані #1
7
Автор Сандро Барнабишвили