Brackets

我们给出下列递归的合法括号序列的定义：
  ● 空序列是合法括号序列
  ● 如果s是一个合法括号序列，那么(s)也是合法括号序列
  ● 如果a和b是合法括号序列，那么ab也是合法括号序列
  ● 没有其它情况是合法括号序列

比如下列括号序列是合法括号序列
(), (()), ()(), ()(())
下列括号序列则不是
(, ), )(, ((), ((()

现在，我们要构造长度为$n$的合法括号序列，前面的一些括号已经给出，问可以构造出多少合法序列。

多组测试数据(大概$2000$)，每一组数据占两行。
第一行给出一个整数$n$。
第二行给出一个字符串代表前面已经确定的几个括号。
请处理到文件末尾。

[参数约定]
$1 \leq n \leq 1000000$
字符串只包含’(’和’)’，长度大于$0$并且不超过$n$.

对于每一个数据，在一行中输出答案对$1000000007$取余的结果。

4
()
4
(
6
()

1
2
2

第一组数据只有一种可能，它就是()().
对于第二组数据他有两种可能，他们是(()) 和()().
对于第三种数据，两种可能是()()() 和()(()).