该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

2025/3/2 21:01 民间数据 v1.0

题目描述

在一次探险中，小 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

输入 #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

输入 #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]$。

【样例 3】

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

该组样例满足测试点 3 ~ 5 的限制。

【样例 4】

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

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

【样例 5】

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

该组样例满足测试点 11 ~ 14 的限制。

【样例 6】

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

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

【样例 7】

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

该组样例满足测试点 17 ~ 19 的限制。

【样例 8】

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

该组样例满足测试点 22 ~ 25 的限制。

【子任务】

对于所有测试点，

• $1\leq T\leq 10$，
• $1\leq n,m\leq 2500$，
• $\forall 1\leq i\leq n$，$1\leq a_i\leq m$。

特殊性质 A：$\forall 1 \leq i < j \leq n, a_i \neq a_j$。 特殊性质 B：$\forall 1 \leq i < n, a_i < a_{i+1}$。