문제

Bessie has two arrays of length $N$ ($1 \le N \le 500$). The $i$-th element of the first array is $a_i$ ($1 \le a_i \le 10^6$) and the $i$-th element of the second array is $b_i$ ($1 \le b_i \le 10^6$).

Bessie wants to split both arrays into non-empty subarrays such that the following is true. Every element belongs in exactly 1 subarray. Both arrays are split into the same number of subarrays. Let the number of subarrays the first and second array are split into be $k$ (i.e. the first array is split into exactly $k$ subarrays and the second array is split into exactly $k$ subarrays). For all $1 \le i \le k$, the average of the $i$-th subarray on the left of the first array is less than or equal to the average of the $i$-th subarray on the left of the second array.

Count how many ways she can split both arrays into non-empty subarrays while satisfying the constraints modulo $10^9+7$. Two ways are considered different if the number of subarrays are different or if some element belongs in a different subarray.

입력

The first line contains $N$.

The next line contains $a_1,a_2,...,a_N$.

The next line contains $b_1,b_2,...,b_N$.

출력

Output the number of ways she can split both arrays into non-empty subarrays while satisfying the constraints modulo $10^9+7$.

예제 입력 1

2
1 2
2 2

예제 출력 1

2

예제 입력 2

3
1 3 2
2 2 2

예제 출력 2

3

예제 입력 3

5
2 5 1 3 2
2 1 5 2 2

예제 출력 3

1

예제 입력 4

7
3 5 2 3 4 4 1
5 3 5 3 3 4 1

예제 출력 4

140

점수

Inputs 5-6: $N \le 10$Inputs 7-9: $N \le 80$ Inputs 10-17: $N \le 300$ Inputs 18-20: $N \le 500$