시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.6 초 256 MB 1 1 1 100.000%

문제

One day, JOI-kun got a time machine. He decided to go to Japan in the 9th century. He met Kukai, one of the most famous priests in Japan at the moment. The priest wanted to develop the new way of training.

His training is done in the following way:

  • Kukai reads the sutra with N sentences. These sentences are ordered, and he has to read in order.
  • Each sentence has one integer between 1 and N, inclusive. No two different sentences have the same number.
  • He has to read the sentence with the integer i (1 ≤ i ≤ N) in the i-th period among the N equally divided time periods in a day. Each sentence is so short that it is always possible for him to read a sentence in a period.

Kukai wants to read the whole sutra as fast as possible. However, how many days it takes for him to finish depends on the integers on the sentences in the sutra. JOI-kun was asked by Kukai to count the number of possible ways of integers on the sentences that takes Kukai exactly K days to finish reading, if he reads optimally.

Given the number of sentences N and an integer K, calculate the number of possible ways of integers on the sentences that takes Kukai exactly K days to finish reading, if he reads optimally, modulo 1 000 000 007.

입력

Read the following data from the standard input.

  • The first line of input contains N and K, separated by a single space.

출력

Print the number of possible ways of integers on the sentences that takes Kukai exactly K days to finish reading, if he reads optimally, modulo 1 000 000 007.

제한

  • 1 ≤ N ≤ 100 000.
  • 1 ≤ K ≤ N.

예제 입력 1

3 2

예제 출력 1

4

There are 4 possible ways of integers on the sentences that takes him 2 days to finish reading.

  • The first sentence has 1, the next sentence has 3 and the last sentence has 2. He reads the first two sentences (numbered 1 and 3 each) on the first day, and the last sentence (numbered 2) on the second day.
  • The first sentence has 2, the next sentence has 1 and the last sentence has 3.
  • The first sentence has 2, the next sentence has 3 and the last sentence has 1.
  • The first sentence has 3, the next sentence has 1 and the last sentence has 2.

예제 입력 2

10 5

예제 출력 2

1310354