我们按照如下方式定义合法括号序列：

• () 和 [] 是合法括号序列；
• 如果 A 是合法括号序列，则 (A) 和 [A] 也是合法括号序列；
• 如果 A 和 B 都是合法括号序列，则它们的拼接 AB 也是合法括号序列。

在一个包含至少一对方括号（[ 及其对应的 ]）的合法括号序列中，每一个方括号（无论是开括号还是闭括号）都被替换为了开圆括号 (，从而得到了一个损坏的括号序列。

例如，(( 和 (((((())) 都是损坏的括号序列。第一个序列可以由合法括号序列 [] 得到。第二个序列只能由以下四个合法括号序列之一得到：[]((()))、([](()))、(([]())) 或 ((([])))。

你的任务是：对于给定的损坏括号序列，计算可能得到该损坏序列的合法括号序列的数量。

输入格式

第一行包含一个偶数 $N$ ($2 \le N \le 30000$)，表示给定的损坏括号序列的长度。

第二行包含 $N$ 个字符 ( 和 )，表示给定的损坏括号序列。

输出格式

输出单行，包含一个整数，表示可能的合法括号序列的数量。由于答案可能很大，请将答案对 $1000000009$ 取模后输出。

样例

输入样例 1

4
((()

输出样例 1

2

样例说明 1

对应的合法括号序列为：[]()，([])。

输入样例 2

8
((((((((

输出样例 2

14

样例说明 2

对应的合法括号序列为：[][][][]，[[]][][]，[[]][[]]，[][][[]]，[[[]]][]，[[][]][]，[][[][]]，[][[[]]]，[[[[]]]]，[[][[]]]，[[[]][]]，[[][][]]，[[[][]]]，[][[]][]。

数据范围

• 评测用例满足 $N \le 50$ 的测试点积 20 分。
• 评测用例满足 $N \le 1000$ 的测试点积 45 分。