問題文

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

制約

• $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$ で割ったあまりを出力せよ。

入力例 1

4 2
4 1 3 2

出力例 1

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

入力例 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