生物学家最近在一种特定类型的生物体中发现了一个有趣的现象。每个生物体都拥有一个仅由两种类型的基因组成的基因序列,由字符表示 A 和 B.
这些生物体无性繁殖,这意味着后代通常继承相同的基因序列。然而,由于繁殖过程中偶尔出现的克隆错误,可能会发生突变。生物学家观察到这些错误可以采取以下形式:
- 插入子字符串 AA 位于基因序列中的任何位置。
- 删除子字符串 AA 来自基因序列中的任意位置;其余部分在不改变顺序的情况下连接起来。
- 插入子字符串 BBB 位于基因序列中的任何位置。
- 删除子字符串 BBB 来自基因序列中的任意位置;其余部分在不改变顺序的情况下连接起来。
- 在基因序列的任意位置插入特殊子字符串$$$s$$$。
- 删除基因序列中任意位置的子串$$$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$$$ 取模的答案。
示例
输入复制
2ABABAABAB1ABABA7
输出复制
1 22