Поля
Поля
На двумерной плоскости расположены m линий, параллельных оси x, и n линий, параллельных оси y. Среди линий, параллельных оси x, i - я снизу представлена как y = yi
. Точно так же среди линий, параллельных оси y, i - я слева представлена как x = xi
.
Для каждого прямоугольника, образованного этими линиями, найдите его площадь и выведите общую площадь по модулю 109
+ 7.
То есть для каждой четверки (i, j, k, l) удовлетворяющей 1 ≤ i< j ≤ n и 1 ≤ k < l ≤ m, найти площадь прямоугольника, образованного линиями x = xi
, x = xj
, y = yk
и y = yl
, и выведите сумму этих площадей по модулю 109
+ 7.
Входные данные
Первая строка содержит два целых числа n и m (2 ≤ n, m ≤ 105
).
Вторая строка содержит n целых чисел -109
≤ x1
< x2
< ... < xn
≤ 109
.
Третья строка содержит m целых чисел -109
≤ y1
, y2
, ..., ym
≤ 109
.
Выходные данные
Выведите общую площадь прямоугольников по модулю 109
+ 7.
Пример
На следующем рисунке показан пример входных данных:
Общая сумма площадей девяти прямоугольников A, B, ..., I показанных на рисунке, равна 60.
3 3 1 3 4 1 3 6
60
6 5 -790013317 -192321079 95834122 418379342 586260100 802780784 -253230108 193944314 363756450 712662868 735867677
835067060