记录编号	566686	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2021S]括号序列	最终得分	100
用户昵称	遥时_彼方	是否通过	通过
代码语言	C++	运行时间	3.218 s
提交时间	2021-11-16 14:17:32	内存使用	4.63 MiB

#include<bits/stdc++.h>
#define ull unsigned long long 
#define ll long long 
using namespace std;
int nc,kc; 
int ps=1;
char n[505];
ll mod=1000000007;
ll ans;
ll f[505][505];
ll fs[505][505];
ll g[505][505]; 
void G(int lx,int rx)
{
	if(ps&&lx!=1)
	{
		g[lx][rx]=g[1][1+rx-lx];
		return;
	}
	int ly=lx+1;
	int ry=rx-1;
	g[lx][rx]+=g[ly][ry]+f[ly][ry];
	for(int k=1;k<=kc&&ly+k<ry;k++)
	{
		if(n[lx+k]!='*'&&n[lx+k]!='?') break; 
		g[lx][rx]+=g[ly+k][ry];
		g[lx][rx]+=f[ly+k][ry];
		g[lx][rx]%=mod;
	}///前部分为* 
	for(int k=1;k<=kc&&ry-k>ly;k++)
	{
		if(n[rx-k]!='*'&&n[rx-k]!='?') break; 
		g[lx][rx]+=g[ly][ry-k];
		g[lx][rx]+=f[ly][ry-k];
		g[lx][rx]%=mod;
	}///后部分为* 
	int p=1;
	if(rx-lx-1<=kc)
	{
		for(int i=ly;i<=ry;i++)
		{
			if(n[i]!='*'&&n[i]!='?')
			{
				p=0;
				break;
			}
		}
	}
	else p=0;
	if(p) g[lx][rx]+=1;
	g[lx][rx]%=mod;
//	cout<<"g:"<<lx<<" "<<rx<<":"<<g[lx][rx]<<endl;
	return;
}
void F(int lx,int rx)
{
	if(ps&&lx!=1)
	{
		f[lx][rx]=f[1][1+rx-lx];
		for(int i=1;i<=kc&&lx-i>=1;i++)
		{
			if(n[lx-i]=='*'||n[lx-i]=='?')
			{
				fs[lx-i][rx]+=(f[lx][rx]+g[lx][rx]);
				fs[lx-i][rx]%=mod;
			} 
			else break;
		}
		return;
	}
	int ly=lx+1;
	int ry=rx-1;
	for(int i=ly;i<ry;i++)
	{
		if(n[i]==')'||n[i]=='?')
		{
			f[lx][rx]+=g[lx][i]*f[i+1][rx];//前单后串（不含*） 
			f[lx][rx]+=g[lx][i]*g[i+1][rx];//前单后单（不含*） 
			f[lx][rx]+=g[lx][i]*fs[i+1][rx];//前单后*再接串|单 
			f[lx][rx]%=mod;
		}
	}
	for(int i=1;i<=kc&&lx-i>=1;i++)
	{
		if(n[lx-i]=='*'||n[lx-i]=='?')
		{
			fs[lx-i][rx]+=(f[lx][rx]+g[lx][rx]);
			fs[lx-i][rx]%=mod;
		} 
		else break;
	} 
//	cout<<"f:"<<lx<<" "<<rx<<":"<<f[lx][rx]<<endl;
	return;
}
int main()
{
	freopen("2021bracket.in","r",stdin);
	freopen("2021bracket.out","w",stdout);
	scanf("%d%d",&nc,&kc);
	for(int i=1;i<=nc;i++) 
	{
		cin>>n[i];
		if(n[i]!='?') ps=0;
	}
//	cout<<ps<<endl;
	for(int th=2;th<=nc;th++)
	{
		for(int st=1;st<=nc-th+1;st++)
		{
			if(n[st]=='('||n[st]=='?')
			{
			    if(n[st+th-1]==')'||n[st+th-1]=='?')
			    {
					G(st,st+th-1);
			    	F(st,st+th-1);
				}
			}
		} 
	}
//	for(int i=1;i<=nc;i++)
//	{
//		for(int o=i+1;o<=nc;o++) cout<<i<<" "<<o<<":"<<fs[i][o]<<endl;
//	}
//	cout<<endl;
	ans+=g[1][nc]+f[1][nc];
    ans%=mod;
	printf("%lld\n",ans);
    return 0;
}