← 返回题目列表

AtCoder · abc387_f

I. 计数数组

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

分数: 550 点

问题陈述

给你正整数 N, M,以及一个序列 A = (A_1, A_2, \dots, A_N) 长度 N,每个元素是介于 1 和 N,包括在内。

求模数 998244353,序列 x = (x_1, x_2, \dots, x_N) 长度 N,每个元素是介于 1 和 M,包含在内,满足以下条件:

  • x_i \leq x_{A_i} 对于每个 i (1 \leq i \leq N).

约束

  • 1 \leq N, M \leq 2025
  • 1 \leq A_i \leq N
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 A_2 \dots A_N

输出

打印答案。


示例输入 1

3 3
2 1 1

示例输出 1

6

序列 x=(1,1,1),(2,2,1),(2,2,2),(3,3,1),(3,3,2),(3,3,3) 满足条件。


示例输入 2

4 9
1 1 1 1

示例输出 2

2025

示例输入 3

10 5
9 4 5 5 4 2 1 5 7 2

示例输出 3

10010