Однажды 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\).
Выходные данные
Выведите, сколько строк порождают данный суффиксный массив. Поскольку число может быть очень большим, выведите ответ по модулю \(998244353\).
Примечание
В первом примере «abb» является единственным возможным решением.
Во втором примере можно легко показать, что не существует возможных строк, так как все буквы должны быть одинаковыми.
В четвертом примере одной из возможных строк является «ddbacef».
Пожалуйста, не забывайте выводить свои ответы по модулю \(998244353\).