Problem7263--ABC273 —— G - Row Column Sums 2

7263: ABC273 —— G - Row Column Sums 2

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 2Submit Num: 2StatisticsShowOff!

Description

Find the number, modulo 998244353, of square matrices of size N whose elements are non-negative integers, that satisfy both of the following two conditions:
  • for all $i = 1, 2, \ldots, N$, the sum of the elements in the i-th row is $R_i$;
  • for all $i = 1, 2, \ldots, N$, the sum of the elements in the i-th column is $C_i$.
Note that $R_i$ and $C_i$ given in the input are integers between 0 and 2 (see Constraints).

Input

The input is given from Standard Input in the following format:
$N$
$R_1\ R_2\ \ldots\ R_N$
$C_1\ C_2\ \ldots\ C_N$

Output

Print the answer.

Constraints

$1≤N≤5000$
$0 \leq R_i \leq 2$
$0 \leq C_i \leq 2$
All values in the input are integers.

Sample 1 Input 

3
1 1 1
0 1 2

Sample 1 Output 

3
The following 3 matrices satisfy the conditions: 


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 2 Input 

3
1 1 1
2 2 2

Sample 2 Output 

0

Sample 3 Input 

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

Sample 3 Output 

968235177

Source/Category

 
Submit