問題文

非負整数を要素とする $N$ 次正方行列であって、下記の $2$ つの条件をともに満たすものの個数を $998244353$ で割ったあまりを出力してください。

• すべての $i = 1, 2, \\ldots, N$ について、$i$ 行目の要素の和は $R_i$ である。
• すべての $i = 1, 2, \\ldots, N$ について、$i$ 列目の要素の和は $C_i$ である。

入力で与えられる $R_i$ および $C_i$ は $0$ 以上 $2$ 以下の整数であることに注意してください（制約参照）。

制約

• $1 \\leq N \\leq 5000$
• $0 \\leq R_i \\leq 2$
• $0 \\leq C_i \\leq 2$
• 入力はすべて整数

入力

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

$N$ $R_1$ $R_2$ $\\ldots$ $R_N$ $C_1$ $C_2$ $\\ldots$ $C_N$

出力

答えを出力せよ。

入力例 1

3
1 1 1
0 1 2

出力例 1

3

条件を満たす行列は下記の $3$ つです。

0 1 0
0 0 1
0 0 1
``````plain
0 0 1
0 1 0
0 0 1
``````plain
0 0 1
0 0 1
0 1 0

入力例 2

3
1 1 1
2 2 2

出力例 2

0

入力例 3

18
2 0 1 2 0 1 1 2 1 1 2 0 1 2 2 1 0 0
1 1 0 1 1 1 1 1 1 1 1 1 2 1 1 0 2 2

出力例 3

968235177

$998244353$ で割ったあまりを出力することに注意してください。