Smaller Averages

시간 제한2초메모리 제한1024 MB

요약

길이 N인 두 배열을 같은 개수의 비어 있지 않은 부분 배열로 나누되 각 구간에서 첫 배열의 평균이 둘째 배열의 평균 이하가 되도록 하는 분할의 수를 10^9+7로 나눈 나머지로 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 누적 합, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

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$ .

예제4

예제 1
입력
```
2
1 2
2 2
```
예상 출력
```
2
```
예제 2
입력
```
3
1 3 2
2 2 2
```
예상 출력
```
3
```
예제 3
입력
```
5
2 5 1 3 2
2 1 5 2 2
```
예상 출력
```
1
```
예제 4
입력
```
7
3 5 2 3 4 4 1
5 3 5 3 3 4 1
```
예상 출력
```
140
```