CF1526E.Oolimry and Suffix Array

Once upon a time, Oolimry saw a suffix array. He wondered how many strings can produce this suffix array.

More formally, given a suffix array of length $n$ and having an alphabet size $k$, count the number of strings that produce such a suffix array.

Let $s$ be a string of length $n$. Then the $i$-th suffix of $s$ is the substring $s[i \ldots n-1]$. A suffix array is the array of integers that represent the starting indexes of all the suffixes of a given string, after the suffixes are sorted in the lexicographic order. For example, the suffix array of oolimry is $[3,2,4,1,0,5,6]$ as the array of sorted suffixes is $[\texttt{imry},\texttt{limry},\texttt{mry},\texttt{olimry},\texttt{oolimry},\texttt{ry},\texttt{y}]$.

A string $x$ is lexicographically smaller than string $y$, if either $x$ is a prefix of $y$ (and $x\neq y$), or there exists such $i$ that $x_i \lt y_i$, and for any $1\leq j \lt i$ , $x_j = y_j$.

很久以前，Oolimry 看到了一个后缀数组。他好奇：有多少个字符串能生成该后缀数组？

更形式化地，给定一个长度为 $n$ 的后缀数组以及字母表大小 $k$，请计算能生成该后缀数组的字符串个数。

设 $s$ 是一个长度为 $n$ 的字符串，则 $s$ 的第 $i$ 个后缀是子串 $s[i \ldots n-1]$。后缀数组是一个整数数组，其元素表示原字符串所有后缀在按字典序排序后的起始下标。例如，字符串 $\texttt{oolimry}$ 的后缀数组为 $[3,2,4,1,0,5,6]$，因为其按字典序排序后的后缀序列为 $[\texttt{imry},\texttt{limry},\texttt{mry},\texttt{olimry},\texttt{oolimry},\texttt{ry},\texttt{y}]$。

字符串 $x$ 在字典序上小于字符串 $y$，当且仅当以下任一条件成立：
（1）$x$ 是 $y$ 的真前缀（即 $x \neq y$ 且 $x$ 是 $y$ 的前缀）；
（2）存在某个下标 $i$，使得 $x_i \lt y_i$，且对任意 $1 \leq j \lt i$，均有 $x_j = y_j$。

The first line contain 2 integers $n$ and $k$ ($1 \leq n \leq 200000,1 \leq k \leq 200000$) — the length of the suffix array and the alphabet size respectively.

The second line contains $n$ integers $s_0, s_1, s_2, \ldots, s_{n-1}$ ($0 \leq s_i \leq n-1$) where $s_i$ is the $i$-th element of the suffix array i.e. the starting position of the $i$-th lexicographically smallest suffix. It is guaranteed that for all $0 \leq i \lt j \leq n-1$, $s_i \neq s_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 \lt j \leq n-1$，均有 $s_i \neq s_j$。

Print how many strings produce such a suffix array. Since the number can be very large, print the answer modulo $998244353$.

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

In the first test case, "abb" is the only possible solution.

In the second test case, it can be easily shown no possible strings exist as all the letters have to be equal.

In the fourth test case, one possible string is "ddbacef".

Please remember to print your answers modulo $998244353$.

在第一个测试用例中，“abb”是唯一的可能解。

在第二个测试用例中，可以很容易地证明不存在可能的字符串，因为所有字母都必须相等。

在第四个测试用例中，一个可能的字符串是“ddbacef”。

请注意，您的答案需对 $998244353$ 取模后输出。