题目描述

译自 BalticOI 2012 Day1 T1. Brackets

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

• () 和 [] 是正规括号序列；
• 若 A 是正规括号序列，则 (A) 和 [A] 也是正规括号序列；
• 若 A 和 B 都是正规括号序列，则 AB 也是正规括号序列。

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

例如 (( 和 ((((())) 都是非正规括号序列，(( 可以由 [] 得到，((((())) 则可以由 []((()))，([](()))，(([]())) 和 ((([]))) 这四种正规括号序列得到。

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

输入格式

第一行一个正整数 $N$，代表给定序列的长度。

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

输出格式

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

样例 1

4
((()

2

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

8
((((((((

14

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

数据范围与提示

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