题目背景

你在一条安静的小巷里经营着一家果摊。每天清晨，你都会把来货按“品质签”贴上标签后摆上架。每一件水果都会被随机贴上一个品质签，取值为 1 到 m 之间的某个数字——这不是评分，只是你给不同产地/批次随手做的记号，方便自己回溯。 你还没真正开始贴签，但你的朋友已经把一张“目标小票”递给你，上面记录了一个想要观察到的签号序列 B：B1, B2, ..., Bn。他打赌说：“从你开始贴签那一刻起，多久（以第几件水果为结束）能第一次看到这段连续的签号恰好和我的小票一样？”

清晨的阳光很柔和，你不妨先算一算这个“第一次出现的结束位置”的期望值。

题目描述

请你设想一个无限长的序列 $A$ 表示你依次贴下去的品质签，其中：

1. $A$ 无限长；
2. 每个 $A_i$ 都是从区间 $[1,m]$ 等概率独立随机选择的一个数字。

在你真正贴签之前，给定一个长度为 $n$ 的序列 $B$（元素也都在 $[1,m]$ 内），我们关心 $B$ 在 $A$ 中最早一次出现的“结束位置” $x$ 的期望值。 形式化地，最早的结束位置 $x$ 是满足

$$A_x=B_n,\;A_{x-1}=B_{n-1},\;\ldots,\;A_{x-(n-1)}=B_1$$

的最小正整数 $x$。

请你计算这个期望的数值，并对模数 $998244353$ 取模后输出。

关于分数取模 对任何既约分数 $P/Q$，若 $Q$ 与 $998244353$ 互质，则存在唯一整数 $R$ 使 $0\le R<998244353$ 且 $RQ\equiv P\pmod{998244353}$。定义 $R$ 为 $P/Q \bmod 998244353$。

输入格式

多组测试数据。 第一行一个正整数 $T$ 表示数据组数。 接下来每组数据两行：

• 第一行两个正整数 $m,n$；
• 第二行 $n$ 个正整数，表示序列 $B$（保证每个元素在 $[1,m]$ 内）。

输出格式

输出 $T$ 行，每行一个整数，表示所求期望 $\bmod\, 998244353$ 的结果。

样例

样例输入 1

1
2 2
1 2

样例输出 1

4

样例解释 1

把长度为 $x$ 的前缀恰好是首次包含小票模式的概率记为 $F(x)$。 当 $m=2, B=(1,2)$ 时，必须以 “…12” 结尾且前面从未出现过 “12”。等价地，这个前缀形如

$$\underbrace{22\ldots2}_{\#\ge0}\ \underbrace{11\ldots1}_{\#\ge0}\ 12$$

最后两位固定为 1,2，且 2 要先于 1 出现。这样的前缀共有 $x-1$ 种，且每个长度为 $x$ 的序列概率为 $2^{-x}$，故

$$F(x)=\frac{x-1}{2^x},\quad \mathbb{E}[x]=\sum_{x=2}^{\infty} x\,F(x)=\sum_{x=2}^{\infty}\frac{x(x-1)}{2^x}=4.$$

样例输入 2

1
54321 5
114 514 19 19 810

样例输出 2

229803184

数据范围与提示

测试点	$n$	$m$	特殊性质
1	$=2$	$=2$	无
2,3		$\le 10^5$
4	$\le 10$
5,6	$\le 350$
7,8	$\le 2\times 10^5$		$B$ 元素全部相同
9,10			无

$T\le 10$。

---