F - Avoid K Palindrome 2 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

英小文字のみからなる長さ N の文字列 S が与えられます。

S の文字を並び替えて得られる文字列（S 自身を含む）であって、長さ K の回文を部分文字列として 含まない ものの個数を求めてください。

ただし、長さ N の文字列 T が「長さ K の回文を部分文字列として含む」とは、
ある (N-K) 以下の非負整数 i が存在して、1 以上 K 以下の任意の整数 j について T_{i+j}=T_{i+K+1-j} が成り立つことをいいます。
ここで、T_k は文字列 T の k 文字目を表すものとします。

制約

  • 2\leq K \leq N \leq 10
  • N,K は整数
  • S は英小文字のみからなる長さ N の文字列

入力

入力は以下の形式で標準入力から与えられる。

N K
S

出力

S の文字を並び替えて得られる文字列であって、長さ K の回文を部分文字列として含まないものの個数を出力せよ。

入力例 1

3 2
aab

出力例 1

1

aab を並び替えて得られる文字列は aab, aba, baa の 3 つであり、このうち aab および baa は長さ 2 の回文 aa を部分文字列として含んでいます。
よって、条件をみたす文字列は aba のみであり、1 を出力します。

入力例 2

5 3
zzyyx

出力例 2

16

zzyyx を並べて得られる文字列は 30 個ありますが、そのうち長さ 3 の回文を含まないようなものは 16 個です。よって、16 を出力します。

入力例 3

10 5
abcwxyzyxw

出力例 3

440640

Score : 300 points

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