Gem-Embedded Crab Strength Maximization

A king crab can trigger battle by inlaying gems. Each gem is characterized by an operation \(op\) and an integer \(v\). The operation is either addition or multiplication. The crab starts with an initial strength of \(0\). When a gem is embedded:

• If \(op = +\), the crab's strength increases by \(v\): \(x \to x + v\).
• If \(op = *\), the crab's strength is multiplied by \(v\): \(x \to x \times v\).

Note that \(v\) may be negative, so the order in which the gems are embedded can affect the final strength. Your task is to choose a permutation in which each gem is embedded exactly once so that the final strength is maximized.

Finally, output the maximum strength modulo \(998244353\) (i.e. ensure the answer is in the range \([0, 998244353)\)). In C++ style, if the answer is \(ans\), output \(((ans \% P) + P) \% P\) where \(P = 998244353\).

inputFormat

The first line contains a single integer \(n\) representing the number of gems.

Each of the following \(n\) lines contains an operation and an integer \(v\) separated by a space. The operation is either + or *.

outputFormat

Output a single integer: the maximum final strength modulo \(998244353\).

sample

2
+ 5
* 2

10