给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。
两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。
例如，对于括号序列 ((()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：()()()()()()、()(())()(())、(())()(())()、(()())(()()) 和 ((()))((()))。
输入描述
输入一行包含一个字符串 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)
