EduBrick

E. Пути в сетке

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

Из левого верхнего угла доски n×mn \times m надо попасть в правый нижний, разрешены ходы вправо и вниз. Сколько существует маршрутов?

Динамикой это считается за O(nm)O(nm), но при n,mn, m до 10510^5 такая таблица не поместится ни в память, ни в лимит. Комбинаторика даёт ответ одним коэффициентом.

Формат ввода

Одна строка содержит числа nn и mm (1≤n,m≤1051 \le n, m \le 10^5).

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

Одно число — количество маршрутов по модулю 109+710^9 + 7.

Примеры

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