AT_abc238_f [ABC238F] Two Exams

[problemUrl]: https://atcoder.jp/contests/abc238/tasks/abc238_f 高橋王国にて、 $ 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\ \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 $ を出力することとなります。