QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB
[0]

# 3749. Use FFT

Statistics

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

  • 1n,m5×105
  • 0LRn+m
  • 0ai,bi109
  • Both the sum of n and the sum of m do not exceed 106.