2528: LCS Again
[Creator : ]
Description
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.
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.
Input
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$.
The second line contains string $S$.
Output
Print the only line containing the answer.
Sample 1 Input
3 3
aaa
Sample 1 Output
6
the 6 possible strings T are: aab, aac, aba, aca, baa, caa.
Sample 2 Input
3 3
aab
Sample 2 Output
11
The 11 possible strings T are: aaa, aac, aba, abb, abc, aca, acb, baa, bab, caa, cab.
Sample 3 Input
1 2
a
Sample 3 Output
1
the only possible string T is b.