cho.sh

Magic String

Count permutations of up to 8 given words whose concatenation is a string that has exactly K circular shifts equal to itself.

Medium7String matchingBrute forceCombinatoricsMathNo attempts yetTime limit2sMemory limit512 MB

Problem

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.

Input

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.

Output

Print the answer on the first line.