注意

この問題は多倍長整数の使用を想定しています。
多倍長整数の計算の速度差を問うことがこの問題の目的ではないため、想定解を作るにあたって作成した多倍長整数を扱う簡単なライブラリ (C++) を GitHub にアップロードしました。
想定解はこのライブラリを用いて書かれており、想定解の実行時間は 920 ms です。

問題文

以下の BNF (バッカス・ナウア記法) において <expression> にあたる長さ $N$ の数式 $S$ が与えられます。計算してください。

<nonzero_digit> ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
<digit> ::= '0' | <nonzero_digit>
<positive_number> ::= <nonzero_digit> | <positive_number> <digit>
<number> ::= '0' | <positive_number> | '-' <number> 
<factor> ::= <number> | '(' <expression> ')'
<term> ::= <factor> | <term> '*' <factor>
<expression> ::= <term> | <expression> '+' <term> | <expression> '-' <term>

入力

入力は以下の形式で標準入力から与えられます。

$N$
$S$

出力

計算結果を標準出力に $1$ 行で出力してください。
最後に改行してください。

制約

入力は以下の制約を満たします。

• $1 \leq N \leq 10^6$
• $S$ は長さ $N$ の文字列である。
• $S$ は問題文中の BNF における <expression> である。
• $N$ は整数である。

サンプル

10
-74+5+59-7

-17

10
28*299+-99

8273

15
((8+26))*(92*9)

28152

15
-9659*(----1)-7

-9666

50
4-(((6160)))-((4*8967+6194-581))*1602893-3300-35-7

-66489614031