Background

During a voyage, you accidentally discover a king crab surrounded by reefs. After being eroded by Moon Island energy, what connection does it have with moonlight? It seems that only by defeating it can you find out.

Problem Description

The king crab can be challenged by embedding gems. Different gems have different effects, but strangely, the order in which the gems are embedded sometimes also affects its strength.

The king crab has a strength value initially equal to $0$. Each gem has attributes $op$ and $v$, meaning:

• If $op$ is +, then after embedding, the king crab’s strength value will increase by $v$.
• If $op$ is *, then after embedding, the king crab’s strength value will be multiplied by $v$.

Because the gems’ effects are very strange, $v$ may be negative.

As an adventurer who loves challenges, you want to choose an embedding order such that each gem is embedded exactly once, and the king crab’s strength value is maximized.

You only need to output the maximum strength value modulo $998244353$. Note that this is a number in $[0, 998244353)$.

That is, if the answer is ans, in C++ syntax you need to output (ans % P + P) % P, where P = 998244353.

Input Format

The first line contains an integer $n$, representing the number of gems.

The next $n$ lines each contain a character $op$ and an integer $v$ separated by a space, describing a gem.

Output Format

Output one integer on one line, representing the maximum strength value modulo $998244353$.

3
+ -3
+ 4
* -4

16

3
+ -3
+ -4
* 4

998244346

Hint

[Sample 1 Explanation]

Following the input order, label the three gems as $1, 2, 3$. All possible embedding orders are:

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

Therefore, the maximum strength value is $16$, and after taking modulo $998244353$ it is $16$.

[Sample 2 Explanation]

Following the input order, label the three gems as $1, 2, 3$. All possible embedding orders are:

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

Therefore, the maximum strength value is $-7$, and after taking modulo $998244353$ it is $998244346$.

[Constraints]

This problem uses bundled testdata.

For all testdata: $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): Guarantee that when $op$ is *, $v > 0$.
• Subtask 4 (15 points): Guarantee that when $op$ is +, $v > 0$.
• Subtask 5 (25 points): No special constraints.

Translated by ChatGPT 5