【题意】

括号序列是由左括号 ( 和右括号 ) 构成的字符串。平衡的括号序列要求 ( 和 ) 出现的次数一样多，而且每一个前缀中的 ( 的出现次数都不少于 ) 。最近，奶牛们定义了一种为平衡的括号序列计算分数的规则。

1、首先，如果只有一对括号 () ，则只算 $1$ 分;

2、其次，如果字符串 A 有 $s$ 分，那么字符串 (A) 有 $2s$ 分;

3、最后，如果字符串 A 有 $s$ 分，字符串 B 有 $t$ 分，那么字符串 AB 有 $s+t$ 分。

给定一个平衡的括号序列，请帮助奶牛来计算一下它的分数有多少吧，由于数字可能很大，只要输出答案模 $12345678910$ 的余数即可。

【输入格式】

第一行一个整数 $N(2 < N < 10^5)$。

下来 $N$ 个 $0$ 或 $1$ ，$0$ 代表左括号，$1$ 代表右括号，保证输入所表示的括号序列一定是平衡的。

【输出格式】

单个整数:表示括号序列的分数模 $12345678910$ 的余数。

【输入样例】

6
0
0
1
1
0
1

【输出样例】

3