#P3300. [USACO2011 Feb]Best Parenthesis
[USACO2011 Feb]Best Parenthesis
题目描述
奶牛们在比拼合法括号串的得分。一个合法括号串中的括号能按通常的规则全部配对。它们用以下规则计分。
()的得分为 。- 如果合法括号串 的得分是 ,用一对括号将它完整包住后,所得字符串的得分为 。
- 两个合法括号串 顺次拼接得到 ,得分为 。
例如,(())() 由 (()) 和 () 拼接而成,得分为 。
贝茜给出一个长度为 的合法括号串。求它的得分。
输入格式
从标准输入读取。第一行是长度 。接下来 行,每行一个整数,第 项用 表示左括号,用 表示右括号。
输出格式
向标准输出写入。输出一行一个整数,表示得分对 取模后的值。
样例 1
6
0
0
1
1
0
1
3
样例说明
输入表示括号串 (())()。
数据范围
。