Use FFT

题号：NC52777
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
Special Judge, 64bit IO Format: %lld

题目描述

Bobo computes the product $P(x) \cdot Q(x) = c_0 + c_1 x + \dots + c_{n + m} x^{n + m}$ for two polynomials $P(x) = a_0 + a_1 x + \dots + a_n x^n$ and $Q(x) = b_0 + b_1 x + \dots + b_m x^m$ .
Find $(c_{L} + c_{L + 1} + \dots + c_{R})$ modulo $(10^9+7)$ for given L and R.

输入描述:

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 .
The third line contains (m+1) integers .

输出描述:

For each test case, print an integer which denotes the reuslt.

示例1

输入

复制

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

输出

复制

21
18
5

备注:

* 
* 
* 
* Both the sum of n and the sum of m do not exceed .