#3292. 「BalticOI 2012 Day1」括号

内存限制:64 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: StudyingFather

题目描述

译自 BalticOI 2012 Day1 T1. Brackets

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

  • ()[] 是正规括号序列;
  • A 是正规括号序列,则 (A)[A] 也是正规括号序列;
  • AB 都是正规括号序列,则 AB 也是正规括号序列。

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

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

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

输入格式

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

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

输出格式

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

样例

样例输入 1

4
((()

样例输出 1

2

样例解释 1

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

样例输入 2

8
((((((((

样例输出 2

14

样例解释 2

满足条件的正规括号序列有:[][][][][[]][][][[]][[]][][][[]][[[]]][][[][]][][][[][]][][[[]]][[[[]]]][[][[]]][[[]][]][[][][]][[[][]]][][[]][]

数据范围与提示

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