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