Write a program to count the number of permutations of {1, …, n} with exactly k cycles, where 1 ≤ k ≤ n.

For instance, of the six permutations of {1, 2, 3}, we have:

- two with one cycle, which are: (2, 3, 1) and (3, 1, 2).
- three with two cycles, which are: (2, 1, 3), (1, 3, 2) and (3, 2, 1).
- one with three cycles, which is: (1, 2, 3).

Input

Input consists of several cases, each with n and k, such that 1 ≤ k ≤ n ≤ 1000.

Output

For every case, count the number of permutations of {1, …, n} with k cycles.
As the result can be very large, make the computations modulo 10^{8} + 7.

Observation

Let c be the number of cases.
The expected solution has total cost O(1000^{2} + c).
You can get up to 80 points with test cases where n ≤ 100,
with a solution with cost O(100^{3} + c).

Public test cases

**Input**

3 1 3 2 3 3 4 1 4 2 4 3 4 4 10 2 20 10 100 50

**Output**

2 3 1 6 11 6 1 1026576 28767655 68128793

Information

- Author
- Enric Rodríguez
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++