题目描述

给定一个排列$P = (P_1, P_2, \ldots, P_N)$，其中$P$是$(1, 2, \ldots, N)$的一个排列。

打印出满足以下条件的长度为$N$的整数序列$A = (A_1, A_2, \ldots, A_N)$的数量，对$998244353$取模。

• 对于每个$i = 1, 2, \ldots, N$，满足$1 \leq A_i \leq M$。
• 整数序列$A$在字典序上小于整数序列$(A_{P_1}, A_{P_2}, \ldots, A_{P_N})$。

什么是字典序？

整数序列$X = (X_1,X_2,\ldots,X_N)$在满足以下条件的整数$i$存在时，称其比整数序列$Y = (Y_1,Y_2,\ldots,Y_N)$字典序小：

• 对于所有满足$1 \leq j \leq i-1$的整数$j$，满足$X_j=Y_j$。
• 满足$X_i < Y_i$。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 10^9$
• $1 \leq P_i \leq N$
• $i \neq j \implies P_i \neq P_j$
• 输入中的所有值都是整数。

输入

输入数据从标准输入读取，格式如下：

$N$ $M$ $P_1$ $P_2$ $\ldots$ $P_N$

输出

打印出满足题目描述条件的长度为$N$的整数序列$A$的数量，对$998244353$取模。

示例输入 1

4 2
4 1 3 2

示例输出 1

6

满足题目条件的整数序列$A$有$6$个，分别是$(1, 1, 1, 2)$，$(1, 1, 2, 2)$，$(1, 2, 1, 2)$，$(1, 2, 2, 2)$，$(2, 1, 1, 2)$和$(2, 1, 2, 2)$。
例如，当$A = (1, 1, 1, 2)$时，我们有$(A_{P_1}, A_{P_2}, A_{P_3}, A_{P_4}) = (2, 1, 1, 1)$，其在字典序上大于$A$。

示例输入 2

1 1
1

示例输出 2

0

没有满足题目条件的长度为$N$的整数序列$A$，因此应该输出$0$。

示例输入 3

20 100000
11 15 3 20 17 6 1 9 5 19 10 16 7 8 12 2 18 14 4 13

示例输出 3

55365742