记录编号	572225	评测结果	AAAAAAAAAA
题目名称	[CF629C]Famil Door and Brackets	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.228 s
提交时间	2022-06-29 15:12:11	内存使用	25.55 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const int N=100000+5;
const int M=2000+5;
int n,m,sl;
int l=0,r=0;
char s[N];
ll ans=0;
ll f[M][M]={0};
int main(){
    freopen ("tribrackets.in","r",stdin);
    freopen ("tribrackets.out","w",stdout);
    scanf("%d%d",&n,&m);
    if (n%2==1){
        printf("0\n");
        return 0;
    }
    scanf("%s",s);
    sl=strlen(s);
    for (int i=0;i<sl;i++){
        if (s[i]=='(')l++;
        else{
            if (l==0)r++;
            else l--;
        }
    }
    f[0][0]=1;
    for (int i=1;i<=n-m;i++){
        for (int j=0;j<=i;j++){ 
            f[i][j]=(f[i-1][j-1]+f[i-1][j+1])%mod;
        }
    }
    for (int i=0;i<=n-m;i++){
        for (int j=r;j<=i&&j-r+l<=n-m-i;j++){
            ans=(ans+f[i][j]*f[n-m-i][j-r+l]%mod)%mod;
        }
    }
    printf("%lld\n",ans%mod);
    return 0;
}