Smaller Averages

Time limit2sMemory limit1024 MB

Summary

Count the ways to split two length-N arrays into the same number of contiguous parts, where each a-part's average is at most its paired b-part's average, mod 1e9+7.

Level: Medium7 of 10
Topics: Dynamic programming, Prefix sum
Solved: No attempts yet

Problem

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 so that the following holds.

Every element belongs to exactly one subarray.
Both arrays are split into the same number of subarrays. Let this number be $k$ , so the first array and the second array are each split into exactly $k$ subarrays.
For every $1 \le i \le k$ , the average of the $i$ -th subarray from the left in the first array is less than or equal to the average of the $i$ -th subarray from the left in the second array.

Count the ways to split both arrays under these constraints, modulo $10^9+7$ . Two ways differ if the number of subarrays differs or if some element belongs to a different subarray.

Input

The first line contains $N$ . The next line contains $a_1, a_2, \ldots, a_N$ . The next line contains $b_1, b_2, \ldots, b_N$ .

Output

Output the number of ways to split both arrays under these constraints, modulo $10^9+7$ .

Examples4

Example 1
Input
```
2
1 2
2 2
```
Expected output
```
2
```
Example 2
Input
```
3
1 3 2
2 2 2
```
Expected output
```
3
```
Example 3
Input
```
5
2 5 1 3 2
2 1 5 2 2
```
Expected output
```
1
```
Example 4
Input
```
7
3 5 2 3 4 4 1
5 3 5 3 3 4 1
```
Expected output
```
140
```