Score : $300$ points

问题陈述

给定一个由小写英文字母组成的字符串 $S$，长度为 $N$。

找出通过排列字符串 $S$ 的字符得到的字符串数量（包括字符串 $S$ 本身），这些字符串不包含长度为 $K$ 的回文子串。

这里，如果存在一个非负整数 $i$，且 $i$ 不大于 $(N-K)$，使得对于每一个整数 $j$，满足 $1 \leq j \leq K$，都有 $T_{i+j} = T_{i+K+1-j}$，则称长度为 $N$ 的字符串 $T$ "包含长度为 $K$ 的回文子串"。 在这里，$T_k$ 表示字符串 $T$ 的第 $k$ 个字符。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given a string $S$ of length $N$ consisting only of lowercase English letters.

Find the number of strings obtained by permuting the characters of $S$ (including the string $S$ itself) that do not contain a palindrome of length $K$ as a substring.

Here, a string $T$ of length $N$ is said to "contain a palindrome of length $K$ as a substring" if and only if there exists a non-negative integer $i$ not greater than $(N-K)$ such that $T_{i+j} = T_{i+K+1-j}$ for every integer $j$ with $1 \leq j \leq K$.
Here, $T_k$ denotes the $k$-th character of the string $T$.

Constraints

• $2 \leq K \leq N \leq 10$
• $N$ and $K$ are integers.
• $S$ is a string of length $N$ consisting only of lowercase English letters.

Input

The input is given from Standard Input in the following format:

$N$ $K$

$S$

Output

Print the number of strings obtained by permuting $S$ that do not contain a palindrome of length $K$ as a substring.

Sample Input 1

3 2
aab

Sample Output 1

1

The strings obtained by permuting aab are aab, aba, and baa. Among these, aab and baa contain the palindrome aa of length $2$ as a substring.
Thus, the only string that satisfies the condition is aba, so print $1$.

Sample Input 2

5 3
zzyyx

Sample Output 2

16

There are $30$ strings obtained by permuting zzyyx, $16$ of which do not contain a palindrome of length $3$. Thus, print $16$.

Sample Input 3

10 5
abcwxyzyxw

Sample Output 3

440640