## USACO 2024 US Open Contest, Gold

## Problem 3. Smaller Averages

Contest has ended.

**Log in to allow submissions in analysis mode**

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:

2The 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:

3The 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:

1The 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