题目描述

给定一个只包含左右括号的字符串，得分规则如下：

如果一对括号内没有括号，那么这对括号的得分为1；如果两对括号互不包含（即并列存在），那这两对括号的得分相加；如果括号内包含一对括号，那么这个括号的得分纪为内部括号序列的得分 $\times 2$。

例如：对于这样一个字符串：() ()，两对括号并列存在，则得分为 $1+1=2$;

而对于这样一个字符串：(())，最外层的括号内层包含一对括号，则得分为 $2 \times 1 = 2$。

Bessie 想击败所有同事的牛，所以她需要计算某个字符串的评分。给定一个长度为 $n$ 、只包含括号的字符串（$2 \le N \le 100000$），计算其得分帮助 Bessie。

输入格式

第一行，输入一个整数 $n$。
接下来 $n$ 行，每行一个数字，如果是 $0$，表示这个字符是 (；如果是 $1$，表示这个字符串是 )。

输出格式

字符串的分数，由于数字可能会变得很大，所以对 $12345678910$ 取模。

6 
0 
0 
1 
1 
0 
1 

3 

提示

样例的字符串是 (())()。