给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。
两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。
例如，对于括号序列 ((()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：()()()()()()、()(())()(())、(())()(())()、(()())(()()) 和 ((()))((()))。
输入描述
输入一行包含一个字符串 s，表示给定的括号序列，序列中只有左括号和右括号。
输出描述
输出一个整数表示答案，答案可能很大，请输出答案除以 10000000071000000007 (即 10^9 + 7) 的余数。
输入输出样例
示例 1
输入
((()
输出
5
step1
我们将左括号的值看作 1，右括号的值看作 -1。
定义 sum[i]表示前 i个括号的和，n 表示序列的长度，那么对于一个合法序列，其必定满∀i∈(1,n),sum[i]≥0 且 sum[n] = 0。
step2
我们需要将添加括号使得原括号序列成为合法括号序列。
题目要尽可能少的添加括号，所以我们添加的左括号必然只能和原序列中的右括号匹配；我们添加的右括号必然只能和原序列中的左括号匹配。若我们添加的左括号和我们添加的右括号匹配了，那么它们无疑是一对没有意义的添加。
于是添加的左括号的方案只和原序列中的右括号相关，添加的右括号的方案只和原序列中的左括号相关，所以左右括号的添加是相互独立的。设左括号的添加方案为 f1，右括号的添加方案为 f2，那么显然最后的答案就是f1×f2。
step3
我们先考虑左括号的添加方案数。
设原序列中有 cnt 个右括号，我们以原序列中的右括号为分界点，那么一共可以划分出 cnt+1个区域。我们只能在第 cnt1∼cnt 个区域添加左括号，因为若是在第 cnt+1 区域添加左括号，将不会有右括号可以与它匹配。
定义 dp[i][j] 表示前 i个区域（右括号），在我们添加了若干个左括号后一共有 j个左括号的方案数。对于两个不同的方案，它们至少有一个区域添加的左括号的个数不相同，于是可得：
dp[i][j]=dp[i−1][j]+dp[i−1][j-1]+dp[i−1][j-2]+⋯+dp[i−1][0]
前缀优化
dp[i][j-1]=dp[i-1][j]+dp[i-1][j-1]+·····+dp[i-1][0]
dp[i][j]=dp[i][j-1]+dp[i-1][j+1]
思路：
从左向右是左括号的填空，左括号只能加在右括号的前面的n个位置
s=input()
n=len(s)
mod=1000000007
N=n+5
dp=[[0 for i in range(N)]for j in range(N)]
def calc():
dp[0][0]=1
for i in range(1,n+1):
if s[i-1]=="(":
for j in range(1,n+1):
dp[i][j]=dp[i-1][j-1]%mod
else:
dp[i][0]=(dp[i-1][1]+dp[i-1][0])%mod
for j in range(1,n+1):
dp[i][j]=(dp[i-1][j+1]+dp[i][j-1])%mod
for i in range(n+1):
if dp[n][i]!=0:
return dp[n][i]
return -1
left=int(calc())
a=list(s[::-1])
for i in range(n):
if a[i]==")":
a[i]="("
else:
a[i]=")"
s=''.join(a)
right=calc()
print((left*right)%mod)
import os
import sys
S = input()
dp = [[0 for i in range(5010)] for i in range(5010)]
mod = 1000000007
def calc(cnt, flag, S):
pre = [0] * 5010
nex = [0] * 5010
sum = [0] * 5010
s = S
if cnt == 0:
return 1
if not flag:
s = list(S[::-1])
i = 0
while i < len(s):
if s[i] == ')':
s[i] = '('
else:
s[i] = ')'
i += 1
n = 0
now = 0
i = 0
while i < len(s):
if s[i] == ')':
n += 1
sum[n] = now
if s[i] == '(':
now += 1
i += 1
if sum[1] > 0:
dp[1][0] = 1
pre[0] = 1
i = 1
while i <= cnt:
dp[1][i] = 1
pre[i] = pre[i - 1] + 1
i += 1
i = 2
while i <= n:
j = 0
while j <= cnt:
nex[j] = 0
j += 1
j = i - sum[i]
while j <= cnt:
dp[i][j] = pre[j]
nex[j] = int((nex[j - 1] + dp[i][j]) % mod)
j += 1
j = 0
while j <= cnt:
pre[j] = nex[j]
j += 1
i += 1
return dp[n][cnt]
tot = 0
cnt1 = 0
cnt2 = 0
for i in S:
if i == '(':
tot += 1
else:
tot -= 1
if tot < 0:
tot = 0
cnt1 += 1
cnt2 = tot
print(calc(cnt1, True, S) * calc(cnt2, False, S) % mod)
