Background

2024GDKOI pj day2

Description

Alice 最近学习了表达式，现在他想写一个属于自己的表达式计算器。

规定：

• 单个数字：由若干数字（至少一个）连续拼接，最后必须跟一个’.’ 字符（不含引号）例如：00123. 0. 789.

都是合法的数字

• 单个操作符：由若干数字连续拼接，最后跟一个字符

• 操作符的字符：表示该操作符的操作。该字符必须是 +、∗、^ 之一，分别表示加法，乘法和乘方。特别

约定 0^0 = 1。

例如：000000789+,123^，如果前面的数值合法，那么它们就都是合法的操作符

• 操作符的数字：表示该操作符的优先级，优先级的取值是 [1, n] 之间的正整数，数字越大表示优先级越

高。

• 对于优先级相同的操作符，题目将给出一个长度为 n 的 01 串 C，用于说明对应优先级的操作符之间，

是左结合还是右结合。

其中 0 表示左结合，1 表示右结合。

例如 C=”111011”，其中第 4 个字符为’0’，表示优先级为 4 的操作符是左结合的。

• 左结合：表示该运算符从左往右计算。下面给出左结合的例子：1.4+2.4^3.4^4. 等价于 ((1.4+2.)4^3.)4^4，

其结果与 ((1 + 2)^3)^4 相同

• 右结合：表示该运算符从右往左运算。下面给出右结合的例子：1.6+2.6^3.6^4. 等价于 1.6+(2.6^(3.6^4.))

, 其结果与 1 + (2^(3^4)) 相同.

• 中缀表达式：

1. 单个数字是合法的中缀表达式
2. 若 A 是合法的中缀表达式，则 (A) 也是合法的中缀表达式
3. 若 A、B 均是合法的中缀表达式，c 是合法的单个操作符，则 AcB 也是合法的中缀表达式
4. 其余情况均不合法

现在给出一个长度为 n 的 01 串 C，用于说明，相同优先级的操作符之间，是左结合还是右结合。

给出一个中缀表达式，判断该表达式是否合法，不合法则输出”error”（不包括引号），合法则输出该表达

式的值对 998244353 取模的结果。

Format

Input

第一行一个正整数 n。

第二行一个长度为 n 的 01 串 C。

第三行一个字符串 S，表示一个中缀表达式。

保证表达式中不会存在空格

Output

若中缀表达式不合法则输出”error”，否则输出该表达式的值对 998244353 取模的结果。

Samples

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

243640717

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

Limitation

特殊性质 1：不会出现 ^ 字符。

特殊性质 2：不会出现 + 和 ∗ 字符。

特殊性质 3：不会出现 ( 和 )。

对于 8% 的数据，n = 1,1 ≤ |S| ≤ 100, 且满足特殊性质 1 和特殊性质 3。

对于另外 8% 的数据，n = 1,1 ≤ |S| ≤ 100, 且满足特殊性质 1。

对于另外 20% 的数据，n = 1,1 ≤ |S| ≤ 100, 且满足特殊性质 2 和特殊性质 3。

对于另外 24% 的数据，n = 1,1 ≤ |S| ≤ 1000, 且满足特殊性质 2。

对于 100% 的数据，1 ≤ n ≤ 9,1 ≤ |S| ≤ 10000。