该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

附加文件

题目描述

本题中合法括号串的定义如下：

1. () 是合法括号串。
2. 如果 A 是合法括号串，则 (A) 是合法括号串。
3. 如果 A，B 是合法括号串，则 AB 是合法括号串。

例如，下面的字符串都是合法括号串：

()， (())， ()(())

而以下几个则不是：

(， )(， ())， ((()

定义如下计分规则：

1. () 的得分为 1
2. 如果 A 是合法括号串，则 (A) 的得分为 A 的得分乘以 2
3. 如果 A，B 是合法括号串，则 AB 的得分为 A 的得分加 B 的得分。

现在，给定一个仅由 (，) 构成的字符串 $A$，请你计算 $A$ 的得分。该得分可能很大，你需要将答案 mod 12345678910 后输出。

输入格式

输入第一行：一个正偶数 $n$ 表示字符串 $A$ 的长度。

接下来 $n$ 行，每行一个整数 0 或 1 ，为 0 代表 $A$ 当前字符为 (，为 1 代表 $A$ 当前字符为 ) 。数据保证 $A$ 是非空合法括号串。

输出格式

输出一行一个整数，表示字符串 $A$ 的得分 mod 12345678910。

样例输入

6 
0 
0 
1 
1 
0 
1

样例输出

3

数据范围

2 <= n <= 100,000