题目描述

给定一个排列 $p_1, p_2, \dots, p_n$。你可以重复进行以下操作：

• 选择一个区间 $p_{l}, p_{l+1}, \dots, p_{l+c}$（$l \geq 1, l+c \leq n$），如果 $p_l$ 是该区间中的最小元素，则你可以任意排列 $p_{l+1}, \dots, p_{l+c}$。
• 选择一个区间 $p_{l}, p_{l+1}, \dots, p_{l+c}$（$l \geq 1, l+c \leq n$），如果 $p_{l+c}$ 是该区间中的最小元素，则你可以任意排列 $p_{l}, \dots, p_{l+c-1}$。

你想知道通过这些操作，最多可以得到多少种不同的排列。答案可能很大，请输出对 $998244353$ 取模后的结果。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量（$1\le T\le 100000$）。

每个测试用例的第一行包含两个整数 $n$ 和 $c$（$2\le c \le 500000$，$2\le n\le 500000$）。所有测试用例中 $n$ 的总和不超过 $500000$。

每个测试用例的第二行包含一个排列 $p_1,\ldots, p_n$（$1\le p_i\le n$）。

输出格式

对于每个测试用例，输出一行答案，对 $998244353$ 取模。

5
5 3
3 4 2 1 5
5 4
4 2 1 3 5
5 2
4 5 3 1 2
5 3
4 3 2 1 5
5 2
2 3 1 5 4

6
1
4
6
4

提示

由 ChatGPT 4.1 翻译