$f_{i,j}$ $i,j$ 为匹配的括号方案

$h_{i,j}$ $i,j$ 不匹配方案

$g_{i,j}$ $[i,j]$ 全是 $*$ 或 $?$

$R_i$ 从 $i$ 开始连续 $*/?$ 的最右端点

#include<bits/stdc++.h>
#define int long long
#define pt putchar(' ')
#define nl puts("")
#define pi pair<int,int>
#define pb push_back
#define go(it) for(auto &it:as[x]) //注意加了&
using namespace std;

const int N=510,Q=1e9+7;
int n,m;
int f[N][N],g[N][N],h[N][N],R[N],c[N][N];
char s[N];

int fr(){ //double 不能快读！！！！
    int x=0,flag=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') flag=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x*flag;
}
void fw(int x){
	if(x<0) putchar('-'),x=-x;
    if(x>9) fw(x/10);
    putchar(x%10+'0');
}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}

bool ck(int x,int y)
{
	return (s[x]=='?' || s[x]=='(') && (s[y]==')' || s[y]=='?');
}

signed main()
{
	n=fr(),m=fr();
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
		if((s[i]=='?' || s[i]=='*') && m) g[i][i]=1;
	for(int i=1;i<n;i++)
	{
		if(ck(i,i+1)) f[i][i+1]=1;
		if((s[i]=='*' || s[i]=='?') && (s[i+1]=='*' || s[i+1]=='?') && m>=2) g[i][i+1]=1;
		g[i+1][i]=1;
	}
	
	for(int len=3;len<=m;len++)
		for(int i=1;i+len-1<=n;i++)
		{
			int j=i+len-1;
			g[i][j]|=(s[i]=='*' || s[i]=='?') && g[i+1][j];
			g[i][j]|=(s[j]=='*' || s[j]=='?') && g[i][j-1];
			g[i][j]|=((s[i]=='*' || s[i]=='?') && (s[j]=='*' || s[j]=='?')) && g[i+1][j-1];
		}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=min(n,i+m-1);j>=i;j++)
			if(g[i][j]) {R[i]=j;break;}
		R[i]=max(R[i],i);
	}
	
	for(int len=3;len<=n;len++)
		for(int i=1;i+len-1<=n;i++)
		{
			int j=i+len-1;
			if(ck(i,j)) //第一种
			{
				f[i][j]=f[i+1][j-1]+h[i+1][j-1]; //(A)
				if(g[i+1][j-1]) f[i][j]++; //(S)
				for(int k=i+1;k<j && k-(i+1)+1<=m;k++) //(SA)
					(f[i][j]+=g[i+1][k]*(f[k+1][j-1]+h[k+1][j-1])%Q)%=Q;
				for(int k=j-1;k>i && j-1-k+1<=m;k--) //(AS)
					(f[i][j]+=g[k][j-1]*(f[i+1][k-1]+h[i+1][k-1])%Q)%=Q;
			}
			
			for(int k=i;k<j;k++) //AB
				(h[i][j]+=(f[i][k]+h[i][k])%Q*f[k+1][j]%Q)%=Q;
			
			c[i][j]=(c[i+1][j]+f[i][j])%Q;
			for(int k=i+1;k<j;k++) //ASB
				if(s[k]=='*' || s[k]=='?') (h[i][j]+=(f[i][k-1]+h[i][k-1])%Q*(c[k+1][j]-c[min(j-1,R[k])+2][j])%Q)%=Q;
		}
	fw((f[1][n]+h[1][n])%Q);
	return 0;
}