A string is found at an archaelogical place. Integer values M and N are also written there. There is also a lock. Kun being a great archaeologist, found by decoding the description, that the key to the lock is a string of length N which contains M occurrences of the given string P.
Kun knows that there can be many such strings, so he wants you to find the numbers of such strings modulo 1000000007.
All strings must contain lowercase English alphabets only.
Also the occurrences can overlap.
1 <= N * M * len(P) <= 100000
Input: First-line contains integers N and M (length of resultant string and occurrences required)
Second-line contains string P.
Output: Print a single integer the answer to the problem.