Word Equations

Every non-empty sequence of the symbols 0 and 1 is called a binary word. A word equation has the form

$x_1 x_2 \dots x_l = y_1 y_2 \dots y_r,$

where each $x_i$ and each $y_j$ is either a binary digit (0 or 1) or a variable (a lowercase letter of the English alphabet).

Every variable has a fixed length: the number of binary digits of the words that may be substituted for it. To solve a word equation you must assign to every variable a binary word of exactly that variable's length, so that after substituting the assigned words for all variables, the left side and the right side become the same binary word.

For example, let $a, b, c, d, e$ be variables of lengths $4, 2, 4, 4, 2$ respectively, and consider the equation

$1bad1 = acbe.$

It has exactly $16$ distinct solutions.

For a given equation, compute how many distinct solutions it has. Your program should:

• read the number of equations and their descriptions from standard input;
• find the number of solutions of each equation;
• write the results to standard output.

The first line contains an integer $x$ ($1 \le x \le 5$), the number of equations. The descriptions of the $x$ equations follow, with no blank lines between them. Each description consists of exactly six lines:

1. An integer $k$ ($0 \le k \le 26$), the number of distinct variables in the equation. The variables are the first $k$ lowercase letters of the English alphabet.
2. A sequence of $k$ positive integers separated by single spaces: the lengths of the variables $a, b, \dots$ in order (the first number is the length of $a$, the second the length of $b$, and so on). When $k = 0$ this line is empty.
3. An integer $l$, the length of the left side of the equation, that is, the number of digits and variable letters written in it.
4. The left side of the equation, written as a string of digits and variable letters with no spaces.
5. An integer $r$, the length of the right side of the equation.
6. The right side of the equation, encoded in the same way as the left side.

On each side, the number of digits plus the sum of the lengths of the variables (counting every occurrence of a variable) is at most $10\,000$.

For each $i$ from $1$ to $x$, write on the $i$-th line the number of distinct solutions of the $i$-th equation.