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'~ is the grid after the operation is completed, then for all ~1 \leq r \leq N~, ~G'_{r,1} = A_r~ and for all ~2 \leq c \leq N~, ~G'_{r, c} = 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'~ is the grid after the operation is completed, then for all ~1 \leq c \leq N~, ~G'_{1,c} = B_c~ and for all ~2 \leq r \leq N~, ~G'_{r, c} = 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 \leq N \leq 10^6~

~1 \leq A_i, B_i \leq 2N~

Subtask 1 [30%]

~1 \leq N \leq 2000~

~A_i = 1~ and ~B_i = 2~

Subtask 2 [40%]

~1 \leq N \leq 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