给定字符串 ，字符集 AGCT，定义 为字符串 和 的最长公共子序列。
AGCT
对于每个 ，求有多少个长为 、字符集 AGCT 的字符串 满足 ，答案对 取模。
第一行一个整数 表示数据组数。
对于每组数据，第一行一个字符串 ，第二行一个整数 。
对于每组数据，输出 时的答案，每个占一行。
1 GTC 10
1 22783 528340 497452
对于 的数据，保证 ，，。
