Description

Bobo computes the product P(x) ⋅ Q(x) = c₀ + c₁x + … + c_n + mx^n + m for two polynomials P(x) = a₀ + a₁x + … + a_nxⁿ and Q(x) = b₀ + b₁x + … + b_mx^m. Find (c_L + c_L + 1 + … + c_R) modulo (10⁹ + 7) for given L and R.

• 1 ≤ n, m ≤ 5 × 10⁵
• 0 ≤ L ≤ R ≤ n + m
• 0 ≤ a_i, b_i ≤ 10⁹
• Both the sum of n and the sum of m do not exceed 10⁶.

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 a₀, a₁, …, a_n.

The third line contains (m + 1) integers b₀, b₁, …, b_m.

Output

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

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