Problem Description

Alice has recently been learning about expressions, and now he wants to write his own expression calculator.

Rules:

• A single number: formed by concatenating several digits (at least one), and it must end with a . character (without quotes). For example, 00123. 0. 789. are all valid numbers.
• A single operator: formed by concatenating several digits, and then ending with one character.
• The operator character: represents the operation of this operator. This character must be one of +, *, ^, representing addition, multiplication, and exponentiation, respectively. It is specially defined that 0^0=1.
  For example, 000000789+, 123^. If the preceding numeric value is valid, then they are valid operators.
• The digits of an operator: represent the precedence of this operator. The precedence is a positive integer in $[1, n]$. A larger number means higher precedence.
• For operators with the same precedence, the problem provides a $01$ string $C$ of length $n$ to indicate whether operators of that precedence are left-associative or right-associative.
  Here, 0 means left-associative, and 1 means right-associative.
  For example, if $C=111011$, then the $4$-th character is 0, meaning operators with precedence $4$ are left-associative.
• Left-associative: means the operator is evaluated from left to right. Example: 1.4+2.4^3.4^4. is equivalent to ((1.4+2.)4^3.)4^4., and its result is the same as ((1+2)^3)^4.
• Right-associative: means the operator is evaluated from right to left. Example: 1.6+2.6^3.6^4. is equivalent to 1.6+(2.6^(3.6^4.)), and its result is the same as 1+(2^(3^4)).
• Infix expression:
  1. A single number is a valid infix expression.
  2. If $A$ is a valid infix expression, then $(A)$ is also a valid infix expression.
  3. If $A$ and $B$ are both valid infix expressions, and $c$ is a valid single operator, then $AcB$ is a valid infix expression.
  4. All other cases are invalid.

Now a $01$ string $C$ of length $n$ is given to specify, for operators with the same precedence, whether they are left-associative or right-associative.

Given an infix expression, determine whether it is valid. If it is invalid, output error (without quotes). If it is valid, output the value of the expression modulo $998244353$.

Input Format

The first line contains a positive integer $n$.

The second line contains a $01$ string $C$ of length $n$.

The third line contains a string $S$, representing an infix expression.

It is guaranteed that there are no spaces in the expression.

Output Format

If the infix expression is invalid, output error. Otherwise, output the value of the expression modulo $998244353$.

2
01
1.2+2.1^3.2*4.2^(5.2*6.)2+7.

243640717

Hint

Sample Explanation

243640717 = ((1+2)^(3*(4^((5*6)+7)))) mod 998244353

Constraints

Special Property 1: The ^ character will not appear.

Special Property 2: The + and * characters will not appear.

Special Property 3: The ( and ) characters will not appear.

For $8\%$ of the testdata, $n = 1$, $1 \leq |S| \leq 100$, and Special Property $1$ and Special Property $3$ hold.

For another $8\%$ of the testdata, $n = 1$, $1 \leq |S| \leq 100$, and Special Property $1$ holds.

For another $20\%$ of the testdata, $n = 1$, $1 \leq |S| \leq 100$, and Special Property $2$ and Special Property $3$ hold.

For another $24\%$ of the testdata, $n = 1$, $1 \leq |S| \leq 1000$, and Special Property $2$ holds.

For $100\%$ of the testdata, $1 \leq n \leq 9$, $1 \leq |S| \leq 10000$.

Translated by ChatGPT 5