410303: GYM104003 K William and Necklace

William loves making necklaces. He has an infinite number of each letter 'a'...'z', and wants to arrange them in a circle to make a necklace of length $$$n$$$, where $$$n$$$ is prime.

However, William only wants to make good necklaces. A necklace is considered good if it does not contain the string $$$s$$$, even after rotation.

Help William count the number of distinct good necklaces he can make. Two necklaces are the same if one can be rotated to be equal to the other. "abab" and "baba" are the same, but "abab" and "aabb" are distinct.

The first line contains two integers, $$$m$$$ and $$$n$$$ ($$$1 \leq m \leq n \leq 250$$$). It is guaranteed that $$$n$$$ is prime.

Then, the next line contains the string $$$s$$$, which consists of $$$m$$$ lowercase letters.

Output the number of distinct good necklaces, mod $$$10^9+7$$$.

2 3
aa

5850

3 5
abc

2375620

In the first example, there are 5876 total necklaces of length 3. Of those, the 26 necklaces in the form "aa?" (or equivalently, "a?a" or "?aa") are not good, leaving a total of 5850 necklaces that are good.