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
import sys
from functools import lru_cache

sys.setrecursionlimit(10000)

mn = input()
#print(mn)
m,n = [int(i) for i in mn.split()]

my_string = input()

leftfill = 0
c = 0
const = 1000000007


for char in my_string:
    if char == ')':
        c-=1
    elif char == '(':
        c+=1
    leftfill = min(leftfill,c)
    
rightfill = max(c,0)
leftfill *= -1

@lru_cache(maxsize=None)
def leftdp(a,b):
    #print(a,b)
    #print('...')
    #input('---')
    if b==0:
        return 1
    if a==b:
 #       print(a,b,1,'...')
        return 1
    if a == 0:
        ccc =  leftdp(1,b-1) % const
#        print(a,b,ccc,'...')
        return ccc
    if a >= 0 and b >= 0 and (a + b) % 2 == 0:
        ccc = (leftdp(a-1,b-1) + leftdp(a+1,b-1)) % const
  #      print(a,b,ccc,'...')
        return ccc
    #print(a,b,0,'...')
    return 0


@lru_cache(maxsize=None)
def rightdp(a,b):
   # print(a,b)
 #   print('---')
    #input('***')
    if b==0:
        return 1
    if a==b:
       # print(a,b,1,'***')
        return 1
    if a==0:
        ccc = rightdp(1,b-1) % const
      #  print(a,b,ccc,'***')
        return ccc
    if a >= 0 and b >= 0 and (a + b) % 2 == 0:
        ccc = (rightdp(a-1,b-1) + rightdp(a,b-2)) % const
     #   print(a,b,ccc,'***')
        return ccc
    #print(a,b,0,'***')
    return 0    

diff = m-n-leftfill - rightfill
sum_ = 0

for i in range(diff + 1):
    ddd = min(diff-i,i)
    for j in range(ddd + 1):
        k1 = leftdp(leftfill + j,leftfill + i)
        k2 = rightdp(rightfill + j, rightfill + diff - i) 
        #k1 = max(k1,1)
        #k2 = max(k2,1)
        sum_ +=  k1 * k2 

print(sum_)
