题目描述

给定一个合法的括号字符串，其得分按照以下规则计算：

• () 的得分为 $1$。
• 如果合法括号字符串 $A$ 的得分为 $x$，那么 (A) 的得分为 $2x$。
• 如果合法括号字符串 $A$ 和 $B$ 的得分分别为 $x$ 和 $y$，那么连接得到的字符串 AB 的得分为 $x+y$。

请计算给定括号字符串的得分。由于答案可能很大，输出答案除以 $12345678910$ 的余数。

输入格式

第一行包含一个整数 $n$，表示括号字符串的长度。

第二行包含一个长度为 $n$ 的字符串 $s$，字符串只包含字符 ( 和 )，并保证 $s$ 是合法的括号字符串。

输出格式

输出一个整数，表示括号字符串的得分除以 $12345678910$ 的余数。

样例

6
(())()

3

10
((()))()()

6

数据范围与提示

• 对于 $30\%$ 的数据，$2 \le n \le 20$
• 对于 $60\%$ 的数据，$2 \le n \le 1000$
• 对于 $100\%$ 的数据，$2 \le n \le 10^5$
• $n$ 为偶数