题目描述

在计算机的世界里，住着各类字符居民。一天，计算机病毒来袭。居民们要抓紧修筑防御工事，严防病毒冲破工事，破坏计算机世界。

字符居民们使用英文的小括号 ( 和 ) 修筑防御工事，防御工事的防御能力计算方式如下：

1. 如果一对括号中没有其他括号，如： () ，那么防御能力得分为 $1$ 分。

2. 如果一对括号中包含了一个合法的括号子串 $A$ ，那么防御能力得分 $=$ 括号子串 $A$ 的得分 $\times 2$ ，比如 (()) 的得分为 $1 \times 2 = 2$ 分。

3. 如果一个合法的括号子串 $A$ 和另一个合法的括号子串 $B$ 是并列关系，那么防御能力得分 $=$ $A$ 的得分 $+$ $B$ 的得分。比如 ()(()) 的得分为 $1+2=3$ 分。

现给出长度为 $N$ 的仅包含英文小括号组成的防御工事，请计算该防御工事的防御能力最终得分。

由于防御工事得分可能特别大，请输出得分 $\mod 12345678910$ 的结果。

输入格式

第 $1$ 行，输入一个整数 $N$ 表示英文小括号的长度。

第 $2$ 行，输入 $N$ 个括号字符。

**请注意：**本题测试数据确保读入的括号字符串一定是合法嵌套的，不会出现类似：)(，(()(，()()) 这一类的错误嵌套的情况。

输出格式

输出得分 $\mod 12345678910$ 的结果。

样例输入 #1

6 
(())()

样例输出 #1

3

样例输入 #2

10
((()))()()

样例输出 #2

6

样例输入 #3

22
((((((())))))(((()))))

样例输出 #3

80

数据范围

样例 $1$ 解释

样例 $1$ 输入 (())() 其中 (()) 得分为 $2$ 分，最右侧的 () 得分为 $1$ 分，共计 $3$ 分。

数据范围

对于 $30\%$ 的数据，满足：$2 \le N \le 20$。

对于 $60\%$ 的数据，满足：$2 \le N \le 1000$。

对于 $100\%$ 的数据，满足：$2 \le N \le 100000$。