I found an interesting problem on https://codeforces.com/problemset/problem/629/C:
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:   the total number of opening brackets is equal to the total number of closing brackets;  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^9 + 7.


-----Input-----

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.


-----Output-----

Print the number of pairs of string p and q such that p + s + q is a valid sequence of round brackets modulo 10^9 + 7.


-----Examples-----
Input
4 1
(

Output
4

Input
4 4
(())

Output
1

Input
4 3
(((

Output
0



-----Note-----

In the first sample there are four different valid pairs:   p = "(", q = "))"  p = "()", q = ")"  p = "", q = "())"  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.

I tried it in Python, but could not do it. Can you solve it?
n, m = list(map(int, input().split()))
s = input()
mod = 10 ** 9 + 7
c = b = 0
for x in s:
    c += (x == '(') * 2 - 1
    b = min(c, b)
d = [[1]]
for i in range(n - m):
    nd = d[-1][1:] + [0] * 2
    for j in range(1, i + 2):
        nd[j] = (nd[j] + d[-1][j-1]) % mod
    d.append(nd)
ans = 0
for i in range(n - m + 1):
    l = n - m - i
    for j in range(-b, min(l - c, i) + 1):
        ans = (ans + d[i][j] * d[l][j + c]) % mod
print(ans)