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 has score ;
- if has score then has score ;
- and if and have scores and , respectively, then has score .
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 , help Bessie compute its score.
Input
Line : A single integer: ;
Lines : Line will contain integer: if the -th character of the string is (
, and if the ith character of the string is )
.
Output
Line : The score of the string. Since this number can get quite large, output the score modulo .
6
0
0
1
1
0
1
3
Sample Explain 1
This corresponds to the string (())()
.
Data scale and Agreement
For data, .
Source
Silver