The workshop needs a presenting sequence. There are ~n~ distinct people, and you must choose exactly ~k~ of them to present. Order matters: the person in slot ~1~ speaks first, the person in slot ~2~ speaks second, and so on. The same set of ~k~ people in a different speaking order counts as a different sequence.

Count the number of possible presenting sequences. Since the answer can be large, output it modulo ~10^9 + 7~.

Input

A single line containing two integers ~n~ and ~k~.

Output

Print one integer: the number of presenting sequences of length ~k~, modulo ~10^9 + 7~.

Constraints

• ~0 \le n, k \le 10^6~

Example 1

Input

5 2

Output

20

Explanation

There are ~5~ choices for slot ~1~ and then ~4~ remaining choices for slot ~2~, so there are ~5 \times 4 = 20~ ordered sequences. Alice then Bob is different from Bob then Alice.

Example 2

Input

4 0

Output

1

Explanation

There is exactly one empty presenting sequence.

Example 3

Input

3 5

Output

0

Explanation

You cannot fill ~5~ slots using only ~3~ people.