Problem Description

Saruka has a grand castle! The castle contains $n$ rooms, each labeled with a number $p_i$. One day, Saruka invited his friends LYL and MagHSK to play in the castle. They agreed that if someone is currently in room $i$, their next step would be to go to room $p_i$, and the step after that would be to room $p_{p_i}$.

To make the game more interesting, Saruka decided to rewrite the numbers $p_i$ for each room to satisfy the following conditions:

• If starting from any room numbered from $1$ to $k$, following the rules, one must be able to return to room $1$. Specifically, if starting from room $1$, one must also return to room $1$ (at least one step is required; if $p_1 = 1$, moving from room $1$ to room $1$ is also valid).

• If starting from a room numbered greater than $k$, following the rules, one must never reach room $1$.

Saruka wants to know how many ways there are to rewrite the numbers $p_i$ to meet these requirements, modulo $10^9 + 7$.

Input Format

A single line containing two numbers $n$ and $k$, as described in the problem.

Output Format

A single number representing the number of valid schemes, modulo $10^9 + 7$.

Sample Input and Output

Sample Input #1

5 2

Sample Output #1

54

Sample Input #2

7 4

Sample Output #2

1728

Notes/Hints

For $100\%$ of the data, $1 \le n \le 10^{18}, 1 \le k \le \min(n, 8)$.

见题面 Input 部分

见题面 Output 部分