该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

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

题目描述

帝王蟹可以通过镶嵌宝石触发战斗，不同的宝石效果不同，但奇特的是，镶嵌宝石的顺序有时也会影响它的强度。

帝王蟹有一个初始为 $0$ 的强度值，每个宝石有属性 $op$ 和 $v$，表示：

• 若 $op$ 为 +，则镶嵌后帝王蟹的强度值将会加上 $v$；

• 若 $op$ 为 *，则镶嵌后帝王蟹的强度值将会乘上 $v$。

由于宝石的效果十分奇异，所以 $v$ 可能是负数。

作为一个有挑战精神的冒险者，你希望采取某种镶嵌方式，将每个宝石都镶嵌恰好一遍，且使得帝王蟹的强度值最大。

你只需要输出最大的强度值对 $998244353$ 取模的结果，注意这是一个 $[0, 998244353)$ 中的数。

也就是说，如果答案为 ans，按照 C++ 语法，你需要输出 (ans % P + P) % P，其中 P = 998244353。

输入格式

第一行，一个整数 $n$，表示宝石数量。

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

输出格式

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

3
+ -3
+ 4
* -4

16

3
+ -3
+ -4
* 4

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）：无特殊限制。