Problem Description

An equation of the form:

X1X2…Xn = Y1Y2..Ym

is called a binary equation.

On both sides of the binary equation, Xi and Yj (1 <= i <= n; 1 <= j <= m) are either binary digits (0, 1) or variables (lowercase letters). Each variable is a binary code of a fixed length, which can replace the variable's position in the equation, and this length is called the variable's length. To solve a binary equation, appropriate binary codes need to be assigned to the variables such that when they replace the corresponding variables in the equation (both sides become binary codes), the equation holds true.

Programming Task:

For each given equation, calculate the total number of solutions. It is known that there are at most 26 variables (26 lowercase English letters), and the sum of the lengths of the digits and variables on each side of the equation does not exceed 10000.

Input Format

The first line: k (k <= 26, the number of variables, using the first k lowercase English letters as variables, e.g., if k = 5, then the variables are a, b, c, d, e).

The second line: k positive integers separated by a space, representing the lengths of the k variables in order.

The third line: the expression on the left side of the equation.

The fourth line: the expression on the right side of the equation.

Output Format

The total number of solutions for the variables in the equation.

Sample Input and Output

Sample Input #1

2
4 2
1b1
a

Sample Output #1

4

Sample Input #2

5
4 2 4 4 2
1bad1
acbe

Sample Output #2

16

Notes

Sample 1: There are 4 solutions

1. a = 1001; b = 00
2. a = 1011; b = 01
3. a = 1101; b = 10
4. a = 1111; b = 11

Sample 2: k = 5, variables: a, b, c, d, e. Lengths are: 4, 2, 4, 4, 2. The equation is: 1bad1 = acbe

Output 16, meaning there are 16 solutions for variables a, b, c, d, e.

见题面 Input 部分

见题面 Output 部分