問題文

長さ$N$の,自然数ないしは記号$\{+, -, *\}$のみから構成される文字列が与えられる.(要素間は空白区切り)

なお,$\{+, -, *\}$は順に加算,減算,乗算の演算子であるものとする.

全ての連続部分列(全てで$\frac{N(N+1)}{2}$個)に対して以下の評価値を求め,その総和を$2 ^ {30}$で割ったあまりを求めよ.

その文字列を逆ポーランド記法として評価した際

・正しい評価式であるならば得られる演算結果

・不正な評価式であるならば0

制約

・$1\le N \le 5000$

・文字列の要素について以下が成り立つ.

・数値である場合$1 \le x \le 10 ^ 9$をみたす.

・文字列である場合それは$\{+, -, *\}$のいずれかである.

入力

入力は以下の形式で与えられる.

N
c1 c2 ... c_N

出力

全ての連続部分文字列に対しての評価値(上記参照)を求め

その総和を$2^{30}$で割ったあまりを求めよ.

ただし,数字$1$つから構成される文字列は有効な記法と解釈することに注意せよ.

サンプル

7
3 1 + 4 1 - *

28

考えうる部分列のうち,逆ポーランド記法として評価したとき有効なものは全てで$7$つ存在し, その全てについて評価値を計算すると以下のようになる.

$[3] = 3$

$[3, 1, +] = 4$

$[3, 1, +, 4, 1, -, *] = 12$

$[1] = 1$

$[4] = 4$

$[4, 1, -] = 3$

$[1] = 1$

したがって,その総和である$28$を出力する.

9
+ - * + - * - - *

0

この場合,全ての部分列が誤りである.

3
* * 4

4

この場合,有効な評価式は$[4]$だけである.

22
3 1 4 1 * 5 - 9 2 6 * 5 3 * 5 - 8 * 9 7 - 9

199

10
3 1 * 4 15926535 * 8 + 979 *

234632921

$2^{30}$で割ったあまりを求めることに注意.