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
def ij(s):
    i = 0
    j = 0
    for c in s:
        if c == ')':
            if j > 0:
                j -= 1
            else:
                i += 1
        else:
            j += 1
    return i, j


def ways(n, s):
    I, J = ij(s)
    f = n - len(s) - I - J
    if f < 0 or f%2:
        return 0
    E = f//2

#     print(E, I, J)

    C = [1]
    for n in range(E+2*max(I, J)):
        C.append(C[n] * 2 * (2*n + 1) // (n+2))

    W = []
    W.append(C[:-1])
    W.append(C[1:])

#     for row in W:
#         print('\t'.join(map(str, row)))

    for i in range(2, 2*max(I,J)+1):
        W.append([W[i-1][e+1]-W[i-2][e+1] for e in range(E+2*max(I,J)-i+1)])
#         print('\t'.join(map(str, W[-1])))

#     for e in range(E+1):
#         for k in range(min(e, E-e)+1):
#             print("e={}, k={}".format(e, k))
#             print("W[{}][{}] = {}".format(I+k, e-k, W[I+k][e-k]))
#             print("W[{}][{}] = {}".format(J+k, E-e-k, W[J+k][E-e-k]))

    return sum(W[I+k][e-k] * W[J+k][E-e]
               for k in range(E+1)
               for e in range(E+1)
               if e-k >= 0 and E-e >= 0)


if __name__ == '__main__':
    n, m = map(int, input().split())
    s = input()
    print(ways(n, s) % (10**9 + 7))

