색칠 공부 (큰 버전)

정$n$각형의 꼭짓점을 $k$개의 색으로 칠한다. 쓰지 않는 색이 있어도 되고, 한 색을 여러 꼭짓점에 써도 된다.

꼭짓점에 시계 방향으로 $0$번부터 $n-1$번까지 번호를 붙이면, 돌리기는 꼭짓점 $i$를 꼭짓점 $i+j$로 보내는 대응이고 뒤집기는 꼭짓점 $i$를 꼭짓점 $j-i$로 보내는 대응이다. 꼭짓점 번호는 모두 $n$으로 나눈 나머지로 본다.

두 칠하기에 다음 세 연산을 유한 번 적용해서 서로 같아지면, 두 칠하기를 같은 한 가지 경우로 센다.

• 다각형을 돌린다.
• 다각형을 뒤집는다.
• 서로 다른 두 색 $X$와 $Y$를 골라 $X$색인 꼭짓점을 모두 $Y$색으로 바꾸고 $Y$색인 꼭짓점을 모두 $X$색으로 바꾼다. $X$색인 꼭짓점이 없거나 $Y$색인 꼭짓점이 없어도 이 연산을 쓸 수 있다.

서로 다른 칠하기가 몇 가지인지 구하라.

첫째 줄에 $n$과 $k$가 공백 하나로 구분되어 주어진다.

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

서로 다른 칠하기의 개수를 1,000,000,007로 나눈 나머지를 한 줄에 출력한다.