마법의 문자열

길이가 L인 문자열 T가 있다. 0 <= i < L인 각 i에 대해, T를 i번째 문자부터 시작하도록 원형으로 이동한 문자열을 T(i)라고 하자. T(i)의 길이는 T와 같고, 0 <= j < L인 모든 j에 대해 T(i)의 j번째 문자는 T의 ((i + j) mod L)번째 문자이다.

T(i)가 T와 같은 i의 개수가 정확히 K개이면 T를 마법의 문자열이라고 부른다.

N개의 문자열 S1, S2, ..., SN이 주어진다. 크기가 N인 모든 순열 p = (p0, p1, ..., pN-1)에 대해 새로운 문자열 Sp0 + Sp1 + ... + SpN-1을 만들 수 있다. 이 문자열이 마법의 문자열이 되는 순열의 개수를 구하라. 같은 값의 문자열이 여러 번 주어져도 입력에서의 위치가 다르면 서로 다른 순열 원소로 취급한다.

첫째 줄에 단어의 개수 N이 주어진다. N은 8보다 작거나 같은 자연수이다.

둘째 줄부터 N개의 줄에 각 단어가 주어진다. 단어의 길이는 최대 20이고, 알파벳 대문자로만 이루어져 있다.

마지막 줄에 K가 주어진다. K는 200보다 작거나 같은 자연수이다.

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