[BalticOI 2012 Day1] 括号

一个合法括号序列的定义如下： - () 和 [] 是合法括号序列 - 若 A 是合法括号序列，则 (A) 和 [A] 也是合法括号序列 - 若 A 和 B 都是合法括号序列，则 AB 也是合法括号序列 在包含至少一对方括号的合法括号序列中，我们可以将 [ 和 ] 都用 ( 代替，这样就能够得到一个不合法括号序列。 例如 (( 和 ((((())) 都是不合法括号序列，前者可以由合法括号序列 \[] 转化而来，后者可以通过 \[]((()))，(\[](()))，((\[]())) 和 (((\[]))) 这四种合法括号序列转化而来。 现在给出一个不合法括号序列，求有多少种合法括号序列，在将其中的方括号用 ( 代替后，可以得到给定的括号序列。

第一行一个正整数 $n$，表示给出的不合法括号序列的长度。 第二行一个长度为 $n$ 的字符串，代表给出的序列，只包含 ( 和 )。

输出符合要求的合法括号序列总数对 $10^9+9$ 取模后的结果。

4
((()

2

8
((((((((

14

**【样例解释#1】** 满足条件的合法括号序列有两种：\[]() 和 ([])。 **【数据范围】** - 对于 20% 的数据，满足 $n \leq 50$ - 对于 50% 的数据，满足 $n \leq 1000$ - 对于 100% 的数据，满足 $2\leq n \leq 30000$ **【说明】** 译自 [BalticOI 2012 Day1 T1. Brackets](http://www.boi2012.lv/data/day1/eng/brackets.pdf)