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.
import java.util.Scanner;

public class Main {
	private void solve() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		char[] string = sc.next().toCharArray();
		int[] s = new int[n + 2];
		for (int i = 1; i <= n; i++) {
			s[i] = string[i - 1] - 'a';
		}

		long[][] dp = new long[n + 1][8];
		for (int i = 0; i < m; i++) {
			int state = 1;
			if (i == s[1])
				state |= 2;
			if (i == s[1] || i == s[2])
				state |= 4;
			dp[1][state]++;
		}

		for (int i = 2; i <= n; i++) {
			for (int j = 0; j < 8; j++) {
				int[] d = { i - 3 + get_bit(j, 0), i - 2 + get_bit(j, 1),
						i - 2 + get_bit(j, 2), 0 };
				for (int k = 0; k < m; k++) {
					int[] d2 = new int[4];
					for (int l = 1; l < 4; l++) {

						if (s[i - 2 + l] == k)
							d2[l] = d[l - 1] + 1;
						else
							d2[l] = Math.max(d2[l - 1], d[l]);
					}
					if (d2[1] >= i - 2 && Math.min(d2[2], d2[3]) >= i - 1)
						dp[i][(d2[1] - (i - 2)) | ((d2[2] - (i - 1)) << 1)
								| ((d2[3] - (i - 1)) << 2)] += dp[i - 1][j];
				}
			}
		}
		System.out.println(dp[n][0] + dp[n][1] + dp[n][4] + dp[n][5]);
	}

	private int get_bit(int x, int v) {
		return (x >> v) & 1;
	}

	public static void main(String[] args) {
		new Main().solve();
	}
}
