Лампионы

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

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

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

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

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

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

Примеры