The BASF company was once the world's largest chemical enterprise. They produced dyes in a rich variety of colors, including Tsinghua Purple, Soul Yellow, Forgive Green, Conference Blue, Advanced Black, Peking University Red, and Album White.

Now, B has a ring consisting of $n$ regions, and B wants to color these $n$ regions using $m$ colors.

B does not want any $m$ consecutive regions in the $n$ regions to contain all $m$ colors. In other words, for any $m$ consecutive regions, it is not allowed for all $m$ colors to appear exactly once.

If two coloring schemes can become identical through rotation, we consider them essentially the same. However, if two schemes require reflection to become identical, 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 scheme. We consider $1, 2, 3, 4$ and $4, 3, 2, 1$ to be essentially different schemes. We consider $1, 2, 1, 2$ and $2, 1, 2, 1$ to be essentially the same scheme.

B wants to know the number of essentially different schemes that satisfy the condition, modulo $1\,000\,000\,007$.

Input

The input consists of a single line containing two integers $n$ and $m$.

Here, $n$ represents the length of the ring, and $m$ represents the number of colors.

Output

Output a single integer representing the answer modulo $1\,000\,000\,007$.

Examples

Input 1

6 3

Output 1

44

Input 2

120 6

Output 2

615888898

Subtasks

• For $100\%$ of the test cases, $1 \leq n \leq 1\,000\,000\,000, 2 \leq m \leq 7$.