【题意】

定义一个合法串：

(1)，'('的总数 == ')'的总数。

(2), 串中所有前缀 满足 '('的个数 >= ')'的个数。

题意：给定一个合法串的长度n和一个长度为m的中间串s，要求你找到一个p串和q串，使得p + s + q是一个合法串且长度为n。问有多少种不同的方案数。 结果 % (1e9+7)。

【解题方法】

设置dp[i][j]表示长度为i的合法串且'('的个数 - ')'的个数 == j的方案数。

我们称j为该串的平衡度。其实dp[i][j] = dp[i][-j]，因为'('和')'可以互换。

转移有dp[i][j] = dp[i-1][j+1] + dp[i-1][j-1]。

那么我们可以枚举p串的长度和平衡度，找到合法的q串。再统计方案数。

注意：我们不能仅仅要求p + s + q合法就够了，必须保证选出的p + s也是一个合法串。

假设p + s长度为i且平衡度为j(j>=0)。那么q串长度为n-m-i，平衡度为-j。

【AC code】 
#include <bits/stdc++.h>
using namespace std;
const int maxn=2005;
const int mod=1e9+7;
long long dp[maxn][maxn];
const int inf=0x3f3f3f3f;
int n,m;
string str;
void add(long long &x,long long y){
    x+=y;
    x%=mod;
}
void init(){
    memset(dp,0,sizeof(dp));
    dp[0][0]=1LL;
    for(int i=1; i<=2000; i++){
        dp[i][0]=dp[i-1][1];
        for(int j=1; j<=i; j++){
            add(dp[i][j],(dp[i-1][j+1]+dp[i-1][j-1])%mod);
        }
    }
}

int main()
{
    init();
    cin>>n>>m;
    cin>>str;
    int minn=inf;
    int sum=0;
    for(int i=0; i<m; i++){
        if(str[i]=='(') sum++;
        else sum--;
        minn=min(minn,sum);
    }
    int len=n-m;
    long long ans=0;
    for(int i=0; i<=len; i++){
        for(int j=0; j<=i; j++){
            if(j+minn<0||len-i<j+sum) continue;
            add(ans,dp[i][j]*dp[len-i][j+sum]);
        }
    }
    cout<<ans<<endl;
}