两场考试

题目描述

在 Takahashi 王国,编号为 $1$ 到 $N$ 的 $N$ 名公民参加了一场编程竞赛的考试。

共有两场测验,公民 $i$ 在第一场测验中排名第 $P_i$,在第二场测验中排名第 $Q_i$。

两场测验都没有并列名次。也就是说,序列 $P$ 和 $Q$ 都是 $(1, 2, ..., N)$ 的排列。

Iroha 是王国的总统,她将从公民中选出 $K$ 人组成国家队,参加即将到来的世界编程锦标赛。

国家队成员的选取必须满足以下条件:

不应存在一对公民 $(x, y)$,使得公民 $x$ 被选中、公民 $y$ 未被选中,且 $P_x \gt P_y$ 且 $Q_x \gt Q_y$。

换句话说,如果公民 $y$ 在两场测验中的排名都比公民 $x$ 高,则不允许只选中公民 $x$ 而不选中公民 $y$。

首先,Iroha 想知道满足上述条件的选人方案有多少种。请你帮她求出答案。

由于这个数量可能非常巨大,请对 $998244353$ 取模后输出。

输入格式

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

$N$ $K$
$P_1$ $P_2$ $\dots$ $P_N$
$Q_1$ $Q_2$ $\dots$ $Q_N$

输出格式

以整数形式输出答案。

样例

4 2
2 4 3 1
2 1 4 3

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$。

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

168558757

从 33 名公民中选 16 人的全部 $\binom{33}{16} = 1166803110$ 种方案都满足要求。

因此,应输出 $1166803110$ 对 $998244353$ 取模的结果,即 $168558757$。

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

23

数据范围

• 输入中的所有值均为整数。
• $1 \le N \le 300$
• $1 \le K \le N$
• $P$ 和 $Q$ 都是 $(1,2,...,N)$ 的排列。