CF578D LCS Again

给定一个字符串 $S$，求有多少个与 $S$ 等长字符串 $T$，满足 $\mathrm{LCS}(S,T)=|S|-1$，其中 $S,T$ 只包含前 $m$ 个小写字母。 注：其中 $\operatorname{LCS}(S, T)$ 指的是 $S$ 和 $T$ 的最长公共子序列（Longest Commmon subsequence）。

第一行包括两个数字 $n$ 和 $m$，第二行是给定的字符串 $S$。

输出一行一个整数表示答案。

$ 1\leq n\leq 10^5,2\leq m\leq 26 $。