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$ 的回文子串的字符串的个数。

约束条件

• $ 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$。