Description：

一个字符串 $S$ 只由 $AGCT$ 组成，对于每个 $i$ ，求只由 $AGCT$ 组成的长为 $m$ 的字符串 $T$ 个数，使得 $LCS(T,S)=i$ 。

$1\leqslant m\leqslant 10^3,1\leqslant |S|\leqslant 15$

Solution：

考虑求 $LCS$ 那个 $DP$ ： $$ f[i][j]=\max(\max(f[i-1][j],f[i][j-1]),f[i-1][j-1]+[T[i]=S[j]]) $$ 如果我们只看第二维的话会发现第二维单调不降，并且相邻两个只差 $1$ ，那么我们考虑把差分数组状压起来，然后每次往 $T$ 后面加一个字符，预处理子 $DP$ 每个状态往后面加一个字符 $c$ 能转移到的状态计数即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 1010

#define MAXM 17

#define MAX 15

char c[MAXM];

int toint(char c)

{

	if(c == 'A')return 0;if(c == 'G')return 1;

	if(c == 'C')return 2;if(c == 'T')return 3;

}

int S[MAXM];

int g[1 << MAX][4];

int dp[2][MAXN];

int bit(int s,int i){return ((s >> (i - 1)) & 1);}

int f[2][1 << MAX];

int ans[MAXM];

#define MOD 1000000007

void work()

{

	scanf("%s",c + 1);

	m = strlen(c + 1);

	scanf("%d",&n);

	for(int i = 1;i <= m;++i)S[i] = toint(c[i]);

	for(int i = 0;i < (1 << m);++i)

	{

		for(int x = 0;x < 4;++x)

		{

			for(int k = 1;k <= m;++k)dp[0][k] = dp[0][k - 1] + bit(i,k);

			for(int k = 1;k <= m;++k)dp[1][k] = max(max(dp[0][k],dp[1][k - 1]),dp[0][k - 1] + (x == S[k]));

			int s = 0;

			for(int k = 1;k <= m;++k)s |= ((dp[1][k] - dp[1][k - 1]) << (k - 1));

			g[i][x] = s;

		}

	}

	memset(f,0,sizeof(f));

	int cur = 0;

	f[0][0] = 1;

	for(int i = 1;i <= n;++i)

	{

		cur ^= 1;

		memset(f[cur],0,sizeof(f[cur]));

		for(int s = 0;s < (1 << m);++s)

		{

			for(int x = 0;x < 4;++x)

			{

				f[cur][g[s][x]] = (f[cur][g[s][x]] + f[cur ^ 1][s]) % MOD;

			}

		}

	}

	memset(ans,0,sizeof(ans));

	for(int s = 0;s < (1 << m);++s)

	{

		int sum = 0;

		for(int k = 1;k <= m;++k)sum += (s >> (k - 1)) & 1;

		ans[sum] = (ans[sum] + f[cur][s]) % MOD;

	}

	for(int i = 0;i <= m;++i)printf("%d\n",ans[i]);	

	return;

}

int main()

{

	int testcases = rd();

	while(testcases--)work();

	return 0;

}