分数: 500 点
问题陈述
给你一个排列 P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N).
打印整数序列的数量 A = (A_1, A_2, \ldots, A_N) 长度 N 满足以下两个条件,模 998244353.
- 1 \leq A_i \leq M 对于每个 i = 1, 2, \ldots, N.
- 整数序列 A 按字典顺序小于整数序列 (A_{P_1}, A_{P_2}, \ldots, A_{P_N}).
什么是字典顺序?
整数序列 X = (X_1,X_2,\ldots,X_N) is 按字典顺序较小 比整数序列 Y = (Y_1,Y_2,\ldots,Y_N) 当有一个整数时 1 \leq i \leq N 满足以下两个条件。
- 对于所有整数 j (1 \leq j \leq i-1), X_j=Y_j.
- X_i < 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
输出
打印整数序列的数量 A 长度 N 满足问题陈述中的两个条件,模 998244353.
示例输入 1
4 2 4 1 3 2
示例输出 1
6
六个整数序列 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).
例如,当 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