题目描述

计算平衡字符串的分数，平衡字符串是指由相同数量的 $\texttt{(}$ 和 $\texttt{)}$ 组成，且以 $\texttt{(}$ 开头，以 $\texttt{)}$ 结尾的字符串。

计算规则：

• 字符串 $\texttt{()}$ 的得分是 $1$;
• 如果平衡字符串 $A$ 的得分是 $s(A)$，那么字符串 $\texttt{(}A\texttt{)}$ 的得分是 $2\times s(A)$；
• 如果 $A,B$ 的得分分别是 $s(A)$ 和 $s(B)$，那么平衡字符串 $AB$ 得分为 $s(A)+s(B)$。

例如：$s(\texttt{(())()})=s(\texttt{(())})+s(\texttt{()})=2\times s(\texttt{()})+1=2\times 1+1=3$。

输入格式

第 $1$ 行一个整数 $N$，表示平衡字符串长度。

第 $2\sim N+1$ 行：第 $i+1$ 行一个整数 $0$ 或 $1$，$0$ 代表字符 $\texttt{(}$，$1$ 代表 $\texttt{)}$。

输出格式

字符串的得分，结果对 $12345678910$ 取模。

6
0
0
1
1
0
1

3

样例解释

样例对应字符串 $\texttt{(())()}$。

数据范围

对于 $100\%$ 的数据，$2\leq N\leq 10^5$。