所谓 dp套dp ，实际上就是在说求解一个 dp 的过程中，我们用另一个 dp 求解出他应该从某个状态转移到另一个状态。
考虑一下这道题，首先求 LCS 的 dp 如下：
\[dp_{i,j}=\max\{dp_{i-1,j},dp_{i,j-1},dp_{i-1,j-1}+[s_i==t_j]\} \]显然，当\(i\)固定的时候，\(dp_{i,j}\)是单调不降的，且相邻两个数的差\(\in[0,1]\)，考虑直接状压这个东西，其实相当于就是在说当\(i\)一定的时候，这个\(dp\)识字长什么样。
考虑设\(f_{i,S,0/1/2}\)表示当考虑了兑奖串的前\(i\)位的时候，LCS 的\(dp\)式子状压下来为\(S\)，最后几位同NOI的匹配到了第几位，此时的方案数。
设\(sta_{S,j}\)表示 LCS 的\(dp\)式子状压下来为\(S\)后新加入一位\(j\)后的\(dp\)式子状压下来的情况，具体求解类似LCS 的内层 \(dp\)。
状态转移：
\[f_{i,sta_{S,x},nxt_{y,x}}\to f_{i,sta_{S,x},nxt_{y,x}}+f_{i-1,S,y} \]\(nxt_{x,y}\)表示下一个NOI匹配的状态，初始状态设\(f_{0,0,0}=1\)。
时间为\(\mathcal{O}(n2^k+k2^k)\)，注意状态压缩。
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define p_b push_back
#define m_p make_pair
#define pii pair<int,int>
#define val first
#define id second
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
#define gcd __gcd
#define lowbit(x) (x&(-x))
#define popcount __builtin_popcount
using namespace std;
int rd(){
int x=0,f=1; char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if (ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
void write(int x){
if(x>9) write(x/10);
putchar('0'+x%10);
}
const int N=1000+5,M=15,INF=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
int sta[(1<<M)+5][3],f[2][(1<<M)+5][3],dp[2][M<<1],nxt[3][3]={{1,0,0},{1,2,0},{1,0,3}};
int n,m,b[M<<1],state,ans[N];
void init(){
for(int s=0;s<=state;s++){
for(int i=0;i<m;i++) dp[0][i+1]=dp[0][i]+((s>>i)&1);
for(int j=0;j<=2;j++){
for(int i=1;i<=m;i++){
dp[1][i]=max(dp[1][i-1],dp[0][i]);
if(b[i]==j) dp[1][i]=max(dp[1][i],dp[0][i-1]+1);
}
int S=0;
for(int i=1;i<=m;i++) if(dp[1][i]>dp[1][i-1]) S|=(1<<(i-1));
sta[s][j]=S;
}
}
}
void add(int &x,int y){
x+=y;
if(x>mod)x-=mod;
}
signed main(){
n=rd(),m=rd();
for(int i=1;i<=m;i++){
char ch=getchar();while(ch<'A'||ch>'Z') ch=getchar();
if(ch=='N') b[i]=0;
else if(ch=='O') b[i]=1;
else b[i]=2;
}
state=(1<<m)-1;
init();
int now=1;
f[0][0][0]=1;
for(int i=1;i<=n;i++){
memset(f[now],0,sizeof(f[now]));
for(int s=0;s<=state;s++){//上一个的状压
for(int x=0;x<=2;x++){//现在第i个加入啥
for(int y=0;y<=2;y++){//之前匹配到了第几位
int tmp=nxt[y][x];
if(tmp==3) continue;
add(f[now][sta[s][x]][tmp],f[now^1][s][y]);
}
}
}
now^=1;
}
now^=1;
for(int s=0;s<=state;s++){
for(int i=0;i<=2;i++){
add(ans[popcount(s)],f[now][s][i]);
}
}
for(int i=0;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}