珍珠帝王蟹(Crab King)

题目背景

在一次航程中,你偶然发现了被一片礁石环绕的帝王蟹,被月岛能量侵蚀的它又与月光有着怎样的联系呢?似乎只有击败它才能见分晓。

题目描述

帝王蟹可以通过镶嵌宝石触发战斗,不同的宝石效果不同,但奇特的是,镶嵌宝石的顺序有时也会影响它的强度。 帝王蟹有一个初始为 $0$ 的强度值,每个宝石有属性 $op$ 和 $v$,表示: - 若 $op$ 为 `+`,则镶嵌后帝王蟹的强度值将会加上 $v$; - 若 $op$ 为 `*`,则镶嵌后帝王蟹的强度值将会乘上 $v$。 由于宝石的效果十分奇异,所以 $v$ 可能是负数。 作为一个有挑战精神的冒险者,你希望采取某种镶嵌方式,将**每个宝石**都镶嵌**恰好一遍**,且使得帝王蟹的强度值最大。 你只需要输出最大的强度值对 $998244353$ 取模的结果,注意这是一个 $[0, 998244353)$ 中的数。 也就是说,如果答案为 `ans`,按照 C++ 语法,你需要输出 `(ans % P + P) % P`,其中 `P = 998244353`。

输入输出格式

输入格式


第一行,一个整数 $n$,表示宝石数量。 接下来 $n$ 行,每行有用空格隔开的一个字符 $op$ 和一个整数 $v$,描述一个宝石。

输出格式


输出一行一个整数,表示最大的强度值对 $998244353$ 取模的结果。

输入输出样例

输入样例 #1

3
+ -3
+ 4
* -4

输出样例 #1

16

输入样例 #2

3
+ -3
+ -4
* 4

输出样例 #2

998244346

说明

**【样例 1 解释】** 按照输入顺序以 $1, 2, 3$ 标记每个宝石,所有可能的镶嵌顺序如下: $1\to 2\to 3$:$x = ((0 + {\color{red}{-3}}) + {\color{red}{4}}) \times {\color{red}{-4}} = -4$; $1\to 3\to 2$:$x = ((0 + {\color{red}{-3}}) \times {\color{red}{-4}}) + {\color{red}{4}} = 16$; $2\to 1\to 3$:$x = ((0 + {\color{red}{4}}) + {\color{red}{-3}}) \times {\color{red}{-4}} = -4$; $2\to 3\to 1$:$x = ((0 + {\color{red}{4}}) \times {\color{red}{-4}}) + {\color{red}{-3}} = -19$; $3\to 1\to 2$:$x = ((0 \times {\color{red}{-4}}) + {\color{red}{-3}}) + {\color{red}{4}} = 1$; $3\to 2\to 1$:$x = ((0 \times {\color{red}{-4}}) + {\color{red}{4}}) + {\color{red}{-3}} = 1$。 因此,强度值的最大值为 $16$,对 $998244353$ 取模后为 $16$。 --- **【样例 2 解释】** 按照输入顺序以 $1, 2, 3$ 标记每个宝石,所有可能的镶嵌顺序如下: $1\to 2\to 3$:$x = ((0 + {\color{red}{-3}}) + {\color{red}{-4}}) \times {\color{red}{4}} = -28$; $1\to 3\to 2$:$x = ((0 + {\color{red}{-3}}) \times {\color{red}{4}}) + {\color{red}{-4}} = -16$; $2\to 1\to 3$:$x = ((0 + {\color{red}{-4}}) + {\color{red}{-3}}) \times {\color{red}{4}} = -28$; $2\to 3\to 1$:$x = ((0 + {\color{red}{-4}}) \times {\color{red}{4}}) + {\color{red}{-3}} = -19$; $3\to 1\to 2$:$x = ((0 \times {\color{red}{4}}) + {\color{red}{-3}}) + {\color{red}{-4}} = -7$; $3\to 2\to 1$:$x = ((0 \times {\color{red}{4}}) + {\color{red}{-4}}) + {\color{red}{-3}} = -7$。 因此,强度值的最大值为 $-7$,对 $998244353$ 取模后为 $998244346$。 --- **【数据范围】** **本题采用捆绑测试。** 对于全部测试数据:$1 \le n \le {10}^5$,$2 \le |v| \le {10}^6$。 - Subtask 1(26 points):$n \le 9$,$|v| \le 5$。 - Subtask 2(22 points):$v > 0$。 - Subtask 3(12 points):保证当 $op$ 为 `*` 时 $v > 0$。 - Subtask 4(15 points):保证当 $op$ 为 `+` 时 $v > 0$。 - Subtask 5(25 points):无特殊限制。 --- ![](https://cdn.luogu.com.cn/upload/image_hosting/rwzuwu9z.png)