4120. [统一省选 2025]封印

【题目描述】

在一次探险中，小 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$ 取模后的结果。

【输入格式】

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

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

【输出格式】

对于每组测试数据输出一行一个整数，表示通过修改操作可以得到的非空序列个数，对 $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

【样例输出1】

4
7
20
59

【样例输入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

【样例输出2】

694
4961744

【样例说明】

样例 1：

该组样例共有 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]$。

【数据规模与约定】

【来源】

2025联合省选day2T3