Description

Given an integer array $s$ whose length is $n$ and an integer array $t$ whose length is $m$. Calculate

$$\sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^n\sum_{l=1}^m \max\{(s_i+t_j)-(s_k+t_l)+1,0\} $$

Input

The first line contains two integers $n,m$ ($1\le n,m\le 10^6$).

The second line contains $n$ integers $s_1,s_2,\ldots,s_n$ ($1\le s_i\le 10^7$).

The third line contains $m$ integers $t_1,t_2,\ldots,t_m$ ($1\le t_j\le 10^7$).

It's guaranteed that $\sum_{i=1}^n s_i\le 10^7$ and $\sum_{j=1}^m t_j\le 10^7$.

Output

Output one integer indicating the answer. Please output the answer modulo $10^9+7$.

Samples

3 3
1 1 3
1 2 3

106

Resources

The 22nd UESTC Programming Contest Preliminary