#P3300. [USACO2011 Feb]Best Parenthesis

    ID: 2489 传统题 1000ms 256MiB 尝试: 366 已通过: 152 难度: 3 上传者: 标签>难度分类普及-数据结构栈模拟与实现技巧直接模拟数论同余的加减乘运算CF1200Silver

[USACO2011 Feb]Best Parenthesis

题目描述

奶牛们在比拼合法括号串的得分。一个合法括号串中的括号能按通常的规则全部配对。它们用以下规则计分。

  • () 的得分为 11。
  • 如果合法括号串 AA 的得分是 s(A)s(A),用一对括号将它完整包住后,所得字符串的得分为 2s(A)2s(A)。
  • 两个合法括号串 A,BA,B 顺次拼接得到 ABAB,得分为 s(A)+s(B)s(A)+s(B)。

例如,(())() 由 (()) 和 () 拼接而成,得分为 2⋅1+1=32\cdot1+1=3。

贝茜给出一个长度为 NN 的合法括号串。求它的得分。

输入格式

从标准输入读取。第一行是长度 NN。接下来 NN 行,每行一个整数,第 ii 项用 00 表示左括号,用 11 表示右括号。

输出格式

向标准输出写入。输出一行一个整数,表示得分对 1234567891012345678910 取模后的值。

样例 1

6
0
0
1
1
0
1
3

样例说明

输入表示括号串 (())()。

数据范围

2≤N≤1000002\le N\le100000。