AT_pakencamp_2024_day3_1_m Two Permutations

$ (1,2,\dots,N) $ の順列 $ P,Q $ が与えられます。 以下の手順で生成されうる長さ $ N $ の $ 01 $ 列 $ S $ の個数を $ 998244353 $ で割った余りを求めてください。 - 以下を満たすような $ (1,2,\dots,2N) $ の順列 $ R $ を用意する。 - 任意の整数 $ i (1 \leq i \leq N) $ について、 $ R_1,R_2,\dots,R_N $ における $ P_i $ 番目に小さい要素は $ R_i $ である。 - 任意の整数 $ i (1 \leq i \leq N) $ について、 $ R_{N+1},R_{N+2},\dots,R_{2N} $ における $ Q_i $ 番目に小さい要素は $ R_{N+i} $ である。 - $ i=1,2,\dots,N $ について、 $ R_i < R_{N+i} $ ならば $ S_i=1 $ 、 $ R_i > R_{N+i} $ ならば $ S_i=0 $ とする。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ P_1 $ $ P_2 $ $ \dots $ $ P_N $ $ Q_1 $ $ Q_2 $ $ \dots $ $ Q_N $

答えを出力せよ。

### 部分点 - $ N \leq 3000 $ を満たすデータセットに正解した場合は、 $ 30 $ 点与えられる。 - 追加制約のないデータセットに正解した場合は、上記とは別に $ 70 $ 点与えられる。 ### Sample Explanation 1 $ S=000,001,010,101,011,111 $ (4:16 修正) の $ 6 $ 通りがありえます。 ### Constraints - $ 1 \leq N \leq 200000 $ - $ P,Q $ は $ (1,2,\dots,N) $ の順列 - 入力は全て整数