E. Oolimry и суффиксный массив
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды Oolimry увидел суффиксный массив. Ему стало интересно, сколько строк могут дать этот суффиксный массив.

Более формально, для данного суффиксного массив длины $$$n$$$ и размера алфавита $$$k$$$, подсчитайте количество строк, которые порождают такой суффиксный массив.

Пусть $$$s$$$ — строка длины $$$n$$$. Тогда $$$i$$$-й суффикс $$$s$$$ — это подстрока $$$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$$$.

Входные данные

Первая строка содержит 2 целых числа $$$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$$$.

Примеры
Входные данные
3 2
0 2 1
Выходные данные
1
Входные данные
5 1
0 1 2 3 4
Выходные данные
0
Входные данные
6 200000
0 1 2 3 4 5
Выходные данные
822243495
Входные данные
7 6
3 2 4 1 0 5 6
Выходные данные
36
Примечание

В первом примере «abb» является единственным возможным решением.

Во втором примере можно легко показать, что не существует возможных строк, так как все буквы должны быть одинаковыми.

В четвертом примере одной из возможных строк является «ddbacef».

Пожалуйста, не забывайте выводить свои ответы по модулю $$$998244353$$$.