Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

D. И снова НОП!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка S длины n, где каждый символ является одной из первых m строчных букв английского алфавита.

Подсчитайте, сколько различных строк T длины n, состоящих из первых m букв английского алфавита существует, таких, что длина НОП (наибольшей общей подпоследовательности) S и T равняется n - 1.

Напомним, что НОП двух строк, S и T — это наибольшая строка C, такая, что C встречается как в S, так и в T как подпоследовательность.

Входные данные

В первой строке записано два числа, n и m, обозначающих длину строки S и количество первых строчных букв английского алфавита, из которых формируется набор символов для строк (1 ≤ n ≤ 100 000, 2 ≤ m ≤ 26).

Во второй строке записана сама строка S.

Выходные данные

Выведите ответ в единственной строке.

Примеры
Входные данные
3 3
aaa
Выходные данные
6
Входные данные
3 3
aab
Выходные данные
11
Входные данные
1 2
a
Выходные данные
1
Входные данные
10 9
abacadefgh
Выходные данные
789
Примечание

В первом примере 6 возможных строк T таковы: aab, aac, aba, aca, baa, caa.

Во втором примере 11 возможных строк T таковы: aaa, aac, aba, abb, abc, aca, acb, baa, bab, caa, cab.

В третьем примере единственная возможная строка T такова: b.