Recently, the cows have been competing with strings of balanced parentheses and comparing them with each other to see who has the best one.</p>

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 2s(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("()") = 2s("()")+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 ')'

출력 형식

• Line 1: The score of the string. Since this number can get quite large, output the  score modulo 12345678910.

예제 입력

6
0
0
1
1
0
1

예제 출력

3

힌트

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