Tree Generators

Two expressions are given as input. Each one describes a procedure that generates a single tree. The procedure is randomized, so different trees may be generated each time it runs. Count the number of trees that can be generated from both expressions.

The syntax of an expression is as follows.

$E$ ::= ‘1’ | ‘(’ $E$ $E$ ‘)’

A tree is generated from an expression as follows.

• The expression 1 generates a tree with a single vertex labeled $1$.
• For two expressions $E_1$ and $E_2$, the expression ($E_1E_2$) generates a tree as follows.
  • Generate a tree $T_1$ from $E_1$ with $n_1$ vertices, and a tree $T_2$ from $E_2$ with $n_2$ vertices.
  • Increment the labels of all vertices in $T_2$ by $n_1$.
  • Choose one vertex from $T_1$ and one vertex from $T_2$ at random. Adding an edge between them forms a single tree with vertices labeled $1$ through $(n_1 + n_2)$. This is the tree generated by ($E_1E_2$).

For example, the expression (11) can generate only the leftmost tree in Figure D.1. The expression (1(11)) can generate the other two trees.

Figure D.1. Trees generated from the two expressions, (11) and (1(11))

The same tree can be generated from different expressions. The middle tree can also be generated from ((11)1).

For two expressions of the same length, count the trees that can be generated from both. The trees generated from the two expressions always have the same number of vertices. Two trees are different if there are two indices $i$ and $j$ such that vertices $i$ and $j$ are connected by an edge in one tree but not in the other.

The input consists of two lines. Each line contains one expression string. The two strings have the same length, between $1$ and $7 \times 10^5$, inclusive. Both strings follow the syntax given above.

Print the number of trees that can be generated from both expressions, modulo $998\,244\,353$.

For Sample Input 1, the trees that can be generated from the two expressions are shown in Figure D.2. The top six trees come from the first expression, and the bottom four come from the second. Only the leftmost tree in each row can be generated from both.

Figure D.2. Illustration of Sample Input 1