P10614 BZOJ3864 Hero meet devil

给定一个字符集为 `ACGT` 的字符串 $S$。定义 $\text{LCS}(S,T)$ 为两个字符串 $S,T$ 的最长公共子序列。 对于每个 $0\leq i \leq |S|$，求有多少个长度为 $m$，字符集 `ACGT` 的字符串 $T$，满足 $|\text{LCS}(S,T)|=i$，答案对 $10^9+7$ 取模。

第一行一个整数 $T$ 表示数据组数。 对于每组数据，第一行一个字符串 $S$，第二行一个整数 $m$。

对于每组数据，输出 $i=0,1,\dots,|S|$ 时的答案，每个占一行。

对于 $100\%$ 的数据，保证 $1\leq T\leq 5$，$1\leq |S| \leq 15$，$1\leq m\leq 1000$。