Bobo 计算两个多项式 $P(x) = a_0 + a_1 x + \dots + a_n x^n$ 和 $Q(x) = b_0 + b_1 x + \dots + b_m x^m$ 的乘积 $P(x) \cdot Q(x) = c_0 + c_1 x + \dots + c_{n + m} x^{n + m}$。 给定 $L$ 和 $R$，求 $(c_{L} + c_{L + 1} + \dots + c_{R})$ 对 $(10^9+7)$ 取模的结果。

输入格式

输入包含多组测试数据，以文件结束符（EOF）终止。

每组测试数据的第一行包含四个整数 $n, m, L, R$。

第二行包含 $(n+1)$ 个整数 $a_0, a_1, \dots, a_n$。

第三行包含 $(m+1)$ 个整数 $b_0, b_1, \dots, b_m$。

输出格式

对于每组测试数据，输出一个整数，表示计算结果。

样例

样例输入 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

样例输出 1

21
18
5

数据范围

• $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$
• $n$ 的总和与 $m$ 的总和均不超过 $10^6$。