← 返回题目列表

Codeforces · 2172/G

G. 基因编辑器

中文机器翻译题面 查看原题

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

这些生物体无性繁殖,这意味着后代通常继承相同的基因序列。然而,由于繁殖过程中偶尔出现的克隆错误,可能会发生突变。生物学家观察到这些错误可以采取以下形式:

  1. 插入子字符串 AA 位于基因序列中的任何位置。
  2. 删除子字符串 AA 来自基因序列中的任意位置;其余部分在不改变顺序的情况下连接起来。
  3. 插入子字符串 BBB 位于基因序列中的任何位置。
  4. 删除子字符串 BBB 来自基因序列中的任意位置;其余部分在不改变顺序的情况下连接起来。
  5. 在基因序列的任意位置插入特殊子字符串$$$s$$$。
  6. 删除基因序列中任意位置的子串$$$s$$$;其余部分在不改变顺序的情况下连接起来。

这些突变可能在单个克隆事件期间发生多次,并且总是按顺序发生,一次一个。

例如,假设 $$$s = \texttt{ABAB}$$$。具有基因序列的生物体 阿巴巴 可以产生具有基因序列的后代 A 通过以下一系列突变:

生物学家拥有一种具有特定基因序列$$$t$$$的生物体。他们还对基因序列长度为 $$$n$$$ 的所有可能的生物体感兴趣。由于基因序列中的每个位置都可以是 A or B,总共有$$$2^n$$$个这样的生物。

问题是:给定字符串 $$$s$$$、$$$t$$$ 和 $$$n$$$,通过如上所述的一系列有效突变操作,可以从具有基因序列 $$$t$$$ 的生物体中产生多少个 $$$2^n$$$ 生物体(即长度为 $$$n$$$ 的所有基因序列)?

由于答案可能非常大,因此输出对 $$$998244353$$$ 取模的结果。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量$$$q$$$。测试用例的描述如下。

第一行包含字符串$$$s$$$,表示特殊子字符串。

第二行包含字符串$$$t$$$,表示给定的基因序列。

第三行包含一个整数$$$n$$$,代表感兴趣的生物体长度。

  • $$$1 \le q \le 10$$$
  • $$$2 \le |s| \le 11$$$
  • $$$s$$$ 中的第一个字符是 A.
  • $$$s$$$ 中的最后一个字符是 B.
  • 没有两个连续的 A位于 $$$s$$$ 中。
  • 没有连续三个 B位于 $$$s$$$ 中。
  • $$$1 \le |t| \le 10^5$$$
  • $$$1 \le n \le 10^9$$$

输出

对于每个测试用例,在一行中打印一个整数,表示对 $$$998244353$$$ 取模的答案。

示例

输入
复制

2
ABAB
AABAB
1
ABAB
A
7

输出
复制

1
22