問題
もけちゃんは現在整数 $0$ を持っています。
もけちゃんは $N$ 回にわたって以下に示す演算を行いました。
$i$ 回目 $(1 \leq i \leq N)$ に行った演算は以下の通りです。
- $operator_i$ が
+のとき: 現在持っている値に $A_i$ を足す。 - $operator_i$ が
-のとき: 現在持っている値から $A_i$ を引く。 - $operator_i$ が
*のとき: 現在持っている値に $A_i$ を掛ける。
もけちゃんが $N$ 回の演算を行った後持っている値を、$998244353$ で割った余りを求めてください。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $operator_1$ $A_1$ $operator_2$ $A_2$ $\vdots$ $operator_N$ $A_N$
出力
もけちゃんが $N$ 回の演算を行った後持っている値を、$998244353$ で割った余りを求めよ。
出力の末尾には改行を入れること。
制約
- $0 \leq N \leq 5 \times 10^5$
- $operator_i$ は
+,-,*のいずれかである。 - $-10^{18} \leq A_i \leq 10^{18}$
- $N, A_i$ は整数である。
入出力例
入力例１
3 + 6 * 10 - 4
出力例１
56
$1$ 回目: $0 + 6 = 6$
$2$ 回目: $6 \times 10 = 60$
$3$ 回目: $60 - 4 = 56$
入力例２
20 - 2480065053 * 1168033940 - -7566614986 * 2238231839 - 3828425094 * -8341480807 - 4657261640 + 5724127805 - 4404580933 + -4664759394 + -7249931195 * 7675895036 * 6851486131 + -9545880483 * -9984148954 + -4096613650 + -506703059 - 2662210897 * 3292453233 + 508675073
出力例２
914535375