Magic String

There is a string T of length L. For each i with 0 <= i < L, let T(i) be the circular shift of T that starts from the i-th character. Its length is the same as T. For every j with 0 <= j < L, the j-th character of T(i) is the ((i + j) mod L)-th character of T.

If exactly K values of i make T(i) equal to T, then T is called a magic string.

You are given N strings S1, S2, ..., SN. For every permutation p = (p0, p1, ..., pN-1) of size N, define a new string Sp0 + Sp1 + ... + SpN-1. Count how many permutations make this new string a magic string. If two input strings have the same value, their input positions are still treated as distinct elements of the permutation.

The first line contains the number of words N. N is a positive integer no greater than 8.

Each of the next N lines contains one word. Each word has length at most 20 and consists only of uppercase English letters.

The last line contains K. K is a positive integer no greater than 200.

Print the answer on the first line.