分数: 500 点
问题陈述
在高桥王国, N 编号为公民 1 to N 参加了竞争性编程考试。
有两次测试,西铁城 i 排名 P_i- 第一个测试中的第一个和 Q_i- 第二次测试中的第一个。
两项测试均没有平局。也就是说,每个序列 P 和 Q 是一个排列 (1, 2, ..., N).
王国总统伊吕波即将选择 K 公民代表国家队参加即将举行的世界竞技编程锦标赛。
国家队成员的选择必须满足以下条件。
- 不应该有一对公民 (x, y) 其中西铁城
选择 x 并且西铁城
未选择 y 使得 P_x > P_y 和 Q_x > Q_y.
- 换句话说,如果公民 y 的排名低于公民 x 在两次测试中都不允许选择Citizen x 未选择 Citizen 时 y.
首先,伊吕波想知道满足上述条件的国家队公民选拔方式有多少种。找到它来帮助她。
由于这个数字可能很大,因此打印它的模 998244353.
约束
- 输入中的所有值都是整数。
- 1 \le N \le 300
- 1 \le K \le N
- 每个 P 和 Q 是一个排列 (1,2,...,N).
输入
输入由标准输入按以下格式给出:
N K P_1 P_2 \dots P_N Q_1 Q_2 \dots Q_N
输出
将答案打印为整数。
示例输入 1
4 2 2 4 3 1 2 1 4 3
示例输出 1
3
- 选择西铁城即可 1 和公民 2 为团队。
- 如果公民 选择 1 和公民 3 ,公民 4 排名高于西铁城 3 在两次测试中都做了,所以这对 (x,y)=(3,4) 将违反问题陈述中的条件。 选择
- 选择西铁城即可 1 和公民 4.
- 如果公民 选择 2 和公民 3 ,该对 (x,y)=(3,1) 将违反条件。
- 选择西铁城即可 2 和公民 4.
- 如果公民 选择 3 和公民 4 ,该对 (x,y)=(3,1) 将违反条件。
最终答案是 3.
示例输入 2
33 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
示例输出 2
168558757
全部 \binom{33}{16} = 1166803110 选择方式 16 来自 33 公民满足要求。
因此,我们应该打印 1166803110 模数 998244353,即 168558757.
示例输入 3
15 7 4 9 7 5 6 13 2 11 3 1 12 14 15 10 8 4 14 9 12 7 15 1 2 8 11 3 5 13 6 10
示例输出 3
23