**13 人解决**，24 人已尝试。

**27 份提交通过**，共有 165 份提交。

**6.5** EMB 奖励。

**单点时限: **2.0 sec

**内存限制: **256 MB

```
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

**13 人解决**，24 人已尝试。

**27 份提交通过**，共有 165 份提交。

**6.5** EMB 奖励。

题目标签