Coloring Practice (Large)

You color the vertices of a regular $n$-gon with $k$ colors. Some colors may go unused, and one color may be used on several vertices.

Number the vertices $0$ to $n-1$ clockwise. A rotation sends vertex $i$ to vertex $i+j$, and a reflection sends vertex $i$ to vertex $j-i$, where every vertex number is taken modulo $n$.

Two colorings count as one and the same case when a finite sequence of the following three operations turns one into the other.

• Rotate the polygon.
• Flip the polygon.
• Pick two different colors $X$ and $Y$, recolor every $X$ vertex to $Y$, and recolor every $Y$ vertex to $X$. This operation is allowed even when no vertex has color $X$, or no vertex has color $Y$.

Count the different colorings.

The first line contains $n$ and $k$, separated by one space.

$1 \le n \le 10^9$, $1 \le k \le 25$

Print the number of different colorings modulo 1,000,000,007 on one line.