http://codeforces.com/contest/785/problem/D
题意：给一堆括号，求有多少种规范的括号
假如说这样： ( ) ( ( ( ) ) ) )

考虑每个括号的贡献，假如现在考虑第一个红色括号的贡献：
他的前面有 2 个 ( ，后面有 4 个 )
考虑只配对成1对：他的前面选 0 个 ( ，后面选 1 个 ) ，那就是 C 2 0 ∗ C 4 1 种情况
考虑只配对成2对：他的前面选 1 个 ( ，后面选 2 个 ) ，那就是 C 2 1 ∗ C 4 2 种情况
考虑只配对成3对：他的前面选 2 个 ( ，后面选 3 个 ) ，那就是 C 2 2 ∗ C 4 3 种情况
那么他的贡献就只有这么多了
而 C 2 0 ∗ C 4 1 + C 2 1 ∗ C 4 2 + C 2 2 ∗ C 4 3
也就是 <munderover> ∑ i = 0 k = m i n ( n , m ) </munderover> C n i ∗ C m i + 1
而这种阔以有范德蒙恒等式简化

 
#include"bits/stdc++.h"
using namespace std;
const int maxn=2e5+5;
const int MOD=1e9+7;
char s[maxn];
int sum1[maxn],sum2[maxn];
long long fac[maxn]={1,1},inv[maxn]={1,1};
long long ksm(long long a,long long b,long long mod)
{
    long long res=1,base=a;
    while(b)
    {
        if(b&1)res=(res*base)%mod;
        base=(base*base)%mod;
        b>>=1;
    }
    return res;
}
long long C(int n,int m)
{
    long long res=fac[n]*inv[m]%MOD;
    res=res*inv[n-m]%MOD;
    return res;
}
int main()
{
    for(int i=2;i<=200000;i++)
    {
        fac[i]=(long long)i*fac[i-1]%MOD;
        inv[i]=(long long)inv[i-1]*ksm(i,MOD-2,MOD)%MOD;
    }
// cout<<C(10,5)<<endl;
    while(cin>>s)
    {
        memset(sum1,0,sizeof(sum1));
        memset(sum2,0,sizeof(sum2));
        int len=strlen(s);
        for(int i=1,j=len;i<=len;i++,j--)
        {
            sum1[i]=sum1[i-1];
            if(s[i-1]=='(')sum1[i]++;
            sum2[j]=sum2[j+1];
            if(s[j-1]==')')sum2[j]++;
        }
        long long res=0;
        for(int i=1;i<=len;i++)
        {
            if(s[i-1]=='(')
            {
                res+=C(sum1[i]+sum2[i]-1,sum2[i]-1);
                if(res>MOD)res-=MOD;
            }
        }
        cout<<res<<endl;

    }
}