Problem Description

You are given a string $S$ over the alphabet ACGT. Define $\text{LCS}(S,T)$ as the longest common subsequence of two strings $S$ and $T$.

For each $0 \leq i \leq |S|$, find how many strings $T$ of length $m$ over the alphabet ACGT satisfy $|\text{LCS}(S,T)| = i$. Output the answer modulo $10^9+7$.

Input Format

The first line contains an integer $T$, the number of test cases.

For each test case, the first line contains a string $S$, and the second line contains an integer $m$.

Output Format

For each test case, output the answers for $i = 0,1,\dots,|S|$, one per line.

1
GTC
10

1
22783
528340
497452

Hint

For $100\%$ of the testdata, it is guaranteed that $1 \leq T \leq 5$, $1 \leq |S| \leq 15$, $1 \leq m \leq 1000$.

Translated by ChatGPT 5