Binary Equation

A binary equation is an equation of the form

where each X_i and Y_j (with \(1\le i\le n\) and \(1\le j\le m\)) is either a binary digit (0 or 1) or a variable represented by a lowercase letter. Every variable represents a fixed-length binary code. To solve the binary equation, one must assign a binary string (of the predetermined length for that variable) to every variable so that after replacing the variables in the equation with their corresponding binary codes (thus both sides become binary strings), the equality holds.

The task is to compute how many distinct assignments of binary codes to the variables lead to a valid equation. It is guaranteed that there are at most 26 different variables (corresponding to the 26 lowercase English letters), and the total length of the digits plus the sum of the lengths of the variables on each side of the equation does not exceed 10,000.

inputFormat

The input consists of multiple lines:

1. The first line contains the binary equation in the form A=B without spaces. Here, A and B are sequences consisting of binary digits ('0' or '1') and variables (lowercase letters).
2. The second line contains an integer k representing the number of distinct variables that appear in the equation.
3. Each of the following k lines contains a variable (a lowercase letter) and an integer representing its fixed binary code length. The two values are separated by a space.

Note: When a variable appears in the equation, it should be replaced by its entire binary code (of the given fixed length). The overall length of the expanded left-hand side and right-hand side (i.e. counting each literal digit as length 1 and each occurrence of a variable as its fixed length) must be equal for the equation to have any solution.

outputFormat

Output a single integer representing the number of valid assignments of binary codes to the variables that make the equation hold. If there is no valid assignment, output 0.

sample

a1=1a
1
a 1

1