Coloring Practice (Large)

Time limit3sMemory limit512 MB

Summary

Count colorings of a regular n-gon up to rotation, reflection, and arbitrary permutation of the k colors, modulo 1e9+7.

Level: Hard9 of 10
Topics: Combinatorics, Math, Number theory, Bit manipulation
Solved: No attempts yet

Problem

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.

Input

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

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

Output

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

Examples2

Example 1
Input
```
6 2
```
Expected output
```
8
```
Example 2
Input
```
3 3
```
Expected output
```
3
```