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

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

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

多组输入数据，不超过 100 组 ，每组测试数据占两行。

第一行包括一个整数 n(1≤n≤100000)。

然后第二行包含字符串 str，该字符串为常规序列的前几个括号。

str 仅包含 '(' 和 ')'，并且 str 的长度大于 0 且不大于 n。

对于每种情况，在一行中输出答案 ％ 1000000007

对于第一种情况，唯一的规则序列是()()。

对于第二种情况，规则序列是(())和()()。

对于第三种情况，规则序列是()()()和()(())。