K. William and Necklace
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard 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$$$.

Examples
Input
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.