We give the following inductive definition of a “regular brackets” sequence:
● the empty sequence is a regular brackets sequence,
● if s is a regular brackets sequence, then (s) are regular brackets sequences, and
● if a and b are regular brackets sequences, then ab is a regular brackets sequence.
● no other sequence is a regular brackets sequence
For instance, all of the following character sequences are regular brackets sequences:
(), (()), ()(), ()(())
while the following character sequences are not:
(, ), )(, ((), ((()
Now we want to construct a regular brackets sequence of length $n$, how many regular brackets sequences we can get when the front several brackets are given already.
Multi test cases (about $2000$), every case occupies two lines.
The first line contains an integer $n$.
Then second line contains a string str which indicates the front several brackets.
Please process to the end of file.
[Technical Specification]
$1 \leq n \leq 1000000$
str contains only '(' and ')' and length of str is larger than 0 and no more than $n$.
For each case，output answer % $1000000007$ in a single line.