#描述#
Recently, the cows have been competing with strings of balanced
parentheses and comparing them with each other to see who has the
best one.
<BR>
<BR>
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.
<BR>
<BR>
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 ')'

##输出格式##
* Line 1: The score of the string. Since this number can get quite
large, output the score modulo 12345678910.

#样例1#
##样例输入1##

6
0
0
1
1
0
1

##样例输出1##

3

#限制#
1000ms
32768KB

#提示#

#来源#