题目描述

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

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

• 如果一对括号中没有其他括号，如：()，那么防御能力得分为 $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

数据范围

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

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

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