题目描述

给定字符串 $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$。

输出格式

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

1
GTC
10

1
22783
528340
497452

数据范围

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