7668: [CSES Problem Set] Counting Necklaces
[Creator : ]
Description
Your task is to count the number of different necklaces that consist of $n$ pearls and each pearl has mm possible colors.
Two necklaces are considered to be different if it is not possible to rotate one of them so that they look the same.
Two necklaces are considered to be different if it is not possible to rotate one of them so that they look the same.
Input
The only input line has two numbers $n$ and $m$: the number of pearls and colors.
Output
Print one integer: the number of different necklaces modulo $10^9+7$.
Constraints
$1≤n,m≤10^6$
Sample 1 Input
4 3
Sample 1 Output
24