题目描述

一个合法括号序列的定义如下：

• () 和 [] 是合法括号序列
• 若 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