分数: 1000 点
问题陈述
给定一个整数序列 (X_1,\dots,X_M) 长度 M 组成 1,\dots,K.
查找序列数 (A_1,\dots,A_N) 长度 N 组成 1,\dots,K 满足以下条件,模 998244353:
- 在所有长度序列中 M 组成 1,\dots,K,唯一不能作为(不一定是连续的)子序列获得的序列 (A_1,\dots,A_N) is (X_1,\dots,X_M).
约束
- 2\le M,K \le N \le 400
- 1\le X_i \le K
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M K X_1 X_2 \dots X_M
输出
打印满足条件的序列数,模 998244353.
示例输入 1
5 2 3 1 1
示例输出 1
4
以下四个序列满足条件:
- (2, 3, 1, 2, 3)
- (2, 3, 1, 3, 2)
- (3, 2, 1, 2, 3)
- (3, 2, 1, 3, 2)
示例输入 2
400 3 9 1 8 6
示例输出 2
417833302
示例输入 3
29 3 10 3 3 3
示例输出 3
495293602
示例输入 4
29 3 10 3 3 4
示例输出 4
0