CF1526E Oolimry and Suffix Array

很久以前，Oolimry 看到了一个后缀数组。他想知道有多少个字符串可以生成这个后缀数组。 更正式地说，给定一个长度为 $n$ 的后缀数组和一个字母表大小为 $k$，请计算有多少个字符串能够生成该后缀数组。 设 $s$ 是一个长度为 $n$ 的字符串。那么 $i$ 的后缀是子串 $s[i \ldots n-1]$。后缀数组是一个整数数组，表示给定字符串的所有后缀在按字典序排序后的起始下标。例如，字符串 oolimry 的后缀数组为 $[3,2,4,1,0,5,6]$，因为排序后的后缀数组为 $[\texttt{imry},\texttt{limry},\texttt{mry},\texttt{olimry},\texttt{oolimry},\texttt{ry},\texttt{y}]$。 字符串 $x$ 在字典序上小于字符串 $y$，当且仅当 $x$ 是 $y$ 的前缀（且 $x \neq y$），或者存在某个 $i$ 使得 $x_i < y_i$，并且对于所有 $1 \leq j < i$，都有 $x_j = y_j$。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 200000, 1 \leq k \leq 200000$），分别表示后缀数组的长度和字母表的大小。 第二行包含 $n$ 个整数 $s_0, s_1, s_2, \ldots, s_{n-1}$（$0 \leq s_i \leq n-1$），其中 $s_i$ 是后缀数组的第 $i$ 个元素，即第 $i$ 小的字典序后缀的起始位置。保证对于所有 $0 \leq i < j \leq n-1$，都有 $s_i \neq s_j$。

输出有多少个字符串可以生成该后缀数组。由于答案可能非常大，请输出对 $998244353$ 取模后的结果。

在第一个测试用例中，"abb" 是唯一可能的解。 在第二个测试用例中，可以很容易地证明不存在可能的字符串，因为所有字母都必须相同。 在第四个测试用例中，一个可能的字符串是 "ddbacef"。 请记得输出对 $998244353$ 取模后的答案。 由 ChatGPT 4.1 翻译