|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Сложность Гамма
Consider a string T containing exactly L characters.
The string Ti is a cyclic shift of T starting
from position i (0 ≤ i < L). Ti
contains exactly the same number of characters as T. For each j
between 0 and L-1, inclusive, character j of Ti
is equal to character (i+j)%L of T. Let's call
T a magic word if there are exactly K positions i
such that Ti = T.
You are given a set of N words S = {S[0], ..., S[N-1]}.
For each permutation p = {p[0], ..., p[N-1]} of
integers between 0 and N-1, inclusive, we can define a string generated
by this permutation as a concatenation S[p[0]] + ... + S[p[N-1]].
Return the number of permutations that generate magic words. All indices in
this problem as 0-based.
Input
The first line contains two numbers N and K (1 ≤ N ≤ 8,
1 ≤ K ≤ 200). Next N lines will contain strings S[i].
Each line will contain only uppercase Latin letters ('A' - 'Z'). All lines
will contain between 1 and 20 characters, inclusive.
Output
Output single number - the number of permutations that generate magic words.
|
Input 1
|
Input 2
|
Input 3
|
Input 4
|
3 1
CAD
ABRA
ABRA
|
3 2
AB
RAAB
RA
|
4 1
AA
AA
AAA
A
|
6 15
AA
AA
AAA
A
AAA
AAAA
|
|
Output 1
|
Output 2
|
Output 3
|
Output 4
|
6
|
3
|
0
|
720
|
Для отправки решений необходимо выполнить вход.
|