给定一个序列 $$$A$$$,其中元素的形式为 + x 或 -,其中 $$$x$$$ 是整数。
对于这样的序列 $$$S$$$,其元素采用 + x 或 - 的形式,定义 $$$f(S)$$$ 如下:
- 从第一个到最后一个迭代 $$$S$$$ 的元素,并在迭代时维护一个多重集 $$$T$$$。
- 对于每个元素,如果其形式为 + x,则将 $$$x$$$ 添加到 $$$T$$$;否则,删除 $$$T$$$ 中的最小元素(如果 $$$T$$$ 为空,则不执行任何操作)。
- 迭代所有 $$$S$$$ 的元素后,计算 $$$T$$$ 中所有元素的总和。 $$$f(S)$$$ 被定义为总和。
如果 $$$b$$$ 可以通过删除零个或多个元素而不改变剩余元素的顺序从 $$$a$$$ 导出,则序列 $$$b$$$ 是序列 $$$a$$$ 的子序列。对于所有 $$$A$$$ 的子序列 $$$B$$$,计算 $$$f(B)$$$ 的总和,以 $$$998\,244\,353$$$ 为模。
输入
第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 500$$$) — $$$A$$$ 的长度。
接下来的 $$$n$$$ 行均以运算符 + 或 - 开头。如果运算符是 +,则其后跟随一个整数 $$$x$$$ ($$$1\le x<998\,244\,353$$$)。这些 $$$n$$$ 行中的第 $$$i$$$ 行描述了 $$$A$$$ 中的第 $$$i$$$ 元素。
输出
打印一个整数,即问题的答案,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
4 - + 1 + 2 -
输出 #1
16
输入 #2
15 + 2432543 - + 4567886 + 65638788 - + 578943 - - + 62356680 - + 711111 - + 998244352 - -
输出 #2
750759115
注意
在第一个示例中,以下是所有可能的 $$$B$$$ 和 $$$f(B)$$$ 对:
- $$$B=$$$ {},$$$f(B)=0$$$。
- $$$B=$$$ {-},$$$f(B)=0$$$。
- $$$B=$$$ {+ 1, -}, $$$f(B)=0$$$。
- $$$B=$$$ {-, + 1, -}, $$$f(B)=0$$$。
- $$$B=$$$ {+ 2, -}, $$$f(B)=0$$$。
- $$$B=$$$ {-, + 2, -}, $$$f(B)=0$$$。
- $$$B=$$$ {-},$$$f(B)=0$$$。
- $$$B=$$$ {-, -}, $$$f(B)=0$$$。
- $$$B=$$$ {+ 1, + 2},$$$f(B)=3$$$。
- $$$B=$$$ {+ 1, + 2, -}, $$$f(B)=2$$$。
- $$$B=$$$ {-, + 1, + 2}, $$$f(B)=3$$$。
- $$$B=$$$ {-, + 1, + 2, -}, $$$f(B)=2$$$。
- $$$B=$$$ {-, + 1},$$$f(B)=1$$$。
- $$$B=$$$ {+ 1},$$$f(B)=1$$$。
- $$$B=$$$ {-, + 2},$$$f(B)=2$$$。
- $$$B=$$$ {+ 2},$$$f(B)=2$$$。
这些值的总和为 $$$16$$$。