题目描述

高橋王国にて、 $1$ から $N$ までの番号のついた $N$ 人の国民が競技プログラミングの試験に参加しました。
試験は $2$ 回からなり、人 $i$ は $1$ 回目の試験で $P_i$ 位、 $2$ 回目の試験で $Q_i$ 位となりました。
なお、どちらの試験においても、複数人が同じ順位になることはありませんでした。すなわち、順位を表す数列 $P,Q$ はそれぞれ $(1,2,...,N)$ の順列です。

高橋王国の大統領であるいろはちゃんは、この試験の結果に基づいて、 $N$ 人の中から競技プログラミングの世界大会に出場する $K$ 人の代表を決めることになりました。
代表を決めるにあたって、以下が成立していなければなりません。

• 人 $x$ が代表であり、人 $y$ が代表でないような人の組 $(x,y)$ であって、 $P_x\ >\ P_y$ かつ $Q_x\ >\ Q_y$ であるようなものが存在してはならない。
  • 言い換えると、 $2$ 回の試験の双方で人 $y$ が人 $x$ よりも小さい順位を取っているにも拘らず、人 $x$ が代表で人 $y$ が代表でないということがあってはならない。

いろはちゃんは、ひとまず上記の条件を満たす代表の選び方の数を知りたいので、この数を求めてください。
ただし、この数は非常に大きくなる場合もあるので、 $998244353$ で割った余りを出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを整数として出力せよ。

题目大意

在高桥王国，编号为1到N的N名国民参加了比赛程序设计的考试。

考试由2次组成，国民i在第1次考试中为第 $P_i$ 位、第2次考试中成为了第 $Q_i$ 位。

另外，无论在哪个考试中，都不会有多人排名相同。也就是说，表示名次的数列P、Q分别是（1,2、…、N）的排列。

高桥王国的总统伊吕波，根据这个考试的结果，决定从N人中选出K人作为参加竞技编程世界大会的代表。

如果国民x是代表，国民y不是代表的人，必须满足 $P_x>P_y$ 且$Q_x>Q_y$。

换句话说，尽管两次考试双方都可能国民y的排名比国民x小，但不能有国民x是代表而国民y不是代表的情况。

伊吕波想知道满足上述条件选择代表的方法的数量，请求这个数量除以998244353的余数。

4 2
2 4 3 1
2 1 4 3

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

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)$ の順列である。

Sample Explanation 1

- 人 $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$ 通りです。

Sample Explanation 2

$33$ 人から $16$ 人を選ぶ $\binom{33}{16}\ =\ 1166803110$ 通りの全てにおいて、問題文中の条件を満たします。 よって、 $1166803110$ を $998244353$ で割った余りである $168558757$ を出力することとなります。