Лампіони
Лампіони
На дорозі необхідно встановити нічне освітлення. Робоча бригада вже встановила n лампіонів, залишилось лише їх увімкнути. Для економії коштів було вирішено вмикати стільки лампіонів, щоб їздити по цій дорозі стало безпечно. Безпечною дорога вважається лише тоді, коли ні на одній з ділянок дороги не зустрічається k сусідніх вимкнених лампіонів.
Ваша задача вияснити, скількома способами можна увімкнути освітлення дороги так, щоб їздити по ній було безпечно. Два варіанти освітлення вважаються різними, якщо знайдеться хоча б один лампіон, який у першому варіанті був увімкненим, а у другому вимкненим, або навпаки. Оскільки відповідь може бути дуже великою, виведіть відповідь за модулем 10^9
+ 7.
Вхідні дані
Два цілих числа n (1 ≤ n ≤ 10^6
) та k (1 ≤ k ≤ n).
Вихідні дані
Кількість способів увімкнути освітлення дороги щоб вона була безпечною.
Приклад
3 3
7