#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll dp[505][505][8];
char c[505];
int n,kk;
bool check(int l,int r)
{
	int i;
	if(r-l+1>kk||l>r) return false;
	for(i=l;i<=r;i++)
		if(c[i]!='?'&&c[i]!='*') return false;
	return true;
}
int main()
{
	int i,j,k,l;
	cin>>n>>kk;
	for(i=1;i<=n;i++) cin>>c[i];
	for(i=1;i<n;i++)
		if((c[i]=='('||c[i]=='?')&&(c[i+1]==')'||c[i+1]=='?'))
		{
			dp[i][i+1][0]=1;
		}
	for(i=n-1;i>=1;i--)
		for(j=i+1;j<=n;j++)
			if(check(i+1,j-1)&&(c[i]=='('||c[i]=='?')&&(c[j]==')'||c[j]=='?')) 
			{
				dp[i][j][1]++;
				dp[i][j][7]%=mod;
			}
	for(i=n-1;i>=1;i--)
	{
		for(j=i+1;j<=n;j++)
		{
			int d=0;
			if((c[i]=='('||c[i]=='?')&&(c[j]==')'||c[j]=='?')) 
				dp[i][j][2]=(dp[i][j][2]+dp[i+1][j-1][7]%mod)%mod;
			for(k=i+1;k<j-1;k++)
				if(check(k+1,j-1)&&(c[i]=='('||c[i]=='?')&&(c[j]==')'||c[j]=='?')) 
					dp[i][j][3]=(dp[i][j][3]+dp[i+1][k][7])%mod;
			for(k=i+1;k<j-1;k++)
				if(check(i+1,k)&&(c[i]=='('||c[i]=='?')&&(c[j]==')'||c[j]=='?')) 
				{
					dp[i][j][4]=(dp[i][j][4]+dp[k+1][j-1][7])%mod;
				}	
			for(k=i+1;k<j;k++)
				for(l=k+1;l<j;l++)
				{
					if(check(k+1,l-1)) 
					{
						long long mul1,mul2;
						mul1=((dp[i][k][7]-dp[i][k][5]+mod)%mod-dp[i][k][6]+mod)%mod;
						mul2=((dp[l][j][7]-dp[l][j][5]+mod)%mod-dp[i][k][6]+mod)%mod;
						dp[i][j][5]=(dp[i][j][5]+mul1*mul2%mod)%mod;
					}
				}
			bool p1=0;
			for(k=i+1;k<j;k++)
				for(l=k+1;l<j;l++)
					if(check(k+1,l-1)) 
					{
						long long mul1,mul2;
						mul1=((dp[i][k][7]-dp[i][k][6]+mod)%mod-dp[i][k][5]+mod)%mod;
						mul2=((dp[l][j][7]-dp[l][j][6]+mod)%mod-dp[l][j][5]+mod)%mod;
						if(mul1>0&&mul2>0)
						{
							dp[i][j][5]=(dp[i][j][5]+mul2*dp[i][k][5]%mod)%mod;
							dp[i][j][5]=(dp[i][j][5]+mul1*dp[l][j][5]%mod)%mod;
							dp[i][j][5]=(dp[i][j][5]+dp[i][k][5]*dp[l][j][5]%mod)%mod;
							break;
						}
					}
			for(k=i;k<j;k++)
			{
				long long mul1,mul2;
				mul1=((dp[i][k][7]-dp[i][k][6]+mod)%mod+mod)%mod;
				mul2=((dp[k+1][j][7]-dp[k+1][j][6]+mod)%mod+mod)%mod;
				dp[i][j][6]=(dp[i][j][6]+mul1*mul2%mod)%mod;
			}
			bool p2=0;
			for(k=i;k<j;k++)
			{
				long long mul1,mul2;
				mul1=(dp[i][k][7]-dp[i][k][6]+mod)%mod;
				mul2=(dp[k+1][j][7]-dp[i][k][6]+mod)%mod;
				if(mul1>0&&mul2>0)
				{
					dp[i][j][6]=(dp[i][j][6]+dp[i][k][6]*mul2%mod)%mod;
					dp[i][j][6]=(dp[i][j][6]+mul1*dp[k+1][j][6]%mod)%mod;
					dp[i][j][6]=(dp[i][j][6]+dp[i][k][6]*dp[k+1][j][6]%mod)%mod;
					break;	
				}
			}
			dp[i][j][7]=(dp[i][j][7]+dp[i][j][0])%mod;
			dp[i][j][7]=(dp[i][j][7]+dp[i][j][1])%mod;
			dp[i][j][7]=(dp[i][j][7]+dp[i][j][2])%mod;
			dp[i][j][7]=(dp[i][j][7]+dp[i][j][3])%mod;
			dp[i][j][7]=(dp[i][j][7]+dp[i][j][4])%mod;
			dp[i][j][7]=(dp[i][j][7]+dp[i][j][5])%mod;
			dp[i][j][7]=(dp[i][j][7]+dp[i][j][6])%mod;
		}
	}
	cout<<dp[1][n][7]%mod;
	return 0;
}

0-7表示序列的7种形态，含义如题目描述