题目描述

非負整数を要素とする $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$ 以下の整数であることに注意してください（制約参照）。

输入格式

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

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

输出格式

答えを出力せよ。

题目大意

给定正整数 $N$ 和两个长为 $N$ 的序列 $R_i, C_i$，求有多少个 $N\times N$ 的矩阵满足以下条件:

• 所有元素是非负整数。
• 对于所有 $1\leq i\leq N$，第 $i$ 行上所有元素之和为 $R_i$。
• 对于所有 $1\leq i\leq N$，第 $i$ 列上所有元素之和为 $C_i$。

$C_i$ , $R_i$ 都是 $0$ 到 $2$ 之间的整数。

答案对 $998,244,353$ 取模。

3
1 1 1
0 1 2

3

3
1 1 1
2 2 2

0

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

968235177

提示

制約

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

Sample Explanation 1

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

Sample Explanation 3

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