题目描述

Carol 的字符串弄丢了。

Carol 想复原她的字符串，但是她知道的信息太少了。她只知道这个字符串的长度、字符集大小，以及这个字符串各个后缀按字典序排序后的顺序。

具体而言，她有一个序列 $a$，第 $i$ 个元素代表字典序第 $i$ 小的后缀的左端点。例如 abb 对应的数组是 $[1,3,2]$。

Carol 知道这些信息难以还原出她的字符串，所以她只想求出符合她要求的字符串个数。由于这个数很大，你只需要求出它对 $998244353$ 取模的结果。

输入格式

第一行两个正整数 $n,k$，代表字符串的长度和字符集大小。

第二行 $n$ 个正整数 $a_i$，第 $i$ 个数代表字符串中字典序第 $i$ 小的后缀的左端点。

输出格式

一行一个整数，表示符合要求的字符串个数对 $998244353$ 取模的结果。

3 3
1 3 2

4

数据范围

• 对于 $30\%$ 的数据，$n,k \leq 5$；
• 对于另外 $30\%$ 的数据，$k \leq 2$；
• 对于 $100\%$ 的数据，$1 \leq n,k \leq 2\cdot 10^5$。