P2456 [SDOI2006] Binary Equation

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.

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.

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

#### 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