Veshy is trying to come up with a username for his new alt-account! Unfortunately, he is currently in a creative lull, so he has turned to permuting strings of lowercase letters of length $N$ to find a username. This was still not creative enough for Veshy, so he is currently trying to increase the number of potential candidate usernames by having $K$ wildcard characters (*) in his starting string before permuting. Since you are Veshy's absolute best friend, help him find the number of candidate usernames!

Constraints

For all subtasks:

$1\le N\le 15$

$0\le K\le 2$

Subtask 1 [10%]

$N\le 5$

Subtask 2 [10%]

$K=0$

Subtask 3 [20%]

$K=1$

Subtask 4 [60%]

No additional constraints.

Input Specification

The first line will have $2$ space-separated integers, $N$ and $K$. The following line will have a string composed of only lowercase alphabet characters and/or the character *. There will be $K$ *'s in the string.

Output Specification

Output the total number of possible permutations of the string.

Sample Input 1

2 1
b*

Sample Output 1

51

Explanation of Sample Output 1

There are $26$ different possibilities for the wildcard character. Out of these $26$ possibilities, $25$ result in $2$ unique permutations (e.g. ba → ba and ab, bc → bc and cb, etc.), and $1$ results in only $1$ unique permutation (when the wildcard character is b, to make bb). $2\times 25+1=51$.

Sample Input 2

2 2
**

Sample Output 2

676