#include
using namespace std;
const int mod = 1e9 + 7; const int maxs = 17; const int maxst = (1 « 15) + 3; const char deoxynucleotide[5] = “AGCT”;
#define mInc(a,b) {
a += b;
if (a >= mod)
a -= mod;
}
int n, m, f[2][maxst], ans[maxs]; int trv[maxst][4]; char s[maxs];
int getTrans(int i, int j) { static int fc[maxs], fd[maxs]; fc[0] = fd[0] = 0; for (int k = 0; k < n; ++ k) fc[k + 1] = fc[k] + ((i » k) & 1); for (int k = 1; k <= n; ++ k) { if (s[k] == deoxynucleotide[j]) fd[k] = fc[k - 1] + 1; else if (fc[k] > fd[k - 1]) fd[k] = fc[k]; else fd[k] = fd[k - 1]; } int sn(0); for (int k = 0; k < n; ++ k) sn |= (fd[k + 1] - fd[k]) « k; return sn; }
void sov() { scanf("%s%d", s + 1, &m); n = strlen(s + 1); memset(f, 0, sizeof(f)); int cur(0), prv(1), e(1 « n); for (int i = 0; i < e; ++ i) for (int j = 0; j < 4; ++ j) trv[i][j] = getTrans(i, j); f[cur][0] = 1; for (int fi = 0; fi < m; ++ fi) { swap(cur, prv); memset(f[cur], 0, sizeof(f[cur])); for (int i = 0; i < e; ++ i) if (f[prv][i]) { for (int j = 0; j < 4; ++ j) mInc(f[cur][trv[i][j]], f[prv][i]); } } memset(ans, 0, sizeof(ans)); for (int i = 0; i < e; ++ i) if (f[cur][i]) { int j(i), c(0); for (; j; j »= 1) if (j & 1) ++ c; mInc(ans[c], f[cur][i]); } for (int i = 0; i <= n; ++ i) printf("%d\n", ans[i]); }
int main() { #ifndef ONLINE_JUDGE freopen(".in", “r”, stdin); #endif
int t;
scanf("%d", &t);
while (t --)
sov();
}