配点 : $500$ 点

問題文

高橋王国にて、 $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$ で割った余りを出力してください。

制約

• 入力は全て整数
• $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$

出力

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

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