시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB23121178.571%

문제

길이가 n이며, 첫 m개의 소문자 알파벳만으로 이루어진 문자열 S가 주어진다. 이때, 길이가 n이고 첫 m개의 알파벳만으로 이루어진 문자열들 중, S와의 LCS (Longest Common Subsequence)의 길이가 n-1인 문자열의 개수를 구하시오.

입력

입력의 첫 번째 줄에는 문자열의 길이 n과 사용될 알파벳의 개수 m이 주어진다. (1 ≤ n ≤ 100,000; 2 ≤ m ≤ 26)

다음 줄에는 문자열 S가 주어진다. 이 문자열은 길이가 n이며, ‘a’에서 ‘a’+m-1까지의 문자들만으로 이루어졌음이 보장된다.

출력

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

예제 입력 1

3 3
aaa

예제 출력 1

6

예제 입력 2

3 3
aab

예제 출력 2

11

예제 입력 3

1 2
a

예제 출력 3

1

예제 입력 4

10 9
abacadefgh

예제 출력 4

789

힌트

첫 번째 예제에서는 aab, aac, aba, aca, baa, caa가 조건을 만족한다.

두 번째 예제에서는 aaa, aac, aba, abb, abc, aca, acb, baa, bab, caa, cab가 조건을 만족한다.

세 번째 예제에서는 b가 조건을 만족한다.