Problem Description

docriz is taking an exam, and he encounters a strange multiple-choice question: there are $n$ options in total, and only one option is correct. He cannot solve it at all, so he can only guess.

Guessing this question consists of $n - 2$ rounds. Before round $1$ starts, docriz randomly guesses one of the $n$ options. Then, in each following round, the process is as follows: first, nocriz comes to help him eliminate one option. Since nocriz knows the answer in advance, he will randomly delete one option among the current options, excluding the correct option and the option that docriz is currently choosing. After that, docriz may choose whether to switch his guessed option. If he switches, he randomly switches to any option other than the one he is currently choosing.

During these $n - 2$ rounds, due to a mysterious agreement with nocriz, docriz must switch options exactly $k$ times. He wants to know how to switch so that the probability of guessing correctly is maximized, and you should output this probability. For convenience, you need to output the result of this probability in fractional form modulo $10^9 + 7$.

Input Format

One line with two integers $n, k$, with the meanings as described above.

Output Format

One line with one number, representing the answer.

3 1

666666672

3 0

333333336

4 1

750000006

4 2

625000005

100000 99998

439903656

Hint

Samples $1$ to $4$ are $\frac{2}{3}, \frac{1}{3}, \frac{3}{4}, \frac{5}{8}$, respectively.

For $30\%$ of the testdata, it is guaranteed that $5 \leq n \leq 10$.

For another $5\%$ of the testdata, it is guaranteed that $k = 0$.

For another $10\%$ of the testdata, it is guaranteed that $k = 1$.

For another $10\%$ of the testdata, it is guaranteed that $k = n - 2$.

For another $5\%$ of the testdata, it is guaranteed that $n \leq 10^2$.

For another $10\%$ of the testdata, it is guaranteed that $n \leq 10^3$.

For $100\%$ of the testdata, it is guaranteed that $5 \leq n \leq 10^5, 0 \leq k \leq n - 2$.

Translated by ChatGPT 5