配点 : $500$ 点

問題文

$(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})$ より辞書順で小さい。

制約

• $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$

出力

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

4 2
4 1 3 2

6

問題文中の $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$ より辞書順で大きいです。

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