P7454 [THUSC 2017] If Miracles Have Colors

Fabben Company used to be the world’s largest chemical enterprise. They produced dyes with a wide variety of colors, such as Tsinghua Purple, Soul Yellow, Forgive Green, Meeting Blue, Premium Black, Peking University Red, Album White, and so on.

Now Person B has a cycle consisting of $n$ regions. Person B wants to dye these $n$ regions using $m$ colors. Person B does not want there to exist $m$ consecutive regions among these $n$ regions such that all $m$ colors appear exactly once. In other words, for any $m$ consecutive regions, it must not be the case that all $m$ colors appear exactly. If two colorings can be made exactly the same by rotation, then we consider them essentially the same. However, if two colorings need to be made exactly the same by reflection (flipping), we do not consider them essentially the same. For example, if $n=4,m=4$: We consider $1,2,3,4$ and $3,4,1,2$ to be essentially the same coloring. We consider $1,2,3,4$ and $4,3,2,1$ to be essentially different colorings. We consider $1,2,1,2$ and $2,1,2,1$ to be essentially the same coloring. Person B wants to know the number of essentially different colorings that satisfy the condition. Output the answer modulo $10^9+7$.

Read input from standard input. The input consists of one line containing two integers $n,m$, where $n$ denotes the length of the cycle and $m$ denotes the number of colors.

Write output to standard output. Output one line with one integer, representing the result of the answer modulo $10^9+7$.

For $100\%$ of the test points, $1\le n\le 10^9,2\le m\le7$. | Test point ID $\operatorname*{Id}$ | $n$ | $m$ | | :----------: | :----------: | :----------: | | 1~2 | $n\le10$ | $m=\operatorname*{Id}+2$ | | 3~8 | $n\le 10^5,n$ is prime | $m=\operatorname*{Id}-1$ | | 9~14 | $n$ is prime | $m=\operatorname*{Id}-7$ | | 15~19 | No special constraints | $m=\operatorname*{Id}-13$ | | 20 | $n=635,643,090$ | $m=7$ | Translated by ChatGPT 5