给定一个长度为 n 的字符串 S,每个字符都是前 m 个小写英文字母之一。
计算存在多少个由前 m 个小写英文字母组成的长度为 n 的不同字符串 T,使得 S 和 T 之间的 LCS(最长公共子序列)长度为 n - 1。
回想一下,两个字符串 S 和 T 的 LCS 是最长的字符串 C,使得 C 都在 S 和 T 中作为子序列。
输入
第一行包含两个数字 n 和 m,表示字符串 S 的长度以及构成字符串字符集的第一个英文小写字符的数量 (1 ≤ n ≤ 100 000, 2 ≤ m ≤ 26)。
第二行包含字符串 S。
输出
打印唯一包含答案的行。
示例
输入 #1
3 3 aaa
输出 #1
6
输入 #2
3 3 aab
输出 #2
11
输入 #3
1 2 a
输出 #3
1
输入#4
10 9 abacadefgh
输出#4
789
注意
对于第一个样本,6 个可能的字符串 T 是:aab、aac、aba、aca、baa、caa。
对于第二个样本,11 个可能的字符串 T 是:aaa、aac、aba、abb、abc、aca、acb、baa、bab、caa、cab。
对于第三个样本,唯一可能的字符串 T 是 b。