「BalticOI 2012 Day1」括号

译自 BalticOI 2012 Day1 T1. Brackets

题目描述

一个正规括号序列的定义如下：

1. () 和 [] 是正规括号序列；
2. 若 $A$ 是正规括号序列，则 (A) 和 [A] 也是正规括号序列；
3. 若 $A$ 和 $B$ 都是正规括号序列，则 $AB$ 也是正规括号序列。

在包含至少一对方括号的正规括号序列中，我们将方括号（包括 [ 和 ]）都用 ( 代替，这样就可以得到一个非正规括号序列。

例如：

• (( 可以由 [] 得到
• ((((())) 可以由 []((()))、([](()))、(([]())) 和 ((([]))) 这四种正规括号序列得到

你的任务是：给出一个非正规括号序列，求出有多少种正规括号序列，使得将其中的方括号用 ( 代替后，可以得到给定的非正规括号序列。

输入格式

• 第一行一个正整数 $N$，代表给定序列的长度
• 第二行一个长度为 $N$ 的字符串（只包含 ( 和 )），代表给定的非正规括号序列

输出格式

输出要求的正规括号序列的数量对 $10^9+9$ 取模的结果。

样例 1

输入

4
((()

输出

2

解释：满足条件的正规括号序列有两种：[]() 和 ([])。

样例 2

输入

8
((((((((

输出

14

解释：满足条件的正规括号序列有： [][][][]，[[]][][]，[[]][[]]，[][][[]]，[[[]]][]，[[][]][]，[][[][]]，[][[[]]]，[[[[]]]]，[[][[]]]，[[[]][]]，[[][][]]，[[[][]]]，[][[]][]。

数据范围与提示

• 对于 $20\%$ 的数据：$N \leq 50$
• 对于 $45\%$ 的数据：$N \leq 10^3$
• 对于 $100\%$ 的数据：$2 \leq N \leq 3 \times 10^4$

---

补充说明

• 输入保证是一个合法的非正规括号序列（即可以通过将某个包含至少一对[]的正规括号序列中的所有[和]替换为(得到）
• 需要计算所有可能的原始正规括号序列的数量
• 结果需要对 $10^9+9$ 取模