← 返回题目列表

AtCoder · arc151_b

B. A小于AP

中文机器翻译题面 查看原题

分数: 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