题目描述

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

重排列字符串 $S$，问有多少种排列方式使得，字符串 $S$ 不存在长度为 $K$ 的回文子串。

输入格式

第一行输入 $N$ $K$

第二行输入 $S$

输出格式

输出一个整数代表答案。

3 2
aab

1

5 3
zzyyx

16

10 5
abcwxyzyxw

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