小马要做最棒的牛

题目描述

小田的农场开始了一年一度的评分，每头牛都得到了一个字符串来作为它们今年的评分，谁评分最高谁就是最棒的牛。

字符串中只包含左右括号，计分规则如下：

• 如果一对括号里没有括号，那么这对括号的得分为 $1$。
• 如果两对括号并列存在，互不包含，那么在计算得分时它们的分数相加。
• 如果括号内包含其他括号，那么这个括号的得分是它包含的括号的总分乘 $2$。

小田知道你看不懂上面的规则，所以他贴心的为你准备了样例：

()()，这两对括号是并列存在，且每对括号的得分都是 $1$，所以总分为 $2$。

(()())()，内部的两个括号总分是 $2$，因为外层括号包括了它们，所以 (()()) 的得分是 $4$，再加上右边单独的括号，总分是 $5$。

小马作为小田农场里最勤劳的牛，它想知道自己会不会被评为最优秀的，但它实在不会算这个评分，所以需要你帮帮他。

告诉你小马得到的字符串，请你帮它计算它的得分。

输入描述

第一行输入一个正整数 $n$，表示字符的数量。

第二行输入 $n$ 个数字，数字只会有 0 和 1，其中 0 表示 (，1 表示 )。

输出描述

输出包含一行一个整数，表示最终的答案。

因为答案可能很大，所以结果需要对 12345678910 取模。

输入输出样例

输入 #1

6
0 0 1 1 0 1

输出 #1

3

说明/提示

【样例 1 解释】

其对应的字符串为 (())()，得分为 $3$。

【数据范围】

对于 $5\%$ 的数据，括号不会互相包含。

对于 $10\%$ 的数据，括号会层层包含，形如 (())。

$1 \le n \le 10 ^ 5$。