贝西因不懂字母而被解雇后,决定去鱼片和鸡蛋食者学院上学。她的学习取得了很大的进步,现在已经认识了前 k 个英文字母。
每天早上,Bessie 沿着由 m + n 块瓷砖组成的人行道去学校。为了帮助Bessie复习,Moozing先生用前k个小写英文字母中的一个标记了前m个人行道瓷砖中的每一个,拼出字符串t。莫辛先生对贝西对农场动物的丰富知识印象深刻,计划让她自己完成人行道最后 n 块瓷砖的标记。
考虑结果字符串 s (|s| = m + n),该字符串由按照从家到学校的顺序标记在图块上的字母组成。对于任何索引序列 p1 < p2 < ... < pq,我们可以将字符串 s 的子序列定义为字符串 sp1sp2...spq。如果两个子序列作为字符串不同,则认为它们是不同的。 Bessie 希望对人行道的剩余部分进行标记,以使不同的瓷砖子序列的数量尽可能多。然而,由于贝西还没有学完字母表,她需要你的帮助!
请注意,空子序列也计算在内。
输入
输入的第一行包含两个整数 n 和 k (0 ≤ n ≤ 1 000 000, 1 ≤ k ≤ 26)。
第二行包含一个仅由前 k 个小写英文字母组成的字符串 t (|t| = m, 1 ≤ m ≤ 1 000 000)。
输出
确定 Bessie 在用前 k 个小写英文字母之一标记最后 n 个人行道瓷砖后可以形成的不同子序列的最大数量。由于这个数字可能相当大,因此您应该将其打印为 109 + 7 模。
请注意,系统不会要求您最大化模 109 + 7 的余数!目标是最大化初始值,然后打印余数。
示例
输入 #1
1 3 ac
输出 #1
8
输入 #2
0 2 aaba
输出 #2
10
注意
在第一个示例中,最佳标签给出 8 个不同的子序列:“”(空字符串)、“a”、“c”、“b”、“ac”、“ab”、“cb”和“acb”。
在第二个示例中,整个人行道已被标记。有 10 个可能的不同子序列:“”(空字符串)、“a”、“b”、“aa”、“ab”、“ba”、“aaa”、“aab”、“aba”和“aaba”。请注意,某些字符串(包括“aa”)可以通过多个图块序列获得,但仅计算一次。