{"raw_statement":[{"iden":"statement","content":"给定一个字符集为 `ACGT` 的字符串 $S$。定义 $\\text{LCS}(S,T)$ 为两个字符串 $S,T$ 的最长公共子序列。\n\n对于每个 $0\\leq i \\leq |S|$，求有多少个长度为 $m$，字符集 `ACGT` 的字符串 $T$，满足 $|\\text{LCS}(S,T)|=i$，答案对 $10^9+7$ 取模。"},{"iden":"input","content":"第一行一个整数 $T$ 表示数据组数。\n\n对于每组数据，第一行一个字符串 $S$，第二行一个整数 $m$。"},{"iden":"output","content":"对于每组数据，输出 $i=0,1,\\dots,|S|$ 时的答案，每个占一行。"},{"iden":"note","content":"对于 $100\\%$ 的数据，保证 $1\\leq T\\leq 5$，$1\\leq |S| \\leq 15$，$1\\leq m\\leq 1000$。"}],"translated_statement":null,"sample_group":[["1\nGTC\n10","1\n22783\n528340\n497452"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}