Однажды JOI-kun раздобыл машину времени. Он решил отправиться в Японию IX века. Там он встретил Kukai, одного из самых известных священнослужителей Японии того времени. Священнослужитель хотел разработать новый способ духовной практики.

Его практика устроена следующим образом:

• Kukai читает сутру из $N$ предложений. Предложения упорядочены, и читать их нужно по порядку.
• Каждому предложению приписано одно целое число от $1$ до $N$ включительно. Никаким двум различным предложениям не приписано одно и то же число.
• Предложение с числом $i$ ($1 \le i \le N$) он должен читать в $i$-й из $N$ равных промежутков времени, на которые разделён день. Каждое предложение настолько короткое, что он всегда успевает прочитать его за один промежуток.

Kukai хочет прочитать всю сутру как можно быстрее. Однако количество дней, необходимое для завершения чтения, зависит от чисел, приписанных предложениям сутры. Kukai попросил JOI-kun подсчитать количество способов приписать предложениям числа так, чтобы при оптимальном чтении Kukai потребовалось ровно $K$ дней для прочтения всей сутры.

Задание

По заданным количеству предложений $N$ и целому числу $K$ вычислите количество способов приписать предложениям числа так, чтобы при оптимальном чтении Kukai потребовалось ровно $K$ дней для прочтения всей сутры, по модулю $1\,000\,000\,007$.

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

Считайте следующие данные из стандартного ввода.

• В первой строке входных данных содержатся $N$ и $K$, разделённые одним пробелом.

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

Выведите количество способов приписать предложениям числа так, чтобы при оптимальном чтении Kukai потребовалось ровно $K$ дней для прочтения всей сутры, по модулю $1\,000\,000\,007$.

Ограничения

Все входные данные удовлетворяют следующим условиям.

• $1 \le N \le 100\,000$.
• $1 \le K \le N$.

Подзадачи

Всего есть 4 подзадачи. Баллы и дополнительные ограничения для каждой подзадачи приведены ниже.

Подзадача 1 [4 балла]

• $N \le 10$.

Подзадача 2 [20 баллов]

• $N \le 300$.

Подзадача 3 [25 баллов]

• $N \le 3\,000$.

Подзадача 4 [51 балл]

Дополнительных ограничений нет.

Примеры

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

3 2

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

4

Примечание

Есть 4 способа приписать предложениям числа так, чтобы чтение заняло у него 2 дня.

• Первому предложению приписано число $1$, следующему — $3$, а последнему — $2$. Первые два предложения (с числами $1$ и $3$ соответственно) он читает в первый день, а последнее предложение (с числом $2$) — во второй день.
• Первому предложению приписано число $2$, следующему — $1$, а последнему — $3$.
• Первому предложению приписано число $2$, следующему — $3$, а последнему — $1$.
• Первому предложению приписано число $3$, следующему — $1$, а последнему — $2$.

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

10 5

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

1310354