Description

An equality of the form:

$$\overline{X_1X_2\dots X_n}= \overline{Y_1Y_2\dots Y_m}$$

is called a binary equation.

On both sides of a binary equation, each $X_i$ and $Y_j$ ($1 \le i \le n$ and $1 \le j \le m$) is either a binary digit $0$ or $1$, or a variable (a lowercase letter). Each variable represents a binary string of fixed length; this length is called the length of the variable. To solve a binary equation, we assign suitable binary strings to the variables so that, after replacing the variables with their strings (so both sides become binary strings), the equality holds.

Programming task:

For each given equation, compute how many solutions there are in total.

Input Format

The input consists of four lines.

Line 1: $k$, the number of variables. The variables are the first $k$ lowercase English letters (for example, if $k=5$, then the variables are $a, b, c, d, e$).

Line 2: $k$ positive integers separated by a single space, giving the lengths of the $k$ variables in order.

Line 3: the expression on the left-hand side of the equation.

Line 4: the expression on the right-hand side of the equation.

Output Format

A single integer, the total number of solutions for the variables that appear in the equation.

2
4 2
1b1
a

4

5
4 2 4 4 2
1bad1
acbe

16

Hint

Explanation for Sample 1

There are $4$ solutions, as follows:

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

Explanation for Sample 2

$k=5$, so the variables are $a, b, c, d, e$, with lengths: $4\space 2\space 4\space 4\space2$. The equation is $\overline{1bad1}=\overline{acbe}$.

Therefore, the output is $16$, meaning there are $16$ solutions for the variables $a, b, c, d, e$.

Constraints

$k \le 26$, because there are at most $26$ variables (the $26$ lowercase English letters).

On each side of the equation, the sum of the lengths of digits and variables does not exceed $10000$.

Translated by ChatGPT 5