在计算机的世界里，住着各类字符居民。一天，计算机病毒来袭。居民们要抓紧修筑防御工事，严防病毒冲破工事，破坏计算机世界。
字符居民们使用英文的小括号 ( 和 ) 修筑防御工事，防御工事的防御能力计算方式如下：
如果一对括号中没有其他括号，如： () ，那么防御能力得分为 1 分。
如果一对括号中包含了一个合法的括号子串 A ，那么防御能力得分 = 括号子串 A 的得分 \times 2 ，比如 (()) 的得分为 1 \times 2 = 2 分。
如果一个合法的括号子串 A 和另一个合法的括号子串 B 是并列关系，那么防御能力得分 = A 的得分 + B 的得分。比如 ()(()) 的得分为 1+2=3 分。
现给出长度为 N 的仅包含英文小括号组成的防御工事，请计算该防御工事的防御能力最终得分。
由于防御工事得分可能特别大，请输出得分 \mod 12345678910 的结果。
第 1 行，输入一个整数 N 表示英文小括号的长度。
第 2 行，输入 N 个括号字符。
请注意：本题测试数据确保读入的括号字符串一定是合法嵌套的，不会出现类似：)(，(()(，()()) 这一类的错误嵌套的情况。
输出得分 \mod 12345678910 的结果。
6 (())()
3
10 ((()))()()
6
22 ((((((())))))(((()))))
80
样例 1 输入 (())() 其中 (()) 得分为 2 分，最右侧的 () 得分为 1 分，共计 3 分。
对于 30\% 的数据，满足：2 \le N \le 20。
对于 60\% 的数据，满足：2 \le N \le 1000。
对于 100\% 的数据，满足：2 \le N \le 100000。