题目背景

淡く煌(きらめ)く傷口が

瞬間 世界を止めて

---

长夜伴浪破晓梦，梦晓破浪伴夜长。

题目描述

给定正整数 $k$，本题的字符集大小为 $k$，我们用正整数 $i$ 来表示字符集中的第 $i$ 个字符。

给定正整数 $m$，定义一个字符串 $\mathcal{S}$ 为「动听」的，当且仅当 $\mathcal{S}$ 的长度小于 $m+2$，或在 $\mathcal{S}$ 中任意删除恰好 $m$ 个字符后都不存在一个长度大于 $1$ 的回文连续子串。

你需要处理 $q$ 次询问，每次给定一个长度为 $m+2$ 且「动听」的字符串 $T$，和一个不可重字符集合 $U$，试求出有几个长度为 $n$ 的字符串，满足以下条件：

• $T$ 为该字符串的一段前缀
• 该字符串是「动听」的
• 字符串最后一位属于 $U$

答案对 $998244353$ 取模。对于每组询问，$k$ 和 $m$ 是相同的。

注意：本题数据保证 $k-m\ge3$。

输入格式

第一行包含一个整数 $c$ 表示测试点编号。样例满足 $c = 0$。

第二行包含四个整数 $q,k,m$。分别表示询问次数、字符集大小和判定字符串为「动听」时所用到的常数。

接下来 $q$ 行，每行包含一个询问。依次输入一个正整数 $n$，一个长度为 $m+2$ 的正整数序列 $T$，一个正整数 $|U|$ 表示集合 $U$ 的大小，和 $|U|$ 个正整数表示 $U$ 中的元素。其定义见题目描述。

输出格式

对于每次询问，输出一行一个整数表示所求的答案。

0
1 5 1
5 1 2 3 1 1

2

0
1 5 1
7 1 2 3 2 1 2

6

0
1 40 4
50 2 3 5 7 11 31 2 5 10

732767443

0
1 12 1
12 3 5 7 1 7

32390928

提示

【样例 1 解释】

相当于给定一个串 abc，$U = \{a\}$，字符集合为 $\{a,b,c,d,e\}$，询问有多少长度为 $5$ 的串满足题意，容易发现有且仅有以下 $2$ 个：

abcda
abcea

故答案为 $2$。

【样例 2 解释】

相当于给定一个串 abc，$U = \{a,b\}$，字符集合为 $\{a,b,c,d,e\}$，询问有多少长度为 $7$ 的串满足题意，容易发现有且仅有以下 $6$ 个：

abceadb
abcdeab
abcedba
abcdeba
abcedab
abcdaeb

故答案为 $6$。

【数据范围】

对于所有测试点保证：$1 \leq n \leq 10^7$，$1 \leq q,m \leq 2 \times 10^3$，$m + 3 \leq k\le 10^9$，$U \subseteq [1,k]$，$T_i \in [1,k]$。

测试点编号	$q=$	$n\le$	$m=$	$\sum\vert U\vert=$	特殊性质
$1$	$700$		$100$	$700$	$k-m=3$
$2$					无
$3$	$10^3$	$5\times 10^5$	$20$	$4\times 10^3$
$4$	$2\times 10^3$		$100$	$4\times10^3$
$5$				$10^6$
$6$		$2.5\times 10^5$	$10^3$	$4\times 10^3$
$7$		$5\times 10^5$	$2\times 10^3$
$8$		$2.5\times 10^5$	$10^3$	$10^6$
$9$		$5\times 10^5$	$2\times 10^3$
$10$		$10^7$		$2\times 10^6$