102385: [AtCoder]ABC238 F - Two Exams

Problem Statement

In the Kingdom of Takahashi, $N$ citizens numbered $1$ to $N$ took an examination of competitive programming.
There were two tests, and Citizen $i$ ranked $P_i$-th in the first test and $Q_i$-th in the second test.
There were no ties in either test. That is, each of the sequences $P$ and $Q$ is a permutation of $(1, 2, ..., N)$.

Iroha, the president of the kingdom, is going to select $K$ citizens for the national team at the coming world championship of competitive programming.
The members of the national team must be selected so that the following is satisfied.

• There should not be a pair of citizens $(x, y)$ where Citizen $x$ is selected and Citizen $y$ is not selected such that $P_x > P_y$ and $Q_x > Q_y$.
  • In other words, if Citizen $y$ got a rank smaller than that of Citizen $x$ in both tests, it is not allowed to select Citizen $x$ while not selecting Citizen $y$.

To begin with, Iroha wants to know the number of ways to select citizens for the national team that satisfy the condition above. Find it to help her.
Since this number can be enormous, print it modulo $998244353$.

Constraints

• All values in input are integers.
• $1 \le N \le 300$
• $1 \le K \le N$
• Each of $P$ and $Q$ is a permutation of $(1,2,...,N)$.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer as an integer.

Sample Input 1

4 2
2 4 3 1
2 1 4 3

Sample Output 1

3

• It is fine to select Citizen $1$ and Citizen $2$ for the team.
• If Citizen $1$ and Citizen $3$ are selected, Citizen $4$ ranked higher than Citizen $3$ did in both tests, so the pair $(x,y)=(3,4)$ would violate the condition in the Problem Statement.
• It is fine to select Citizen $1$ and Citizen $4$.
• If Citizen $2$ and Citizen $3$ are selected, the pair $(x,y)=(3,1)$ would violate the condition.
• It is fine to select Citizen $2$ and Citizen $4$.
• If Citizen $3$ and Citizen $4$ are selected, the pair $(x,y)=(3,1)$ would violate the condition.

The final answer is $3$.

Sample Input 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

Sample Output 2

168558757

All $\binom{33}{16} = 1166803110$ ways of selecting $16$ from the $33$ citizens satisfy the requirement.
Therefore, we should print $1166803110$ modulo $998244353$, that is, $168558757$.

Sample Input 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

Sample Output 3

23

问题描述

在Takahashi王国，编号为1到N的N位公民参加了一场编程竞赛。

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

两场测试都没有平局。即，$P$和$Q$序列都是$(1, 2, ..., N)$的排列。

Iroha，该国的总统，打算从将要参加的国际编程竞赛中选出$K$位公民组成国家队。

国家队的成员必须满足以下条件：

• 不应该存在一个公民对$(x, y)$，其中公民$x$被选中，公民$y$未被选中，且$P_x > P_y$和$Q_x > Q_y$。
• 换句话说，如果公民$y$在两场测试中都获得了比公民$x$更高的排名，那么在选中公民$x$的同时不选中公民$y$是不允许的。

首先，Iroha想知道满足上述条件的选人方式有多少种。帮助她找出答案。

由于这个数字可能非常庞大，请将它模$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

从33位公民中选出16位公民的$\binom{33}{16} = 1166803110$种方式都满足要求。

因此，我们应该输出$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