AT_arc151_b [ARC151B] A < AP

[problemUrl]: https://atcoder.jp/contests/arc151/tasks/arc151_b $ (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 $ で割ったあまりを出力せよ。

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