题目描述

给定一个 $(1,\ 2,\ \ldots,\ N)$ 的排列 $P = (P_1,\ P_2,\ \ldots,\ P_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)$ 和 $Y = (Y_1,\ Y_2,\ \ldots,\ Y_N)$，如果存在整数 $1 \leq i \leq N$，使得以下两个条件都成立，则称 $X$ 的字典序严格小于 $Y$：

• 对于所有 $1 \leq j \leq i-1$，都有 $X_j = Y_j$。
• $X_i < Y_i$。

输入格式

输入以如下格式从标准输入读入。

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

输出格式

输出满足题目中两个条件的整数列 $A$ 的个数，对 $998244353$ 取模。

样例 1

输入

4 2
4 1 3 2

输出

6

样例 2

输入

1 1
1

输出

0

样例 3

输入

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

输出

55365742

说明/提示

数据范围

• $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$
• 输入均为整数

样例解释 1

满足题目中两个条件的整数列 $A$ 有 $(1,\ 1,\ 1,\ 2),\ (1,\ 1,\ 2,\ 2),\ (1,\ 2,\ 1,\ 2),\ (1,\ 2,\ 2,\ 2),\ (2,\ 1,\ 1,\ 2),\ (2,\ 1,\ 2,\ 2)$ 共 $6$ 个。例如，当 $A = (1,\ 1,\ 1,\ 2)$ 时，$(A\_{P\_1},\ A\_{P\_2},\ A\_{P\_3},\ A\_{P\_4}) = (2,\ 1,\ 1,\ 1)$，它的字典序大于 $A$。

由 ChatGPT 4.1 翻译