题目描述

在一次探险中，小 H 发现了一个古老的封印。封印的本体是一个长度为 $n$ 的序列 $A = [a_1, a_2, \ldots, a_n]$。初始，每个元素都是 $1$ 至 $m$ 间的正整数。

设 $|A|$ 表示序列 $A$ 的长度，小 H 可以对序列进行以下修改：

1. 选择序列 $A$ 的某个严格前缀最大值元素 $a_s$，即选择 $1 \leq s \leq |A|$ 满足 $\forall 1 \leq j < s$，$a_s > a_j$，特别地，$a_1$ 总是序列 $A$ 的严格前缀最大值；

2. 若 $a_s \neq 1$，将 $(a_s - 1)$ 插入序列 $A$ 的尾端；

3. 删去序列 $A$ 的前 $s$ 个元素。

考虑如下例子：在 $A = [1, 3, 2, 3, 4]$ 时，

• 小 H 可以选择 $s = 1$，此时修改后的序列变为 $[3, 2, 3, 4]$；

• 小 H 可以选择 $s = 2$，此时修改后的序列变为 $[2, 3, 4, 2]$；

• 小 H 不能选择 $s = 4$，因为 $a_2 = a_4 = 3$，这意味着 $a_4$ 并非严格前缀最大值。

小 H 可以进行任意多次修改操作，也可以不进行任何修改。为了解开封印，小 H 想知道：通过以上修改操作，他可以得到多少种不同的非空序列。

认为两个序列 $A = [a_1, \ldots, a_n]$ 和 $B = [b_1, \ldots, b_m]$ 不同，当且仅当 $n \neq m$ 或 $\exists 1 \leq i \leq \min{n, m}$，$a_i \neq b_i$。

由于答案可能很大，你只需告诉小 H 答案对 $998,244,353$ 取模后的结果。

输入格式

从文件 seal.in 中读入数据。

本题有多组测试数据。输入的第一行两个整数 $c$, $T$，分别表示测试点编号和测试数据组数，接下来输入每组测试数据。样例满足 $c = 0$。

对于每组测试数据，第一行两个整数 $n$, $m$，分别表示序列长度与值域，第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，描述序列 $A$。

输出格式

输出到文件 seal.out 中。

对于每组测试数据输出一行一个整数，表示通过修改操作可以得到的非空序列个数，对 $998,244,353$ 取模。

样例 1

输入：

0 4
3 2
1 2 1
4 3
3 1 2 1
5 4
1 3 2 3 4
7 5
4 4 5 2 3 3 1

输出：

4
7
20
59

该组样例共有 $4$ 组测试数据。

• 对于第一组测试数据，可以通过修改得到的非空序列有 $[1, 2, 1]$，$[2, 1]$，$[1, 1]$，$[1]$。

• 对于第二组测试数据，可以通过修改操作得到的非空序列有 $[3, 1, 2, 1]$，$[1, 2, 1, 2]$，$[2, 1, 2]$，$[1, 2, 1]$，$[2, 1]$，$[1, 1]$，$[1]$。

样例 2

输入：

0 2
11 10
8 8 8 9 9 8 8 9 9 9 8
12 2500
1529 1470 1361 1416 1492 1503 1641 1868 1829 1959 2052 2105

输出：

694
4961744

样例 3

见选手目录下的 seal/seal3.in 与 seal/seal3.ans。

该组样例满足测试点 $3 \sim 5$ 的限制。

样例 4

见选手目录下的 seal/seal4.in 与 seal/seal4.ans。

该组样例满足测试点 $10$ 的限制。

样例 5

见选手目录下的 seal/seal5.in 与 seal/seal5.ans。

该组样例满足测试点 $11 \sim 14$ 的限制。

样例 6

见选手目录下的 seal/seal6.in 与 seal/seal6.ans。

该组样例满足测试点 $15$ 的限制。

样例 7

见选手目录下的 seal/seal7.in 与 seal/seal7.ans。

该组样例满足测试点 $17 \sim 19$ 的限制。

样例 8

见选手目录下的 seal/seal8.in 与 seal/seal8.ans。

该组样例满足测试点 $22 \sim 25$ 的限制。

子任务

对于所有测试点，

• $1 \leq T \leq 10$，

• $1 \leq n, m \leq 2500$，

• $\forall 1 \leq i \leq n$，$1 \leq a_i \leq m$。

测试点编号	$n \leq$	$m \leq$	特殊性质
1,2	10		无
3~5	18	70
6			A
7,8			AB
9	70		A
10			AB
11~14			无
15	300		A
16			AB
17~19			无
20	2500		A
21			AB
22~25			无

• 特殊性质 A：$\forall 1 \leq i < j \leq n$，$a_i \neq a_j$。

• 特殊性质 B：$\forall 1 \leq i < n$，$a_i < a_{i+1}$。