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