You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

AT_abc363_c [ABC363C] Avoid K Palindrome 2

题目描述

给定长度为 $N$ 的字符串 $S$。 请求出 $S$ 重排字符串（包括 $S$ 本身）中，不包含长度为 $K$ 的回文子字符串的个数。

但是，长度为 $N$ 的字符串 $T$“包含长度为 $K$ 的回文作为子字符串” 是指$\exist i \le n-k,j=1,2,3,\dots,k,T_{i+j}=T_{i+K+1-j}$成立。

$T_k$ 表示字符串 $T$ 的第 $k$ 个字符。

输入格式

输入以以下形式由标准输入给出。

$N$ $K$ $S$

输出格式

输出将 $S$ 的字符重新排列得到的字符串中不包含长度 $K$ 的回文子串的字符串的个数。

输入输出样例 #1

输入 #1

3 2
aab

输出 #1

1

输入输出样例 #2

输入 #2

5 3
zzyyx

输出 #2

16

输入输出样例 #3

输入 #3

10 5
abcwxyzyxw

输出 #3

440640

说明/提示

约束条件

• $2\le K \le N \le 10$
• $N,K$为整数
• $S$ 长度为 $N$，仅包含小写字母

样例 #1 解释

重新排列 aab 得到的字符串是 aab，aba，baa，其中 aab 和 baa 包含长度 $2$ 的回文子串 aa 作为部分字符串。因此，满足条件的字符串只有 aba，输出 $1$。

样例 #2 解释

排列 zzyyx 得到的字符串有 $30$ 个，其中不包含长度 $3$ 的回文子串的字符串有 $16$ 个。因此，输出 $16$。