[Baltic2012]brackets

时间限制:30s      空间限制:64MB

题目描述

我们把一种由[、]、(、)组成的序列成为合法的:

单独的“()”和“[]”是合法的。

如果A和B是合法的,那么AB也是合法的。

如果A是合法的,那么(A)和[A]也是合法的。

有一个序列A,他的所有的“[”和“]”都被替换成了“(”,这样形成了序列B,现在已知序列B,求有多少种可能的序列A,答案mod 10^9+9。


输入格式

第一行一个数N ,2≤N≤30000

接下来一个字符串,由"("和")"组成,长度为N.


输出格式


样例输入

4 
((() 

样例输出

2

提示

对于样例有如下两种:

[](), ([])


题目来源

By Sbullet