I. Mofusigil's String Challenge
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mofusigil decides to test the wit of his old friend, Caiwen.

Mofusigil starts with a hidden original string of length $$$n$$$. He then performs exactly $$$m$$$ operations on it. In each operation, he selects a random position in the string and replaces the character at that position with a different lowercase English letter.

It is important to note that:

  • The same position can be modified multiple times.
  • The character used for replacement must always be different from the character currently at that position (immediately before the replacement).
  • The string consists only of lowercase English letters.

After performing these $$$m$$$ operations, Mofusigil shows Caiwen the final result string and asks: "Based on this final string, how many different original strings could I have started with?"

Mofusigil expected Caiwen to solve this instantly, but Caiwen stared at the string in total confusion. Seeing his friend's struggle, Mofusigil decided to go easy on him and guaranteed that the number of operations $$$m$$$ is very small: $$$m \le 2$$$.

Unfortunately, even with this simplification, Caiwen is completely stumped. Not wanting to lose face in front of Mofusigil, Caiwen has secretly asked for your help.

Input

The first line contains two integers $$$n$$$ ($$$1 \le n \le 10^6$$$) and $$$m$$$ ($$$0 \le m \le 2$$$), denoting the length of the final string and the number of operations.

The second line contains the final string.

Output

Print a number denoting the number of possible original strings.

Examples
Input
4 1
momo
Output
100
Input
4 2
momo
Output
3851