行列和 2

题目描述

求大小为 $N$、元素均为非负整数的方阵中,同时满足以下两个条件的方阵的个数,对 $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$

输出格式

输出答案。

样例

3
1 1 1
0 1 2

3

以下 $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

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

注意要对 $998244353$ 取模后输出。

数据范围

• $1 \le N \le 5000$
• $0 \le R_i \le 2$
• $0 \le C_i \le 2$
• 输入中的所有值均为整数。