Counting strings with LCS n-1

You are given a string $S$ of length $n$ that uses only the first $m$ lowercase letters of the alphabet.

Count the strings $T$ of length $n$, built from the same $m$ letters, whose longest common subsequence (LCS) with $S$ has length exactly $n-1$.

A subsequence of a string is what remains after deleting zero or more characters and keeping the order of the characters that stay.

The first line contains the string length $n$ and the alphabet size $m$, separated by a space. ($1 \le n \le 100000$, $2 \le m \le 26$)

The second line contains the string $S$. Its length is $n$, and it uses only the first $m$ lowercase letters starting from a.

Print the number of strings that satisfy the condition on one line.