EduBrick

I. Никакие два рядом

2000 мс · 256 МБ · всё или ничего

В ряду стоит nn стульев. Надо выбрать kk из них так, чтобы никакие два выбранных не стояли рядом.

Сколькими способами это можно сделать?

Подсказка: мысленно уберите по одному стулу справа от каждого выбранного, кроме последнего. Запрет исчезнет, а число стульев уменьшится.

Формат ввода

Одна строка содержит числа nn и kk (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5, 0≤k≤n0 \le k \le n).

Формат вывода

Одно число — количество способов по модулю 109+710^9 + 7. Если способов нет, выведите 0.

Примеры

ввод
5 2
вывод
6
ввод
5 3
вывод
1
Войдите, чтобы отправлять решения.