103632: [Atcoder]ABC363 C - Avoid K Palindrome 2

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

问题陈述

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

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

这里，如果存在一个非负整数i，不大于(N-K)，使得对于每个整数j（1≤j≤K），都有T_{i+j} = T_{i+K+1-j}，那么长度为N的字符串T“包含长度为K的回文作为子字符串”。
这里，T_k表示字符串T的第k个字符。

约束条件

• 2≤K≤N≤10
• N和K是整数。
• S是由小写英文字母组成的长度为N的字符串。

输入

输入从标准输入以下格式给出：

N K
S

输出

打印通过排列S得到的字符串的数量，这些字符串不包含长度为K的回文作为子字符串。

示例输入1

3 2
aab

示例输出1

1

通过排列aab得到的字符串有aab、aba和baa。在这些字符串中，aab和baa包含长度为2的回文aa作为子字符串。
因此，满足条件的唯一字符串是aba，所以打印1。

示例输入2

5 3
zzyyx

示例输出2

16

通过排列zzyyx得到的字符串有30个，其中16个不包含长度为3的回文。因此，打印16。

示例输入3

10 5
abcwxyzyxw

示例输出3

440640