Bobo computes the product P(x)⋅Q(x)=c0+c1x+⋯+cn+mxn+m for two polynomials P(x)=a0+a1x+⋯+anxn and Q(x)=b0+b1x+⋯+bmxm. Find (cL+cL+1+⋯+cR) modulo (109+7) for given L and R.
Input
The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains four integers n, m, L, R.
The second line contains (n+1) integers a0,a1,…,an.
The third line contains (m+1) integers b0,b1,…,bm.
Output
For each test case, print an integer which denotes the reuslt.
Sample Input
1 1 0 2 1 2 3 4 1 1 1 2 1 2 3 4 2 3 0 5 1 2 999999999 1 2 3 1000000000
Sample Output
21 18 5
Constraint
- 1≤n,m≤5×105
- 0≤L≤R≤n+m
- 0≤ai,bi≤109
- Both the sum of n and the sum of m do not exceed 106.