問題文

(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 とする。

制約

• 1 \leq N \leq 200000
• P,Q は (1,2,\dots,N) の順列
• 入力は全て整数

部分点

• N \leq 3000 を満たすデータセットに正解した場合は、30 点与えられる。
• 追加制約のないデータセットに正解した場合は、上記とは別に 70 点与えられる。

入力例 1

3
2 3 1
1 3 2

出力例 1

6

S=000,001,010,101,011,111(4:16 修正) の 6 通りがありえます。

入力例 2

5
3 4 2 1 5
3 1 2 5 4

出力例 2

11

入力例 3

10
9 2 10 3 4 8 6 7 5 1
7 8 3 4 1 6 5 2 10 9

出力例 3

43