Famil Door and Brackets
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 109 + 7.
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.
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.
Print the number of pairs of string p and q such that p + s + q is a valid sequence of round brackets modulo 109 + 7.
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)
K = 10 ** 9 + 7

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
    if E == 0:
        return 1
    C = [1]
    for n in range(E + max(I, J) + 1):
        C.append(C[n] * 2 * (2 * n + 1) // (n + 2))
    W = [[c % K for c in C]]
    W.append(W[0][1:])
    for i in range(2, E + max(I, J) + 1):
        W.append([(W[i - 1][e + 1] - W[i - 2][e + 1]) % K for e in range(E + max(I, J) + 1 - i + 1)])
    result = sum((W[I + k][e - k] * W[J + k][E - e] % K for k in range(E + 1) for e in range(k, E + 1)))
    return result
if __name__ == '__main__':
    (n, m) = map(int, input().split())
    s = input()
    print(ways(n, s) % K)
(n, m) = map(int, input().split())
s = input()
mod = 10 ** 9 + 7
(c, b, ans, d, k) = (0, 0, 0, [[1]], n - m)
for i in s:
    c += (i == '(') * 2 - 1
    b = min(c, b)
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)
for i in range(k + 1):
    for j in range(-b, min(k - i - c, i) + 1):
        ans = (ans + d[i][j] * d[k - i][j + c]) % mod
print(ans)
(n, m) = map(int, input().split())
s = input()
mod = 10 ** 9 + 7
(c, b, ans, d, k) = (0, 0, 0, [[1]], n - m)
for i in s:
    c += (i == '(') * 2 - 1
    b = min(c, b)
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)
for i in range(k + 1):
    for j in range(-b, min(k - i - c, i) + 1):
        ans = (ans + d[i][j] * d[k - i][j + c]) % mod
print(ans)