Polish version    English version  
  History of OI -> V OI 1997/1998 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
Stage III - results
Stage II - results
Stage I - results
Problems
Regulations
Schedule
Stats
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
V Olimpiada Informatyczna 1997/1998

Task: ROW
Author: Wojciech Rytter
Word equations

II stage contest  

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.

Task

Write a program, that

  • reads the number of equations and their descriptions from the text file PRO.IN;
  • finds the number of solutions of every equation;
  • writes the results to the text file ROW.OUT.

Input

In the first line of the input file ROW.IN there is an integer x, 1 <= x <= 5, which denotes the number of equations. The following lines contain descriptions of x equations. Each description consists of 6 lines. There are no empty lines between descriptions. Each 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 every i, 1 <= i <= x, your program should write the number of distinct solutions of the i-th equation to the i-th line of the output file ROW.OUT.

Example

For the text file ROW.IN:

1
5
4 2 4 4 2
5
1bad1
4
acbe
the correct result is the output file ROW.OUT: :
16




Print friendly version