题目描述

给定字符串 $S$，字符集 AGCT，定义 $\text{LCS}(S,T)$ 为字符串 $S$ 和 $T$ 的最长公共子序列

对于每个 $0\le i\le|S|$，求有多少个长为 $m$ 、字符集 AGCT 的字符串 $T$ 满足 $\text{LCS}(S,T)=i$，答案对 $10^{9}+7$ 取模

输入格式

第一行一个整数 $T$ 表示数据组数

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

$T\le5,|S|\le15,m\le1000$

输出格式

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

1
GTC
10

1
22783
528340
497452