嗯。。本人的第二篇blog，想想有点激动。
其实这篇blog是我在学习DP套DP的时候临时想到要发一篇blog。
网上关于DP套DP的资料不多，在百度上搜DP套DP大多数都是搜到这道题的题解，虽然题解大致说了DP套DP的原理，但对代码没有多少解释，以至于像我这种蒟蒻根本理解不了啊。。。。
于是在苟且抄了题解后，根据自己的理解写了注释，也希望对后来的人有帮助。
注：我是根据Candy? 的blog写的代码。 （其实就是换了变量名QwQ）.
如果不太了解求lcs的dp方程，建议先去看一看。。
其实 这道题 (因为蒟蒻太弱，不确定是不是DP套DP的套路) 代码分两部分，因为T字符串每个字符在AGCT随便取，所以每一位的转移都是一样的，那么我们可以预处理出状态转移的通式，对于T的每一位都是这样的，那么我们只要转移 m 次就好。
如果你看了本文仍然不会DP套DP的话，没关系，我也不会。。。
不用来问我了（雾）。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define gch getchar
#define pch putchar
#define LL long long
#define INF 0xfffffff
using namespace std;
template <class X> inline void read(X &x){
char c=getchar();x=0;X flag=1;
while(c>'9'||c<'0') {if(c=='-') flag=-1;c=getchar();}
while(c<='9'&&c>='0') {x=x*10+c-48;c=getchar();}
x*=flag;
}
template <class X> inline void print(X x){
if(x<0) {putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
const int MAXN=20;
const int MAXM=1005;
const int MAX=1<<15|5;
const int MO=1000000000+7;
int n,m;char s[MAXN],c[MAXN]="ACGT";
int trans[MAX][4],one[MAX],f[2][MAX];
int ans[MAXM];
//转移矩阵trans[i][k]:当前LCS状态为i的情况下T串填字符k能到的状态。
//One[j]:状态 j 对应的最长公共子序列。
inline void init(){
static int d[MAXN],g[MAXN];//d[j],g[j]：相当于lcs[i][j]的后面一维。
//两者区别在于，d[j]是lcs[i-1],g[j]是lcs[i];
for(int j=0;j<(1<<n);++j){//枚举lcs[i-1]的状态。
for(int i=0;i<n;++i)
d[i+1]=d[i]+((j&(1<<i))?1:0);
//因为用差分压缩，所以用前缀和解压。
one[j]=d[n];
//One[j]就是j状态对应的最长公共子序列，自然就是我们算出来的d[n]啦。
//此后枚举所有可能的状态。
for(int k=0;k<4;++k){//枚举T的某一位(假想的一位,模拟lcs dp 的过程)可能的四种情况:A,C,G,T;
for(int i=1;i<=n;++i){//枚举S的第几位。
g[i]=max(g[i-1],d[i]);
if(c[k]==s[i]) g[i]=max(g[i],d[i-1]+1);
//lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1],(a[i]==b[j])lcs[i-1][j-1]+1);
}
trans[j][k]=0;
for(int i=0;i<n;++i)
if(g[i+1]-g[i]) trans[j][k]|=1<<i;
//把g数组压缩。
}
}
}
int main(){
int t;read(t);
while(t--){
memset(s,0,sizeof s);
memset(ans,0,sizeof ans);
memset(f,0,sizeof f);
scanf("%s",s+1);
n=strlen(s+1);read(m);
//printf("n:%d m:%d
",n,m);
init();
//预处理出转移矩阵:trans[j][k]和每种状态对应的lcs:one[j];
int cur=0;
f[0][0]=1;
for(int i=1;i<=m;++i){
cur^=1;
memset(f[cur],0,sizeof f[cur]);
for(int j=0;j<(1<<n);j++){
for(int k=0;k<4;++k){
f[cur][trans[j][k]]+=f[cur^1][j];
f[cur][trans[j][k]]%=MO;
}
}
}
//状态转移,滚动数组优化一维。
for(int j=0;j<(1<<n);++j){
ans[one[j]]+=f[cur][j];
ans[one[j]]%=MO;
}
for(int i=0;i<=n;++i){
print(ans[i]);pch('
');
}
}
return 0;
}