AT_arc151_b [ARC151B] A < AP

给定一个 $ (1,\ 2,\ \ldots,\ N) $ 的排列 $ P = (P_1,\ P_2,\ \ldots,\ P_N) $。 请输出满足以下两个条件的长度为 $ 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) $，如果存在整数 $ 1 \leq i \leq N $，使得以下两个条件都成立，则称 $ X $ 的字典序严格小于 $ Y $： - 对于所有 $ 1 \leq j \leq i-1 $，都有 $ X_j = Y_j $。 - $ X_i < Y_i $。

输入以如下格式从标准输入读入。 > $ N $ $ M $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

输出满足题目中两个条件的整数列 $ 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 $ - 输入均为整数 ### 样例解释 1 满足题目中两个条件的整数列 $ 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 $。 由 ChatGPT 4.1 翻译