Вам дана строка S длины n, где каждый символ является одной из первых m строчных букв английского алфавита.
Подсчитайте, сколько различных строк T длины n, состоящих из первых m букв английского алфавита существует, таких, что длина НОП (наибольшей общей подпоследовательности) S и T равняется n - 1.
Напомним, что НОП двух строк, S и T — это наибольшая строка C, такая, что C встречается как в S, так и в T как подпоследовательность.
Выходные данные
Выведите ответ в единственной строке.
Примечание
В первом примере 6 возможных строк T таковы: aab, aac, aba, aca, baa, caa.
Во втором примере 11 возможных строк T таковы: aaa, aac, aba, abb, abc, aca, acb, baa, bab, caa, cab.
В третьем примере единственная возможная строка T такова: b.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
aaa
|
6
|
|
2
|
3 3
aab
|
11
|
|
3
|
1 2
a
|
1
|
|
4
|
10 9
abacadefgh
|
789
|