Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

greedy

*2700

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. LCS Again

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 04:48:30 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|