EduBrick

F. Разложить на слагаемые

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

Сколькими способами можно представить число nn в виде суммы kk неотрицательных целых слагаемых, если слагаемые упорядочены?

Например, при n=3n = 3 и k=2k = 2 таких представлений четыре: 0+30+3, 1+21+2, 2+12+1, 3+03+0.

Приём, который это решает, называется «шарики и перегородки»: выложим nn шариков в ряд и расставим между ними k−1k - 1 перегородку. Каждая расстановка задаёт своё разложение.

Формат ввода

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

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

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

Примеры

ввод
3 2
вывод
4
ввод
10 3
вывод
66
Войдите, чтобы отправлять решения.