Best Parenthesis

Recently the cows have been competing with strings of balanced parentheses, comparing them to see whose string is best.

A balanced parenthesis string is scored by the following rules (every string considered here is balanced):

• The string () has score $1$.
• If a string A has score $s(A)$, then (A) has score $2 \cdot s(A)$.
• If strings A and B have scores $s(A)$ and $s(B)$, then their concatenation AB has score $s(A) + s(B)$.

For example, $s(\text{(())()}) = s(\text{(())}) + s(\text{()}) = 2 \cdot s(\text{()}) + 1 = 2 \cdot 1 + 1 = 3$.

Bessie wants to beat every other cow, so she must be able to compute the score of a given string. Given a balanced parenthesis string of length $N$ ($2 \le N \le 100{,}000$), compute its score.

• Line 1: a single integer $N$.
• Lines 2 to $N+1$: line $i+1$ contains one integer describing the $i$-th character of the string — $0$ if it is (, or $1$ if it is ).

• Line 1: the score of the string. Because this value can be very large, output it modulo $12345678910$.

The input encodes the string one character at a time: each value $0$ means an opening parenthesis ( and each value $1$ means a closing parenthesis ). Concatenate these characters in order to reconstruct the original string, then apply the scoring rules.