P13947 [EC Final 2019] Permutation

给定一个排列 $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$ 取模。

由 ChatGPT 4.1 翻译