12748번 - 색칠 공부 (Large)

종원이는 정n각형의 꼭짓점을 k개의 색으로 칠하려고 한다. 이때 정다각형을 돌려서 같은 경우나, 뒤집어서 같은 경우, 또는 임의의 다른 두 색 X, Y를 선택해 X색의 점들을 모두 Y색으로 바꾸고 Y색의 점들을 모두 X색으로 바꾸는 과정을 유한 번 반복해서 (X색의 점들이나 Y색의 점들이 없었을 수 있음) 돌리거나 뒤집을 때 같은 모양이 되는 경우를 모두 같은 한 가지의 경우로 생각한다.

숙제를 새벽까지 하느라 머리가 복잡해진 종원이는 안타깝게도 이 문제를 풀지 못하였다. 그래서 종원이는 여러분들에게 도움을 요청하였다. 종원이를 도와주기 위해 정n각형의 꼭짓점을 k개의 색으로 칠하는 서로 다른 경우의 수를 구하여라.

첫 번째 줄에 n, k가 주어진다.

n, k의 제한은 다음과 같다.

1 ≤ n ≤ 10⁹ , 1 ≤ k ≤ 25

조건을 만족시키면서, 정n각형의 꼭짓점을 k개의 색으로 칠하는 서로 다른 경우의 수를 1,000,000,007로 나눈 나머지를 구하여라.