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$.

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_0, a_1, \dots, a_n$.

The third line contains $(m+1)$ integers $b_0, b_1, \dots, b_m$.

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 \leq n, m \leq 5\times 10^5$
• $0 \leq L \leq R \leq n + m$
• $0 \leq a_i, b_i \leq 10^9$
• Both the sum of $n$ and the sum of $m$ do not exceed $10^6$.