Description

Now Person B has a cycle consisting of $n$ regions. Person B wants to dye these $n$ regions using $m$ colors.

Person B does not want there to exist $m$ consecutive regions among these $n$ regions such that all $m$ colors appear exactly once. In other words, for any $m$ consecutive regions, it must not be the case that all $m$ colors appear exactly.

If two colorings can be made exactly the same by rotation, then we consider them essentially the same.

However, if two colorings need to be made exactly the same by reflection (flipping), we do not consider them essentially the same.

For example, if $n=4,m=4$:

We consider $1,2,3,4$ and $3,4,1,2$ to be essentially the same coloring.

We consider $1,2,3,4$ and $4,3,2,1$ to be essentially different colorings.

We consider $1,2,1,2$ and $2,1,2,1$ to be essentially the same coloring.

Person B wants to know the number of essentially different colorings that satisfy the condition. Output the answer modulo $10^9+7$.

Input Format

Read input from standard input.

The input consists of one line containing two integers $n,m$, where $n$ denotes the length of the cycle and $m$ denotes the number of colors.

Output Format

Write output to standard output.

Output one line with one integer, representing the result of the answer modulo $10^9+7$.

6 3

44

120 6

615888898

Hint

For $100\%$ of the test points, $1\le n\le 10^9,2\le m\le7$. | Test point ID $\operatorname*{Id}$ | $n$ | $m$ | | :----------: | :----------: | :----------: | | 1~2 | $n\le10$ | $m=\operatorname*{Id}+2$ | | 3~8 | $n\le 10^5,n$ is prime | $m=\operatorname*{Id}-1$ | | 9~14 | $n$ is prime | $m=\operatorname*{Id}-7$ | | 15~19 | No special constraints | $m=\operatorname*{Id}-13$ | | 20 | $n=635,643,090$ | $m=7$ |

Translated by ChatGPT 5