TLE求助

#include<bits/stdc++.h>
#define int long long
#define p 1000000007
using namespace std;
template<typename T>inline void read(T &x){
	T f=1;char ch=getchar();x=0;
	for(;!isdigit(ch);ch=getchar()){if(ch=='-')f=-1;}
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+ch-'0';
	x*=f;
}
template<typename T>inline void write(T x){
	if(x<0){putchar('-');x=-x;}
	if(x<=9){putchar(x+'0');return;}
	write(x/10);
	putchar(x%10+'0');
}
int n,k;
char st[510];
bool isstar(int x){
	return st[x]=='*'||st[x]=='?';
}
bool isbracket(int l,int r){
	return (st[l]=='('||st[l]=='?')&&(st[r]==')'||st[r]=='?');
}
int cal(int &x,int y){
	x=(x+y)%p;
}
int f0[510][510],//S ok
	f1[510][510],//A
	f2[510][510],//AS ok
	f3[510][510],//SA ok
	f4[510][510];//(A)
signed main(){
	read(n);read(k);
	for(int i=1;i<=n;i++){
		scanf("%ch",st+i);
	}
	for(int i=1;i<=n;i++){
		for(int j=i;j<=i+k-1;j++){
			if(!isstar(j))break;
			f0[i][j]=1;
		}
	}
	for(int len=1;len<n;len++){
		for(int l=1;l<=n-len;l++){
			int r=l+len;
//			cout<<"***"<<l<<" "<<r<<endl;
			for(int i=l;i<r;i++){
				cal(f2[l][r],f1[l][i]*f0[i+1][r]);
				cal(f3[l][r],f0[l][i]*f1[i+1][r]);
			}
			if(isbracket(l,r)){
				if(len==1){
//					cout<<"%%%"<<l<<" "<<r<<"\n";
					cal(f4[l][r],1);
					cal(f1[l][r],1);
				}
				cal(f4[l][r],f0[l+1][r-1]+f1[l+1][r-1]+f2[l+1][r-1]+f3[l+1][r-1]);
//				cout<<l+1<<" "<<r-1<<endl;
//				cout<<f4[l][r]<<"="<<f0[l+1][r-1]<<"+"<<f1[l+1][r-1]<<"+"<<f2[l+1][r-1]<<endl;
				cal(f1[l][r],f0[l+1][r-1]+f1[l+1][r-1]+f2[l+1][r-1]+f3[l+1][r-1]);
			}
			for(int i=l;i<r;i++){
				cal(f1[l][r],(f2[l][i]+f1[l][i])*f4[i+1][r]);
			}
		}
		
	}
//	cout<<"\nf0\n";
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++){
//			cout<<setw(4)<<f0[i][j];
//		}
//		cout<<endl;
//	}
//	cout<<"\nf1\n";
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++){
//			cout<<setw(4)<<f1[i][j];
//		}
//		cout<<endl;
//	}
//	cout<<"\nf2\n";
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++){
//			cout<<setw(4)<<f2[i][j];
//		}
//		cout<<endl;
//	}
//	cout<<"\nf3\n";
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++){
//			cout<<setw(4)<<f3[i][j];
//		}
//		cout<<endl;
//	}
//	cout<<"\nf4\n";
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++){
//			cout<<setw(4)<<f4[i][j];
//		}
//		cout<<endl;
//	}
	write(f1[1][n]);
	return 0;
}
/*
7 3
(*??*??

6 3
(*??*?

*/