线性 $dp$，设 $dp_{i,j,k}$ 表示考虑到第 $i$ 位，有 $j$ 个左括号还未被匹配，末尾有 $k$ 个连续的 * 的方案数，边界是 $dp_{0,0,0}=1$，答案是 $dp_{n,0,0}$。但是第一个样例输出 $6$，不是很懂，求大佬教一下/kel。代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define re register
const int N=550,mod=1e9+7;
int dp[N][N],g[N][N],n,k;
char a[N];
il int read(){
    re int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
signed main(){
    n=read(),k=read();
    cin>>(a+1);
    dp[0][0]=1;
    for(re int i=1;i<=n;i++){
        for(re int j=0;j<i;j++)
        for(re int cnt=0;cnt<=min(i-1,k);cnt++){
            if(a[i]=='('||a[i]=='?')
                g[j+1][0]=(g[j+1][0]+dp[j][cnt])%mod;
            if((a[i]==')'||a[i]=='?')&&j)
                g[j-1][0]=(g[j-1][0]+dp[j][cnt])%mod;
            if((a[i]=='*'||a[i]=='?')&&cnt<k)
                g[j][cnt+1]=(g[j][cnt+1]+dp[j][cnt])%mod;
        }
        for(re int j=0;j<=i;j++)
            for(re int cnt=0;cnt<=k;cnt++)
                dp[j][cnt]=g[j][cnt],g[j][cnt]=0;
    }
    cout<<dp[0][0];
    return 0;
}