WORDEQ - Word equations

no tags 

Every non-empty sequence of elements 0 and 1 is called a binary word. A word equation is an equation of the form x1x2...xl = y1y2...yr, where xi and yj are binary digits (0 or 1) or variables i.e. small letters of English alphabet. For every variable there is a fixed length of the binary words that can be substituted for this variable. This length is called a length of variable. In order to solve a word equation we have to assign binary words of appropriate length to all variables (the length of the word assigned to the variable x has to be equal to the length of this variable) in such a way that if we substitute words for variables then both sides of the equation (which are binary words after substitution) become equal.

For a given equation compute how many distinct solutions it has.

Example

Let a, b, c, d, e be variables and let 4, 2, 4, 4, 2 be their lengths (4 is the length of a, 2 is the length of b etc.). Consider the equation:

1bad1 = acbe

This equation has 16 distinct solutions.

Input

The number of equations t is in the first line of input, then t descriptions of equations follow separated by an empty line.

Each description consists of 6 lines. An equation is described in the following way: in the first line of the description there is an integer k, 0 <= k <= 26, which denotes the number of distinct variables in the equation. We assume that variables are the first k small letters of English alphabet. In the second line there is a sequence of k positive integers separated by single spaces. These numbers denote the lengths of variables a, b, ... from the equation (the first number is the length of a, the second - b, etc.). There is an integer l in the third line of the description, which is the length of the left size of equation, i.e. the length of the word built of digits 0 or 1 and variables (single letters). The left side of the equation is written in the next line as a sequence of digits and variables with no spaces between them. The next two lines contain the description of the right side of the equation. The first of these lines contains a positive integer r, which is the length of the right side of the equation. The second line contains the right side of the equation which is encoded in the same way as the left side. The number of digits plus sum of the lengths of variables (we count all appearances of variables) on each side of the equation is not greater than 10000.

Output

For each equation your program should output one line with the number of distinct solutions.

Example

Input:
1
5
4 2 4 4 2
5
1bad1
4
acbe

Output:
16

hide comments
DgenerationX: 2013-03-27 21:41:15

If long long is not enough then how could the answer be displayed?

Reply: Got AC. Since the answer is always a power of 2 displaying the answer is easy. My friends name is String.

Last edit: 2013-03-28 16:12:56
Raghavendran Ramachandran: 2012-08-25 04:58:57

Will the final answer fit in a long long?
Reply: No

Last edit: 2013-03-08 06:02:46
Daniel Ampuero: 2010-04-04 00:35:57

Are the test cases OK? I'm trying to submit a solution with Python and I always get RTE. Is the spacing and the lines being respected?

Yaicel Ge Proenza: 2009-06-30 04:05:15

could some one tell me if the length of the two words most be equal??

Yaicel Ge Proenza: 2009-06-30 02:46:38

The binary word of length 1, could be 0/1

~!(*(@*!@^&: 2009-04-17 15:47:46

check all case of no solution.


Added by:MichaƂ Czuczman
Date:2004-08-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:5th Polish Olympiad in Informatics, stage 2 (Wojciech Rytter)