You have a $N\times N$ grid of integers $G$ which is initially filled with $0$s. You are also given arrays $A$ and $B$ of length $N$. You can perform the following two operations any number of times and in any order on the grid:

1. Push $A$ onto the first column of $G$. All columns move to the right by one, with the last column being deleted. Formally, if $G^{\prime }$ is the grid after the operation is completed, then for all $1\le r\le N$, $G_{r,1}^{\prime }=A_r$ and for all $2\le c\le N$, $G_{r,c}^{\prime }=G_{r,c-1}$.
2. Push $B$ onto the first row of $G$. All rows move down by one, with the last row being deleted. Formally, if $G^{\prime }$ is the grid after the operation is completed, then for all $1\le c\le N$, $G_{1,c}^{\prime }=B_c$ and for all $2\le r\le N$, $G_{r,c}^{\prime }=G_{r-1,c}$.

What is the number of distinct grids with no $0$s that can be created? Since the answer may be very large, output it modulo ${10}^9+7$.

Constraints

$1\le N\le {10}^6$

$1\le A_i,B_i\le 2N$

Subtask 1 [30%]

$1\le N\le 2000$

$A_i=1$ and $B_i=2$

Subtask 2 [40%]

$1\le N\le 2000$

Subtask 3 [30%]

No additional constraints.

Input Specification

The first line contains a single integer, $N$.

The second line will contain $N$ space-separated integers, $A_1,A_2,\dots ,A_N$.

The third line will contain $N$ space-separated integers, $B_1,B_2,\dots ,B_N$.

Output Specification

Output a single integer representing the number of distinct grids that can be created modulo ${10}^9+7$.

Sample Input 1

1
1
1

Sample Output 1

1

Sample Input 2

1
1
2

Sample Output 2

2

Sample Input 3

2
1 1
1 2

Sample Output 3

3