As Famil Door’s birthday is coming, some of his friends (like Gabi) decided to buy a present for him. His friends are going to buy a string consisted of round brackets since Famil Door loves string of brackets of length *n* more than any other strings!

The sequence of round brackets is called valid if and only if: 
 1.  the total number of opening brackets is equal to the total number of closing brackets; 1.  for any prefix of the sequence, the number of opening brackets is greater or equal than the number of closing brackets. 
Gabi bought a string *s* of length *m* (*m* ≤ *n*) and want to complete it to obtain a valid sequence of brackets of length *n*. He is going to pick some strings *p* and *q* consisting of round brackets and merge them in a string *p* + *s* + *q*, that is add the string *p* at the beginning of the string *s* and string *q* at the end of the string *s*.

Now he wonders, how many pairs of strings *p* and *q* exists, such that the string *p* + *s* + *q* is a valid sequence of round brackets. As this number may be pretty large, he wants to calculate it modulo 10<sup class="upper-index">9</sup> + 7.
First line contains *n* and *m* (1 ≤ *m* ≤ *n* ≤ 100 000, *n* - *m* ≤ 2000) — the desired length of the string and the length of the string bought by Gabi, respectively.

The second line contains string *s* of length *m* consisting of characters '(' and ')' only.
In the first sample there are four different valid pairs: 
 1.  *p* = "(", *q* = "))" 1.  *p* = "()", *q* = ")" 1.  *p* = "", *q* = "())" 1.  *p* = "", *q* = ")()" 
In the second sample the only way to obtain a desired string is choose empty *p* and *q*.

In the third sample there is no way to get a valid sequence of brackets.
4 1
(
4
4 4
(())
1
4 3
(((
0
875 50
)))((())()))((()(())))))())))((((((()))))))()(((((
0
1980 464
))(()()))(((((((((()))))))(()(((()((()))()()())()))()))(()))))))(())((())))()())()((())())()())))(())()(()))(()())()((((()))())()(())))))(()()(()(((((()(()()))(((()))(())))))()())(())))))())()()((())))))))((()(())))))()()(()((()((()()))(()))(())(()))()((((())()()))))))()(())))()(()())()())(((((()))())))())())(()))()(()))())((())((((()(()(())))(((()()))))()()()))))((()())()((())())))())))()(()(()()(((((()((((()))()(())()))))()(()))(()(((((((()((()(())))(((((())
854368836
1542 282
())())()((()(()))()((())()))((())(()))))(()()))(())((()))()((()())())()))((())(((()(())((()()())((((())))((()((((()(()()))))(()(()()(())()((())())())))))()()())))(()((((()))(()(()(()(()))())((()()()()(()(()))())(((()(())()(())()()())))()))())(()))(((())()))((())()(())))))(())))()()
631927032
2 2
)(
0
2 2
))
0
#  if you win, you live. you cannot win unless you fight.
import string
import sys
from sys import stdin, setrecursionlimit
# fd=open("cses.txt")
# sys.stdin=fd
input = stdin.readline
rd = lambda: map(lambda s: int(s), input().strip().split())
rdone = lambda: map(lambda s: int(s) - 1, input().strip().split())
ri = lambda: int(input())
rs = lambda: input().strip()
from collections import defaultdict as unsafedict, deque, Counter as unsafecounter
from bisect import bisect_left as bl, bisect_right as br


n,m=rd()
s=rs()
pref,mn=0,float("inf")
for i in s:
    pref+=[-1,1][i=="("]
    mn=min(mn,pref)
dp=unsafedict(lambda :-1)
mod=10**9+7
dif=n-m
def rec(i,type,bal):
    if bal>2000 or bal<0 or i>dif:
        return 0
    if i==dif and type==1:
        return bal==0

    if dp[(i,type,bal)]!=-1:
        return dp[(i,type,bal)]
    ans=0
    if type==0:
        if mn>=0:
            ans=rec(i,1,bal+pref)
        elif mn<0 and (bal>abs(mn)):
            ans=rec(i,1,bal+pref)
        ans+=rec(i+1,0,bal-1)+rec(i+1,0,bal+1)
    else:
        ans+=rec(i+1,1,bal+1)+rec(i+1,1,bal-1)
    ans%=mod
    dp[(i,type,bal)]=ans
    return ans

print(rec(0,0,0))

	  	 		 		 						 		 	 				  		