Лампіони

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

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

Вхідні дані

Два цілі числа $n(1\le n\le 10^6)$ і $k(1\le k\le n)$.

Вихідні дані

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

Приклади