时间复杂度是 $O(n^3)$ ，而且我写的记忆化搜索，状态数量的那部分常数明显不大。#15 TLE 1.02s。求大佬卡常，必关。蒟蒻被硬控一下午了。

#include <bits/stdc++.h>

using namespace std;

const int N = 510, fff=1e9+7;

#define ll long long

int n,k, a[N], c[N];
ll dp[N][N][2], b[N];
bool vis[N][N][2];
char s[N];

bool chk(int i, int j) {
	return a[j]-a[i-1]==j-i+1;
}

ll f(int i, int j, int p) {
	if(vis[i][j][p])return dp[i][j][p];
	if(i>=j)return 0;
	if(s[i]!='('&&s[i]!='?')return 0;
	if(s[j]!=')'&&s[j]!='?')return 0;
	ll ans=f(i+1,j-1,1)%fff;
	for(int l=1;l<=k;l++) {
		if(!chk(i+1,i+l))break;
		if(i+l+1>=j-1)break;
		ans+=f(i+l+1,j-1,1)%fff, ans%=fff;
	}
	for(int l=1;l<=k;l++) {
		if(!chk(j-l,j-1))break;
		if(j-l-1<=i+1)break;
		ans+=f(i+1,j-l-1,1)%fff, ans%=fff;
	}
	if(p!=0) {
		b[i]=0;
		for(int r=i+1;r<=j+1;r++) {
			b[r]=b[r-1]+f(r,j,1);
		}
		for(int k1=i;k1<j;k1++) {
			ans+=(f(i,k1,0)*f(k1+1,j,1))%fff, ans%=fff;
			if(s[k1+1]=='*'||s[k1+1]=='?')ans+=(f(i,k1,0)*((b[min(c[k1+1], j-1)+1]%fff+fff-b[k1+1]%fff)%fff))%fff, ans%=fff;
		}
	}
	if(i+1==j||(chk(i+1,j-1)&&(j-1-i<=k)))ans++, ans%=fff;
	vis[i][j][p]=true, dp[i][j][p]=ans%fff;
	return ans%fff;
}

int main() {
	cin>>n>>k;
	scanf("%s",s+1);
	a[0]=0;
	for(int i=1;i<=n;i++) {
		a[i]=a[i-1];
		if(s[i]=='?'||s[i]=='*')a[i]++;
	}
	for(int i=n;i>=1;i--) {
		if(s[i]!='?'&&s[i]!='*')c[i]=0;
		else if(i==n)c[i]=i;
		else if(s[i+1]!='?'&&s[i+1]!='*')c[i]=i;
		else c[i]=c[i+1];
	}
	for(int i=n;i>=1;i--) {
		if(c[i]-i+1>k)c[i]=i+k-1;
	}
	cout<<f(1,n, 1);
	return 0;
}