T2 命运的X

题目信息

时间限制: 1s

空间限制: 128M

输入文件: x.in

输出文件: x.out

题目描述

你要生成一个数列 $A$，满足以下条件：

1. 数列 $A$ 无限长。
2. 数列 $A$ 的每个元素是 $[1,m]$ 之中等概率随机的某个数字。

现在，你还没有生成这个具体的数列 $A$。你希望猜一下，给定一个数列 $B$，数列 $B$ 最早在数列 $A$ 的哪个结束位置 $x$ 出现？

即，最早出现的结束位置是最小的正整数 $x$ 同时满足，

$$A_{x}=B_n,A_{x-1}=B_{n-1},...,A_{x-(n-1)}=B_{1}$$

请你计算出 $x$ 的期望值，对 $998244353$ 取模。

对于任何一个既约分数 $P/Q$，如果 $Q$ 与 $998244353$ 互质，则可以证明存在唯一的整数 $R$ 满足 $0\le R < 998244353$ 且 $RQ=P \pmod{998244353}$。定义这个 $R$ 为 $P/Q \pmod {998244353}$。

输入格式

包含多组测试数据，第一行一个正整数 $T$ 代表数据组数。

每组数据两行，第一行两个正整数 $m, n$，代表元素值域与 $B$ 的长度。 第二行 $n$ 个正整数，代表 $B$，保证 $B$ 中元素也在 $[1, m]$ 内。

输出格式

$T$ 行，每行一个整数，代表期望 $\pmod {998244353}$ 的值。

样例

样例输入 1

1
2 2
1 2

样例输出 1

4

样例解释 1

设长度为 $x$ 的前缀刚好是最短前缀的概率是 $F(x)$。

可以得到 $F(x)=\frac{x-1}{2^x}$ 这是因为这个前缀必须是形如 $\underbrace{22 \ldots 2}_{\# \geq 0} \underbrace{11 \ldots 1}_{\# \geq 0} 12$ 的, 最后必须有 12 , 而前面不能有 12 , 也就是 2 必须在 1 前面。符合这样形式的显然只有 $x-1$ 种。

故答案 $=\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		$\leq 10^5$
4	$\leq 10$
5,6	$\leq 350$
7,8	$\leq 2 \times 10^5$		$B$ 序列元素全部相同
9,10			无

$T\leq 10$