시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 95 27 24 30.769%

문제

T는 길이가 L인 문자열이다.

T(i)는 T의 i번째 위치부터 시작하게 이동시킨 것이다. (0<=i<L)

T(i)는 T의 길이와 같다.

따라서, 0보다 크거나 같고, L-1보다 작거나 같은 모든 j에 대해, T(i)의 j번째 문자는 T의 (i+j)%L번째 문자와 같을 것이다.

만약에, T(i) = T인 i가 정확하게 K개 있다면, T를 마법의 단어라고 한다.

N개의 단어(S)가 주어진다. 0보다 크거나 같고, N-1보다 작거나 같은 각 순열 p = {p[0], p[1], …, p[N-1]}을 이용해서 새로운 단어를 만들 수 있다. S[p[0]] + S[p[1]] + … + S[p[N-1]]과 같이 만들면 된다. 이 때, 마법의 단어가 나오는 순열의 개수를 출력하는 프로그램을 작성하시오.
 

입력

첫째 줄에 단어의 개수 N이 주어진다. N은 8보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 단어가 주어진다. 단어의 길이는 최대 20이다. 단어는 알파벳 대문자로만 이루어져 있다. 마지막 줄에 K가 주어진다. K는 200보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력

3
AB
RAAB
RA
2

예제 출력

3

힌트

출처