我们按照如下方式定义合法括号序列：
()和[]是合法括号序列；- 如果
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 分。