LCS Again

题意翻译

### 题目描述 给定一个字符串 $S$，求有多少个与 $S$ 等长字符串 $T$，满足 $\mathrm{LCS}(S,T)=|S|-1$，其中 $S,T$ 只包含前 $m$ 个小写字母。 ### 输入格式 第一行包括两个数字 $n$ 和 $m$，第二行是给定的字符串 $S$。 ### 输出格式 输出一行一个整数表示答案。

题目描述

You are given a string $ S $ of length $ n $ with each character being one of the first $ m $ lowercase English letters. Calculate how many different strings $ T $ of length $ n $ composed from the first $ m $ lowercase English letters exist such that the length of LCS (longest common subsequence) between $ S $ and $ T $ is $ n-1 $ . Recall that LCS of two strings $ S $ and $ T $ is the longest string $ C $ such that $ C $ both in $ S $ and $ T $ as a subsequence.

输入输出格式

输入格式

The first line contains two numbers $ n $ and $ m $ denoting the length of string $ S $ and number of first English lowercase characters forming the character set for strings ( $ 1<=n<=100000 $ , $ 2<=m<=26 $ ). The second line contains string $ S $ .

输出格式

Print the only line containing the answer.

输入输出样例

输入样例 #1

3 3
aaa

输出样例 #1

6

输入样例 #2

3 3
aab

输出样例 #2

11

输入样例 #3

1 2
a

输出样例 #3

1

输入样例 #4

10 9
abacadefgh

输出样例 #4

789

说明

For the first sample, the $ 6 $ possible strings $ T $ are: aab, aac, aba, aca, baa, caa. For the second sample, the $ 11 $ possible strings $ T $ are: aaa, aac, aba, abb, abc, aca, acb, baa, bab, caa, cab. For the third sample, the only possible string $ T $ is b.

题意翻译

### 题目描述 给定一个字符串 $S$，求有多少个与 $S$ 等长字符串 $T$，满足 $\mathrm{LCS}(S,T)=|S|-1$，其中 $S,T$ 只包含前 $m$ 个小写字母。 ### 输入格式 第一行包括两个数字 $n$ 和 $m$，第二行是给定的字符串 $S$。 ### 输出格式 输出一行一个整数表示答案。