题解 | #合法的括号序列#

mod = 10**9 + 7
'''
dp[i][j]表示前i个字符中钦定j个左括号的序列数量
'''
s = input()
n = len(s)
dp = [[0]*(n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1,n+1):
    for j in range((i+1)//2,(n+1)):
        if s[i-1] == '?':
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j])%mod
        elif s[i-1] == '(':
            dp[i][j] = dp[i-1][j-1]
        else:
            dp[i][j] = dp[i-1][j]
print(dp[-1][n//2])