Bessie has two arrays of length N(1≤N≤500). The i-th element of the first array is ai (1≤ai≤106) and the i-th element of the second array is bi (1≤bi≤106).
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≤i≤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 109+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 al,a2,...,aN.
The next line contains b1,b2,...,bN.
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 109+7.
SAMPLE INPUT:
2
1 2
2 2
SAMPLE OUTPUT:
2
The two valid ways are:
1.Split the first array into [1],[2] and the second array into [2],[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:
1.Split the first array into [1,3],[2] and the second array into [2,2],[2].
2.Split the first array into [1,3],[2] and the second array into [2],[2,2].
3.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≤10
Inputs 7-9: N≤80
Inputs 10-17: N≤300
Inputs 18-20: N≤500
Problem credits: Alex Liang
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
