题目描述

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

输入格式

第一行两个整数$k$和$m$，分别表示长度和幸运数；第二行给出一个字符串表示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 \leq 100000, 1 \leq k \leq 100000, 1 \leq m \leq n$。