P10079 [GDKOI2024 Junior] EX Infix Expression

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$.

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.

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

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