bzoj#P3300. [USACO2011 Feb] Best Parenthesis

[USACO2011 Feb] Best Parenthesis

Description

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 ()\texttt{()} has score 11;
  • if AA has score s(A)s(A) then (A)\texttt{(}A\texttt{)} has score 2×s(A)2\times s(A);
  • and if AA and BB have scores s(A)s(A) and s(B)s(B), respectively, then ABAB has score s(A)+s(B)s(A)+s(B).

For example, $s(\texttt{(())()})=s(\texttt{(())})+s(\texttt{()})=2\times s(\texttt{()})+1=2\times 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 NN, help Bessie compute its score.

Input

Line 11: A single integer: NN;

Lines 2N+12\sim N+1: Line i+1i+1 will contain 11 integer: 00 if the ii-th character of the string is (, and 11 if the ith character of the string is ).

Output

Line 11: The score of the string. Since this number can get quite large, output the score modulo 1234567891012345678910.

6
0
0
1
1
0
1
3

Sample Explain 1

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

Data scale and Agreement

For 100%100\% data, 2N1052\leq N\leq 10^5.

Source

Silver