← 返回题目列表

Codeforces · 578/D

D. 再次濒海战斗舰

中文机器翻译题面 查看原题

给定一个长度为 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。