2870. Best Parenthesis














Recently, the cows have been competing with strings of balanced

parentheses and comparing them with each other to see who has the

best one.

Such strings are scored as follows (all strings are balanced): the

string "()" has score 1; if "A" has score s(A) then "(A)" has score

2*s(A); and if "A" and "B" have scores s(A) and s(B), respectively,

then "AB" has score s(A)+s(B). For example, s("(())()") =

s("(())")+s("()") = 2*s("()")+1 = 2*1+1 = 3.

Bessie wants to beat all of her fellow cows, so she needs to calculate

the score of some strings. Given a string of balanced parentheses

of length N (2 <= N <= 100,000), help Bessie compute its score.

输入格式




















* Line 1: A single integer: N

* Lines 2..N + 1: Line i+1 will contain 1 integer: 0 if the ith

character of the string is '(',  and 1 if the ith character of

the string is ')'

输出格式














This corresponds to the string "(())()".

OUTPUT FORMAT:

* Line 1: The score of the string. Since this number can get quite

large, output the  score modulo 12345678910.

样例

Input
6
0
0
1
1
0
1

Output
3


11 人解决，22 人已尝试。

25 份提交通过，共有 162 份提交。

6.9 EMB 奖励。