← 返回题目列表

AtCoder · arc179_b

B. B 与 B 之间

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

分数: 500 点

问题陈述

给你一个序列 (X_1, X_2, \dots, X_M) 长度 M 由之间的整数组成 1 和 M,包括在内。

求模数 998244353,序列 A = (A_1, A_2, \dots, A_N) 长度 N 由之间的整数组成 1 和 M,包含在内,满足以下条件:

  • 对于每个 B = 1, 2, \dots, M,值 X_B 存在于任何两个不同的出现之间 B in A (包括两端)。

更正式地说,对于每个 B = 1, 2, \dots, M,必须满足以下条件:

  • 对于每对整数 (l, r) 这样 1 \leq l < r \leq N 和 A_l = A_r = B,存在一个整数 m (l \leq m \leq r) 这样 A_m = X_B.

约束

  • 1 \leq M \leq 10
  • 1 \leq N \leq 10^4
  • 1 \leq X_i \leq M
  • 所有输入值均为整数。

输入

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

M N
X_1 X_2 \cdots X_M

输出

打印答案。


示例输入 1

3 4
2 1 2

示例输出 1

14

以下是序列示例 A 满足条件:

  • (1, 3, 2, 3)
  • (2, 1, 2, 1)
  • (3, 2, 1, 3)

以下是非示例:

  • (1, 3, 1, 3)
    • 没有 X_3 = 2 之间 3s。
  • (2, 2, 1, 3)
    • 没有 X_2 = 1 之间 2s。

示例输入 2

4 8
1 2 3 4

示例输出 2

65536

所有长度序列 8 由之间的整数组成 1 和 4 满足条件。

请注意,当 X_B = B,总是有一个 B 两次不同出现之间 B.


示例输入 3

4 9
2 3 4 1

示例输出 3

628