2051: [USACO 2024 US Open Contest Gold] Problem 3. Smaller Averages

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.

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 $k$ (i.e. the first array is split into exactly $k$ subarrays and the second array is split into exactly $k$ subarrays).
3. 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 next line contains $a_1,a_2,...,a_N$.

The next line contains $b_1,b_2,...,b_N$.

2
1 2
2 2

2