A16611 | Gene Editor

生物学家最近在一种特定的生物体中发现了一个有趣的现象。每个生物体都拥有仅由两种类型基因组成的基因序列，这两类基因分别用字符 A 和 B 表示。

这些生物体通过无性繁殖产生后代，通常后代会继承完全相同的基因序列。然而，由于复制过程中偶尔出现的克隆错误，可能会发生变异。生物学家观察到，这些错误可能以以下形式出现：

1. 在基因序列的任意位置插入子串 AA。
2. 从基因序列的任意位置移除子串 AA，剩余部分会按原有顺序拼接。
3. 在基因序列的任意位置插入子串 BBB。
4. 从基因序列的任意位置移除子串 BBB，剩余部分会按原有顺序拼接。
5. 在基因序列的任意位置插入特殊子串 $s$。
6. 从基因序列的任意位置移除子串 $s$，剩余部分会按原有顺序拼接。

这些变异在一次克隆事件中可能发生多次，并且总是按顺序、一次只进行一种。

例如，假设 $s = \texttt{ABAB}$。拥有基因序列 ABBABBA 的生物体可以通过如下变异过程，最终生成基因序列 A 的后代：


生物学家们现在拥有一个基因序列为 $t$ 的生物体。他们同时对所有长度为 $n$ 的基因序列的生物体感兴趣。由于序列中的每个位置都可以是 A 或 B，这样符合条件的生物体总数为 $2^n$ 个。

问题是：给定字符串 $s$、$t$ 和 $n$，在所有 $2^n$ 个长度为 $n$ 的基因序列中，有多少个可以通过一系列上述有效变异操作，从基因序列为 $t$ 的生物体得到？

由于答案可能非常大，请输出答案对 $998244353$ 取模后的结果。

每组测例包含多个测试用例。第一行为测试用例个数 $q$。接下来为每个测试用例的详细信息：

- 第一行为字符串 $s$，表示特殊子串。
- 第二行为字符串 $t$，表示起始基因序列。
- 第三行为整数 $n$，表示感兴趣的基因序列长度。

- $1 \le q \le 10$
- $2 \le |s| \le 11$
- $s$ 的第一个字符为 A。
- $s$ 的最后一个字符为 B。
- $s$ 中不存在两个连续的 A。
- $s$ 中不存在三个连续的 B。
- $1 \le |t| \le 10^5$
- $1 \le n \le 10^9$

每个测试用例输出一行，表示答案对 $998244353$ 取模后的值。