CF2172G.Gene Editor

Biologists have recently discovered an interesting phenomenon in a particular type of organism. Each organism possesses a gene sequence consisting exclusively of two types of genes, represented by the characters A and B.

These organisms reproduce asexually, meaning that the offspring usually inherit an identical gene sequence. However, due to occasional cloning errors during reproduction, mutations may occur. Biologists have observed that these errors can take the following forms:

1. Inserting the substring AA at any position in the gene sequence.
2. Removing the substring AA from any position in the gene sequence; the remaining parts are concatenated without altering their order.
3. Inserting the substring BBB at any position in the gene sequence.
4. Removing the substring BBB from any position in the gene sequence; the remaining parts are concatenated without altering their order.
5. Inserting a special substring $s$ at any position in the gene sequence.
6. Removing the substring $s$ from any position in the gene sequence; the remaining parts are concatenated without altering their order.

These mutations may occur multiple times during a single cloning event and always happen sequentially, one at a time.

For example, suppose $s = \texttt{ABAB}$. An organism with gene sequence ABBABBA could produce an offspring with gene sequence A through the following series of mutations:

The biologists possess an organism with a specific gene sequence $t$. They are also interested in all possible organisms whose gene sequences have length $n$. Since each position in a gene sequence can be either A or B, there are $2^n$ such organisms in total.

The question is: Given strings $s$, $t$, and $n$, how many of these $2^n$ organisms (that is, all gene sequences of length $n$) can be produced from the organism with gene sequence $t$ through a sequence of valid mutation operations as described above?

Since the answer may be very large, output the result modulo $998244353$.

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

这些生物进行无性繁殖，即子代通常继承与亲代完全相同的基因序列。然而，由于繁殖过程中偶尔发生的克隆错误，可能会发生突变。生物学家观察到，这些错误可能表现为以下形式：

1. 在基因序列的任意位置插入子串 AA；
2. 从基因序列的任意位置删除子串 AA；其余部分按原顺序拼接；
3. 在基因序列的任意位置插入子串 BBB；
4. 从基因序列的任意位置删除子串 BBB；其余部分按原顺序拼接；
5. 在基因序列的任意位置插入一个特殊子串 $s$；
6. 从基因序列的任意位置删除子串 $s$；其余部分按原顺序拼接。

这些突变可能在一次克隆事件中多次发生，且总是按顺序逐次进行。

例如，设 $s = \texttt{ABAB}$。一个基因序列为 ABBABBA 的生物可通过如下一系列突变产生基因序列为 A 的后代：

生物学家手中有一个基因序列为 $t$ 的生物。他们还关心所有长度为 $n$ 的可能生物（即所有长度为 $n$ 的基因序列）。由于基因序列每个位置只能是 A 或 B，因此总共有 $2^n$ 种这样的生物。

问题为：给定字符串 $s$、$t$ 和整数 $n$，在这 $2^n$ 个长度为 $n$ 的基因序列中，有多少个可以通过对序列 $t$ 施加若干次上述合法突变操作而得到？

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

Each test contains multiple test cases. The first line contains the number of test cases $q$. The description of the test cases follows.

The first line contains the string $s$, representing the special substring.

The second line contains the string $t$, representing the given gene sequence.

The third line contains an integer $n$, representing the interested length of organisms.

• $1 \le q \le 10$
• $2 \le |s| \le 11$
• The first character in $s$ is A.
• The last character in $s$ is B.
• There are no two consecutive A's in $s$.
• There are no three consecutive B's in $s$.
• $1 \le |t| \le 10^5$
• $1 \le n \le 10^9$

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$

For each test case, print an integer in one line, representing the answer modulo $998244353$.

对于每个测试用例，在一行中输出一个整数，表示答案对 $998244353$ 取模的结果。