Description

saruka owns a big castle. There are $n$ rooms in the castle, and each room has a number $p_i$ written on it. One day, saruka invited his friends LYL and MagHSK to play in the castle. They agreed that if someone is currently standing in room $i$, then on the next step they must go to room $p_i$, and on the following step to room $p_{p_i}$.

To make it more interesting, saruka decides to rewrite each $p_i$ to satisfy the following:

• If you start from any room numbered from $1 \sim k$ and follow the rule, you must be able to return to room $1$. In particular, if you start from room $1$, you must return to room $1$ as well (you must take at least one step; if $p_1 = 1$, moving from $1$ to $1$ is also considered valid).

• If you start from any room with a number greater than $k$ and follow the rule, you must never reach room $1$.

saruka wants to know how many assignments of $p_i$ satisfy the requirements. Output the answer modulo $10 ^ 9 + 7$.

Input Format

A single line containing two integers $n, k$, as described.

Output Format

Output a single integer, the number of valid assignments. The answer is taken modulo $10 ^ 9 + 7$.

5 2

54

7 4

1728

Hint

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

Translated by ChatGPT 5