Одного дня 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\le100\,000$.
• $1\le K\le N$.

Підзадачі

Є 4 підзадачі. Бали та додаткові обмеження кожної підзадачі наведено нижче.

Підзадача 1 [4 бали]

• $N\le10$.

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

• $N\le300$.

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

• $N\le3\,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