#4175. 小G的电话本

内存限制:256 MiB 时间限制:45 Sec

题目描述

 G是一个商人,他有一个电话本。电话本上记下了许多联系人,如timesqrorzyhb等等。不过Tony对其中的某个联系人的名字S特别感兴趣,他从中提取出了这个联系人的名字中的所有片段,如提取出orz   orzorrzorz等等。现在他想请你统计有多少个长度为k的片段对(P[1], P[2], P[3], ..., P[k]),使得在该片段对中所有片段在S中出现次数之和为他的幸运数m?注意两个片段对不同当且仅当两个片段对的某一位的片段不同,两个片段不同当且仅当这两个片段在S中的位置不同

输入格式

第一行两个整数km,意义见题目描述;第二行给出一个字符串表示Tony喜欢的联系人名字S

输出格式

输出一行一个整数ans,表示答案模1005060097

样例

样例输入


			
3 4
aaaaa

样例输出


			
6

数据范围与提示

【样例解释】



符合要求的片段对一共有6种(用[p]s表示起始位置为p的s片段):


([1]aaaa, [1]aaaaa, [1]aaaaa)、([1]aaaaa, [1]aaaa, [1]aaaaa)、


([1]aaaaa, [1]aaaaa, [1]aaaa)、([2]aaaa, [1]aaaaa, [1]aaaaa)、


([1]aaaaa, [2]aaaa, [1]aaaaa)、([1]aaaaa, [1]aaaaa, [2]aaaa)。


【数据范围】


设n表示联系人的名字的长度,联系人的名字只包含小写字母。


对于10%的数据,1 <= n <= 100, k = 1。


对于40%的数据,1 <= n <= 100, k = 2。


对于70%的数据,1 <= n <= 100000, 1 <= k <= 10。


对于100%的数据,1 <= n <= 100000, 1 <= k <= 100000, 1 <= m <= n。