LCS 길이가 n-1인 문자열 개수

길이가 $n$이고 알파벳 소문자 중 앞에서 $m$개만 사용하는 문자열 $S$가 주어진다.

길이가 $n$이고 같은 $m$개의 문자만 사용하는 문자열 $T$ 가운데, $S$와 $T$의 최장 공통 부분 수열(LCS) 길이가 정확히 $n-1$인 것이 몇 개인지 구한다.

부분 수열은 원래 문자열에서 문자를 0개 이상 지우고 남은 문자를 순서대로 이어 붙인 문자열이다.

첫째 줄에 문자열의 길이 $n$과 사용하는 알파벳의 개수 $m$이 공백을 사이에 두고 주어진다. ($1 \le n \le 100000$, $2 \le m \le 26$)

둘째 줄에 문자열 $S$가 주어진다. $S$는 길이가 $n$이고, a부터 시작하는 앞쪽 $m$개의 알파벳 소문자만으로 이루어진다.

조건을 만족하는 문자열의 개수를 한 줄에 출력한다.