Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Oolimry and Suffix Array

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOnce 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 < y_i$$$, and for any $$$1\leq j < i$$$ , $$$x_j = y_j$$$.

Input

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< j \leq n-1$$$, $$$s_i \neq s_j$$$.

Output

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

Examples

Input

3 2 0 2 1

Output

1

Input

5 1 0 1 2 3 4

Output

0

Input

6 200000 0 1 2 3 4 5

Output

822243495

Input

7 6 3 2 4 1 0 5 6

Output

36

Note

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$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/12/2021 14:37:02 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|