410303: GYM104003 K William and Necklace

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. William and Necklacetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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

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

ExamplesInput
2 3
aa
Output
5850
Input
3 5
abc
Output
2375620
Note

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.

加入题单

上一题 下一题 算法标签: