题目描述

给定一个字符集为 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|$ 时的答案，每个占一行。

输入输出样例 #1

输入 #1

1
GTC
10

输出 #1

1
22783
528340
497452

说明/提示

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