579_F. LCS Again_28659
You are given a string S of length n with each character being one of the first m lowercase English letters. 

Calculate how many different strings T of length n composed from the first m lowercase English letters exist such that the length of LCS (longest common subsequence) between S and T is n - 1.

Recall that LCS of two strings S and T is the longest string C such that C both in S and T as a subsequence.

Input

The first line contains two numbers n and m denoting the length of string S and number of first English lowercase characters forming the character set for strings (1 ≤ n ≤ 100 000, 2 ≤ m ≤ 26).

The second line contains string S.

Output

Print the only line containing the answer.

Examples

Input

3 3
aaa


Output

6


Input

3 3
aab


Output

11


Input

1 2
a


Output

1


Input

10 9
abacadefgh


Output

789

Note

For the first sample, the 6 possible strings T are: aab, aac, aba, aca, baa, caa. 

For the second sample, the 11 possible strings T are: aaa, aac, aba, abb, abc, aca, acb, baa, bab, caa, cab.

For the third sample, the only possible string T is b.
def main():
    n, m = map(int, input().split())
    s = input()
    k = sum(s[i] != s[i - 1] for i in range(1, n)) + 1
    x = i = 0
    while i < n - 1:
        if s[i] != s[i + 1]:
            j = i
            while i + 2 < n and s[i] == s[i + 2]:
                i += 1
            j = (i - j) + 2
            x += j * (j - 1) // 2
        i += 1
    ans = k * (m * n - n) - x
    print(ans)
main()

3 3
aaa
 10 9
abacadefgh
 1 2
a
 3 3
aab
 1 26
z
 100 26
jysrixyptvsesnapfljeqkytlpeepjopspmkviqdqbdkylvfiawhdjjdvqqvcjmmsgfdmpjwahuwhgsyfcgnefzmqlvtvqqfbfsf
 15 3
abababababababa
 100 27
jysrixyptvsesnapfljeqkytlpeepjopspmkviqdqbdkylvfiawhdjjdvqqvcjmmsgfdmpjwahuwhgsyfcgnefzmqlvtvqqfbfsf
 3 6
aab
 10 14
abacadefgh
 1 2
b
 3 12
aab
 10 16
abacadefgh
 1 3
b
 10 18
abacadefgh
 10 9
abacadefhg
 3 2
aab
 3 19
aab
 10 16
abacadeegh
 10 10
abacadefgh
 10 19
hgfedacaba
 3 29
aab
 10 29
abacadeegh
 10 8
hgfedacaba
 10 10
aeacacbfgh
 1 26
y
 100 30
jysrixyptvsesnapfljeqkytlpeepjopspmkviqdqbdkylvfiawhdjjdvqqvcjmmsgfdmpjwahuwhgsyfcgnefzmqlvtvqqfbfsf
 15 6
abababababababa
 10 11
abacadefgh
 100 27
jysrixyptvsesnapfljeqkytlpeepjopspmkviqdqbdkylvfiawhdjjdvqqvcjmmsgfdmpjwahuwhgsyfcgnffzmqlvtvqqfbfsf
 10 14
abadadefgh
 1 1
a
 3 10
aab
 10 14
bbacadefgh
 3 36
aab
 10 8
abacadeegh
 1 5
c
 10 21
hgfedacaba
 3 41
aab
 15 3
ababababababaca
 10 18
abadadefgh
 15 3
aaabababababaca
 3 14
baa
 10 21
abacadefhh
 10 8
aaacadeffh
 3 13
baa
 10 8
hcfedafaaa
 3 11
daa
 3 9
daa
 100 34
jysrixyptvsesnapfljeqkytlpeepjopspmkviqdqbdkylvfiawhdjjdvqqvcjmmsgfdmpjwahuwhgsyfcgnefzmqlvtvqqfbfsf
 3 3
bab
 3 2
aba
 3 35
aab
 10 16
abacbdeegh
 10 30
hgfedacaba
 3 50
aab
 10 29
abacadedgh
 1 36
y
 3 8
aab
 10 19
bbacadefgh
 3 37
baa
 10 33
abacadefgh
 10 24
hgfedadaba
 3 14
aaa
 3 2
aaa
 10 24
abacbdeegh
 10 30
ggfedacaba
 10 29
abacbdedgh
 10 22
hgfedadaba
 3 9
aaa
 3 4
aaa
 10 22
abacbdeegh
 3 43
caa
 10 13
hgfedadaba
 3 4
baa
 10 22
ababbdeegh
 10 13
ggfedacaba
 10 30
ababbdeegh
 10 13
ggfedacaca
 10 16
igfedadaba
 10 13
ggfedadaca
 3 43
aaa
 3 25
aaa
 3 15
aaa
 3 7
aaa
 3 5
aab
 10 22
abacadefgh
 10 14
hgfedacaaa
 3 49
aab
 15 9
abababababababa
 10 11
abacacefgh
 100 35
jysrixyptvsesnapfljeqkytlpeepjopspmkviqdqbdkylvfiawhdjjdvqqvcjmmsgfdmpjwahuwhgsyfcgnffzmqlvtvqqfbfsf
 3 23
aab
 10 18
hgfedadaaa
 10 21
baacadefhh
 10 10
hffedacaaa
 10 8
hcfedfaaaa
 3 13
dba
 10 9
hgfedacabb
 10 16
abbcbdeegh
 10 35
bbacadefgh
 3 26
aab
 10 24
ggfedadaba
 10 42
abacbdeegh
 10 40
ggfedacaba
 3 45
caa
 10 34
abadadefgh

6
 789
 1
 11
 25
 237400
 345
 246900
 29
 1289
 1
 65
 1489
 2
 1689
 789
 5
 107
 1340
 889
 1789
 167
 2510
 689
 887
 25
 275400
 1020
 989
 244301
 1287
 0
 53
 1161
 209
 620
 4
 1989
 239
 369
 1687
 332
 77
 1790
 483
 71
 552
 59
 47
 313400
 15
 6
 203
 1341
 2889
 293
 2788
 35
 41
 1611
 215
 3189
 2287
 39
 3
 2061
 2600
 2789
 2087
 24
 9
 1881
 251
 1187
 17
 1670
 1070
 2310
 1066
 1487
 1068
 126
 72
 42
 18
 23
 2089
 1032
 287
 1695
 987
 319501
 131
 1350
 1592
 623
 484
 106
 711
 1192
 3051
 149
 2058
 3681
 3500
 263
 3287
