gold_Smaller_Averages — USACO US_Open_Contest
Task type: batch | Time limit: 2 s | Memory limit: 256 MB | Difficulty: 20
Algorithms: sorting, prefix sum, two pointers, dynamic programming

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.
INPUT FORMAT (input arrives from the terminal / stdin):
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 FORMAT (print output to the terminal / stdout):
Output the number of ways she can split both arrays into non-empty subarrays
while satisfying the constraints modulo $10^9+7$.
SAMPLE INPUT:
2
1 2
2 2
SAMPLE OUTPUT:
2
The two valid ways are:
Split the first array into $[1],[2]$ and the second array into
$[2],[2]$.
Split the first array into $[1,2]$ and the second array into
$[2,2]$.
SAMPLE INPUT:
3
1 3 2
2 2 2
SAMPLE OUTPUT:
3
The three valid ways are:
Split the first array into $[1,3],[2]$ and the second array into
$[2,2],[2]$.
Split the first array into $[1,3],[2]$ and the second
array into $[2],[2,2]$.
Split the first array into $[1,3,2]$ and the
second array into $[2,2,2]$.
SAMPLE INPUT:
5
2 5 1 3 2
2 1 5 2 2
SAMPLE OUTPUT:
1
The only valid way is to split the first array into $[2],[5,1,3],[2]$ and the 
second array into $[2],[1,5],[2,2]$.
SAMPLE INPUT:
7
3 5 2 3 4 4 1
5 3 5 3 3 4 1
SAMPLE OUTPUT:
140
SCORING:
Inputs 5-6: $N \le 10$
Inputs 7-9: $N \le 80$
Inputs
10-17: $N \le 300$
Inputs 18-20: $N \le 500$
Problem credits: Alex Liang

Starter code: