题目描述

最近，奶牛们一直在比拼平衡括号字符串，并比较它们的得分，以确定谁的字符串最好。

这样的字符串得分规则如下（所有字符串都是平衡的）：字符串 "()" 的得分为 1；如果 "A" 的得分为 $s(A)$，那么 "(A)" 的得分为 $2 \times s(A)$；如果 "A" 和 "B" 的得分分别为 $s(A)$ 和 $s(B)$，那么 "AB" 的得分为 $s(A) + s(B)$。例如，$s("(())()") = s("(())")+s("()") = 2 \times s("()")+1 = 2 \times 1+1 = 3$。

贝茜想要击败她所有的同伴奶牛，因此她需要计算一些字符串的得分。给定一个长度为 $N$ 的平衡括号字符串（$2 \leq N \leq 100,000$），请帮助贝茜计算它的得分。

输入格式

• 第 1 行：一个整数 $N$
• 第 2 到 $N+1$ 行：每行包含一个整数：如果字符串的第 $i$ 个字符是 '('，则为 $0$；如果字符串的第 $i$ 个字符是 ')'，则为 $1$

输出格式

• 第 1 行：字符串的得分。由于这个数可能非常大，输出时对 $12345678910$ 取模。

输入样例

6
0
0
1
1
0
1

输出样例

3

输入数据 1 说明

这对应着字符串 "(())()"。

数据范围

对于 $100\%$ 的数据，$2 \leq N \leq 100,000$。

提示

输出结果需要对 $12345678910$ 取模。