A < AP

时间限制：2s
空间限制：1024MB

题目描述

给定一个 $1$ 到 $N$ 的排列 $P=(P_1,P_2,\ldots,P_N)$。

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

• 对所有 $1\le i\le N$，有 $1\le A_i\le M$；
• $A$ 的字典序严格小于 $(A_{P_1},A_{P_2},\ldots,A_{P_N})$。

若两个等长序列 $X,Y$ 在第一个不同的位置 $i$ 上满足 $X_i<Y_i$，则称 $X$ 的字典序严格小于 $Y$。

输入格式

第一行输入两个整数 $N,M$。

第二行输入 $N$ 个整数 $P_1,P_2,\ldots,P_N$。

输出格式

输出答案对 $998244353$ 取模后的结果。

样例输入 1

4 2
4 1 3 2

样例输出 1

6

样例输入 2

1 1
1

样例输出 2

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

数据范围

对于所有数据，$1\le N\le 2\times 10^5$，$1\le M\le 10^9$，且 $P$ 是 $1$ 到 $N$ 的排列。