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

n, _ = [int(i) for i in input().split(' ')]

s = input()


s_num_open = len([c for c in s if c == '('])
s_num_close = len(s) - s_num_open

num_open_needed = (n // 2) - s_num_open

num_close_needed = (n // 2) - s_num_close

min_extra_opens_on_left = max(s_num_close - s_num_open, 0)

@lru_cache()
def possible_strings(num_opens, num_closes, used_opens):
    if num_opens == 0 and num_closes == 0:
        return 1
    if used_opens == 0:
        return possible_strings(num_opens - 1, num_closes, 1)
    else:
        curr_sum = 0
        if num_opens > 0:
            curr_sum += possible_strings(num_opens - 1, num_closes, used_opens + 1)
        if num_closes > 0:
            curr_sum += possible_strings(num_opens, num_closes - 1, used_opens - 1)
        return curr_sum


import sys
sys.setrecursionlimit(10**4)

mod_number = 10 ** 9 + 7

total = 0
for left_opens in range(min_extra_opens_on_left, num_open_needed + 1):
    for left_closes in range(0, left_opens - min_extra_opens_on_left + 1):
        total += (possible_strings(left_opens, left_closes, 0) * possible_strings(n // 2 - left_opens - s_num_open, n // 2 - left_closes - s_num_close, left_opens - left_closes + s_num_open - s_num_close)) % mod_number


print(total)