Subarray Partitioning with Average Constraints

Bessie is given two arrays of length \(N\) (where \(1\le N\le 500\)). The first array contains elements \(a_1,a_2,\dots,a_N\) with \(1\le a_i\le 10^6\) and the second array contains elements \(b_1,b_2,\dots,b_N\) with \(1\le b_i\le 10^6\). She wishes to partition each array independently into one or more non‐empty contiguous subarrays such that:

1. Each element of the array belongs to exactly one subarray.
2. The two arrays are partitioned into the same number \(k\) of subarrays.
3. For every \(1\le i\le k\), if the \(i\)th subarray of the first array is \(a[l_i..r_i]\) and that of the second array is \(b[l'_i..r'_i]\), then their averages satisfy \[ \frac{a_{l_i}+a_{l_i+1}+\cdots+a_{r_i}}{r_i-l_i+1} \le \frac{b_{l'_i}+b_{l'_i+1}+\cdots+b_{r'_i}}{r'_i-l'_i+1}. \]

Two ways of partitioning are considered different if the number of subarrays \(k\) is different or if there exists an element that belongs to different subarrays. Compute the number of valid ways to partition the two arrays under these restrictions, and output the answer modulo \(10^9+7\).

Note: For a subarray defined by indices \(l\) to \(r\), its average is defined as \(\frac{\sum_{i=l}^{r}x_i}{r-l+1}\), where \(x_i\) represents the element in that subarray.

inputFormat

The input consists of three lines:

• The first line contains an integer \(N\) (the length of the arrays).
• The second line contains \(N\) space-separated integers: \(a_1,a_2,\dots,a_N\).
• The third line contains \(N\) space-separated integers: \(b_1,b_2,\dots,b_N\).

outputFormat

Output a single integer representing the number of valid ways to partition the arrays satisfying the conditions described, modulo \(10^9+7\).

sample

1
5
7

1