题目描述

$(1,\ 2,\ \ldots,\ N)$ の順列 $P\ =\ (P_1,\ P_2,\ \ldots,\ P_N)$ が与えられます。

下記の $2$ つの条件をともに満たす長さ $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)$ より辞書順で小さいとは、下記の $2$ つの条件をともに満たす整数 $1\ \leq\ i\ \leq\ N$ が存在することを言います。

• $1\ \leq\ j\ \leq\ i-1$ を満たすすべての整数 $j$ について、$X_j\ =\ Y_j$
• $X_i\ \lt\ Y_i$

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

問題文中の $2$ つの条件をともに満たす整数列 $A$ の個数を $998244353$ で割ったあまりを出力せよ。

题目大意

Description

给定一个 $1\sim N$ 的排列 $P$，找到符合以下条件的 $A$ 数组的数量 $\bmod 998244353$。

• 对于 $1\sim N$ 的每一个 $i$，$1\le A_i\le M$。
• $A$ 数组字典序小于 $(A_{P_1},A_{P_2},\cdots,A_{P_n})$ 数组。

4 2
4 1 3 2

6

1 1
1

0

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$
• 入力はすべて整数

Sample Explanation 1

問題文中の $2$ つの条件をともに満たす整数列 $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$ より辞書順で大きいです。