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

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

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

Два целых числа n (1 ≤ n ≤ 106) и k (1 ≤ k ≤ n).

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

Количество способов включить освещение дороги чтобы она была безопасной.