Smaller Averages

문제

Bessie has two arrays of length $NN$ ($1\le N\le 5001\; \backslash le\; N\; \backslash le\; 500$). The $ii$-th element of the first array is $a_{i}a\_i$ ($1\le a_i\le {10}^{6}1\; \backslash le\; a\_i\; \backslash le\; 10^6$) and the $ii$-th element of the second array is $b_{i}b\_i$ ($1\le b_i\le {10}^{6}1\; \backslash le\; b\_i\; \backslash le\; 10^6$).

Bessie wants to split both arrays into non-empty subarrays such that the following is true.

1. Every element belongs in exactly 1 subarray.
2. Both arrays are split into the same number of subarrays. Let the number of subarrays the first and second array are split into be $kk$ (i.e. the first array is split into exactly $kk$ subarrays and the second array is split into exactly $kk$ subarrays).
3. For all $1\le i\le k1\; \backslash le\; i\; \backslash le\; k$, the average of the $ii$-th subarray on the left of the first array is less than or equal to the average of the $ii$-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+710^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 $NN$.

The next line contains $a_1,a_2,\mathrm{.}\mathrm{.}\mathrm{.},a_{N}a\_1,a\_2,...,a\_N$.

The next line contains $b_1,b_2,\mathrm{.}\mathrm{.}\mathrm{.},b_{N}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+710^9+7$.

2
1 2
2 2

2

3
1 3 2
2 2 2

3

5
2 5 1 3 2
2 1 5 2 2

1

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

140