Score : $500$ points

问题描述

在高桥王国中，编号为 $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$，那么不允许在不选择公民 $y$ 的情况下选择公民 $x$。

首先，いろは想知道满足上述条件的国家队成员选拔方案的数量。请帮助她找到这个数量。
由于这个数字可能会非常大，请将结果对 $998244353$ 取模后输出。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 10:17:58