P10614 BZOJ3864 Hero meet devil

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$.

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$.

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

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