题目描述

计算"平衡字符串"的分数，"平衡字符串"是指由相同数量的$\red{‘（’}$和$\red{‘）’}$组成， 且以$\red{‘（’}$开头，以$\red{‘）’}$结尾的字符串。

计算规则：

字符串$\red{"（）"}$的得分是$\red{1.}$

如果，平衡字符串"$\red{A}$"的得分是是$\red{S(A)，}$那么字符串"$\red{（A）}$"得分是$\red{2\times S(A) }$； 如果，"$\red{A}$"，"$\red{B}$" 得分分别是$\red{S(A)}$和$\red{S(B)，}$那么平衡字符串"$\red{AB}$"得分为$\red{S(A)+S(B)}$ 例如：$\red{s(}$"$\red{(())()}$"$\red{) =s(}$"$\red{(())}$"$\red{)+s(}$"$\red{()}$"$\red{) = 2\times s(}$"$\red{()}$"$\red{)+1 = 2\times 1+1 = 3.}$

输入格式

第$\red{1}$行：$\red{N，}$平衡字符串长度

第$\red{2}$至$\red{N+1}$行：$\red{Linei+1 }$整数$\red{0}$或$\red{1,0}$代表字符‘（’，$\red{1}$代表‘）’

输出格式

计算字符串得分，结果对$\red{12345678910}$取模

样例

输入样例

6
0
0
1
1
0
1

输出样例

3

提示

输入细节：

这对应于字符串"$\red{(())()}$"。