[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