Problem:


Score : 500 points

Problem Statement

On a two-dimensional plane, there are m lines drawn parallel to the x axis, and n lines drawn parallel to the y axis.
Among the lines parallel to the x axis, the i-th from the bottom is represented by y = y_i.
Similarly, among the lines parallel to the y axis, the i-th from the left is represented by x = x_i.

For every rectangle that is formed by these lines, find its area, and print the total area modulo 10^9+7.

That is, for every quadruple (i,j,k,l) satisfying 1\leq i < j\leq n and 1\leq k < l\leq m, find the area of the rectangle formed by the lines x=x_i, x=x_j, y=y_k and y=y_l, and print the sum of these areas modulo 10^9+7.

Constraints

2 \leq n,m \leq 10^5

-10^9 \leq x_1 < ... < x_n \leq 10^9

-10^9 \leq y_1 < ... < y_m \leq 10^9

x_i and y_i are integers.

Input

Input is given from Standard Input in the following format:

n m
x_1 x_2 ... x_n
y_1 y_2 ... y_m

Output

Print the total area of the rectangles, modulo 10^9+7.

Sample Input 1

3 3
1 3 4
1 3 6

Sample Output 1

60

The following figure illustrates this input:

The total area of the nine rectangles A, B, ..., I shown in the following figure, is 60.

Sample Input 2

6 5
-790013317 -192321079 95834122 418379342 586260100 802780784
-253230108 193944314 363756450 712662868 735867677

Sample Output 2

835067060



Sample input:
3 3
1 3 4
1 3 6


Sample output:
60

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
X = list(map(int,readline().split()))
Y = list(map(int,readline().split()))
DIV = 10 ** 9 + 7

# カウントする回数分X,Y軸ともに辺の長さを伸ばしていって巨大な長方形を作るイメージ
# X軸の、長さLの辺を3回数える場合、L * 2分X軸の辺の長さを伸ばす。
# X軸Y軸ともに各辺を数える回数が分かれば、巨大な長方形の面積はその積で求められる
# 
# X軸について、i番目の辺は、((i - 1) + 1) * (N - i)回数える
# 例：4番目の辺の場合
# ...X.. 
# Xより左から4通り（0も含むため） * Xより右から3通り(0も含むため)
# この回数分、辺の長さを掛けることを全ての辺に対して行った総和がX軸の辺の総量
# Y軸についても同じものを求めて、掛け合わせたものが答え

xsum = 0
for i in range(1, len(X)):
  # i番目の辺は、長さX[i] - X[i - 1]
  edge = X[i] - X[i - 1]
  # i番目の辺は((i - 1) + 1) * (N - i)回数える
  times = i * (N - i)
  xsum += ((edge % DIV) * (times % DIV)) % DIV
  xsum %= DIV

ysum = 0
for i in range(1, len(Y)):
  # i番目の辺は、長さY[i] - Y[i - 1]
  edge = Y[i] - Y[i - 1]
  # i番目の辺は((i - 1) + 1) * (M - i)回数える
  times = i * (M - i)
  ysum += ((edge % DIV) * (times % DIV)) % DIV
  ysum %= DIV

print((xsum * ysum) % DIV)

Submission status: Accepted

Solution code:
MOD=10**9+7
n,m=map(int,input().split())
xs=list(map(int,input().split()))
ys=list(map(int,input().split()))
x=0
for i in range(n):
  x+=(2*(i+1)-n-1)*xs[i]
  x%=MOD

y=0
for j in range(m):
  y+=(2*(j+1)-m-1)*ys[j]
  y%=MOD

print(x*y%MOD)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

mod = 10**9+7

sidex, sidey = 0,0

for i in range(1,n):
  sidex += (x[i]-x[i-1])*i*(n-i)%mod

for i in range(1,m):
  sidey += (y[i]-y[i-1])*i*(m-i)%mod

print (sidex*sidey%mod)

Submission status: Accepted

Solution code:
mod=10**9+7
n,m=map(int,input().split())
X=list(map(int,input().split()))
Y=list(map(int,input().split()))
p=0
q=0
for i in range(n-1):
    p=(p+(X[i+1]-X[i])*(i+1)%mod*(n-i-1))%mod
for i in range(m-1):
    q=(q+(Y[i+1]-Y[i])*(i+1)%mod*(m-i-1))%mod
print(p*q%mod)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
MOD=10**9+7
X=list(map(int,input().split()))
Y=list(map(int,input().split()))

Xsum=0
for i in range(1,N+1):
    Xsum+=X[i-1]*i-(N-i+1)*X[i-1]
    Xsum%=MOD

Ysum=0
for i in range(1,M+1):
    Ysum+=Y[i-1]*i-(M-i+1)*(Y[i-1])
    Ysum%=MOD

print(Xsum*Ysum%MOD)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
MOD=1000000007
x=list(map(int,input().split()))
y=list(map(int,input().split()))
sx=0
sy=0
for i in range(1,n):
  sx += (x[i]-x[i-1]) * i * (n-i)
  sx %= MOD
for i in range(1,m):
  sy += (y[i]-y[i-1]) * i * (m-i)
  sy %= MOD
print(sx*sy%MOD)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
mod = 10**9+7
Xs = list(mapint())
Ys = list(mapint())

xsum = 0
for i in range(N):
    x = Xs[i]
    xsum += (i*x-(N-i-1)*x)
    xsum %= mod
ysum = 0
for i in range(M):
    y = Ys[i]
    ysum += (i*y-(M-i-1)*y)
    ysum %= mod

print(xsum*ysum%mod)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
mod = int(1e9) + 7
S = 0
for i in range(n):
  S += (2*i+1-n)*x[i]
  S %= mod
T = 0
for j in range(m):
  T += (2*j+1-m)*y[j]
  T %= mod
print(S*T%mod)

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
MOD = int(1e9) + 7

xs = 0
for i in range(N):
    xs += i * X[i] % MOD - (N - i - 1) * X[i] % MOD + 2 * MOD
    xs %= MOD

ys = 0
for i in range(M):
    ys += i * Y[i] % MOD - (M - i - 1) * Y[i] % MOD + 2 * MOD
    ys %= MOD

print(xs * ys % MOD)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
M,a,b=10**9+7,0,0
for i in range(n):a+=(2*i-n+1)*x[i];a%=M
for i in range(m):b+=(2*i-m+1)*y[i];b%=M
print(a*b%M)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = map(int, readline().split())
    x = list(map(int, readline().split()))
    y = list(map(int, readline().split()))

    s = 0

    for i in range(1, m):
        s += i * (m - i) * (y[i] - y[i - 1])
        s %= MOD

    ans = 0

    for i in range(1, n):
        t = s * (x[i] - x[i - 1])
        t %= MOD
        t *= i * (n - i)
        t %= MOD
        ans += t
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10**9+7
n, m = map(int, input().split())
X = list(map(int ,input().split()))
Y = list(map(int ,input().split()))
X.sort()
Y.sort()
xx, yy = 0, 0
for i in range(n):
    xx += X[i]*i
    xx -= X[i]*(n-i-1)
for i in range(m):
    yy += Y[i]*i
    yy -= Y[i]*(m-i-1)
print(xx*yy%MOD)

Submission status: Accepted

Solution code:
MOD = 10**9+7
n, m = map(int, input().split())
X = list(map(int ,input().split()))
Y = list(map(int ,input().split()))
X.sort()
Y.sort()
mx, my = X[n-1], Y[m-1]
SX, SY = [0], [0]
for i in range(n):
    SX.append(mx-X[i])
for i in range(n):
    SX[i+1] += SX[i]
for i in range(m):
    SY.append(my-Y[i])
for i in range(m):
    SY[i+1] += SY[i]
xx = 0
for i in range(n):
    diff = mx-X[i]
    num = n-(i+1)
    tot = diff*num
    tot -= SX[n]-SX[i+1]
    xx += tot
yy = 0
for i in range(m):
    diff = my-Y[i]
    num = m-(i+1)
    tot = diff*num
    tot -= SY[m]-SY[i+1]
    yy += tot
print(xx*yy%MOD)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
mod=10**9+7

X=0
for i in range(N):
    X+=((i)*x[i]-(N-i-1)*x[i])
    X%=mod
Y=0
for i in range(M):
    Y+=((i)*y[i]-(M-i-1)*y[i])
    Y%=mod
print(X*Y%mod)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
mod = 10**9+7
sum_x = 0
sum_y = 0
for i in range(n):
    sum_x += i*x[i]-(n-i-1)*x[i]
for i in range(m):
    sum_y += i*y[i]-(m-i-1)*y[i]
print(sum_x*sum_y%mod)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
sumx,sumy=0,0
mod=10**9+7
for i in range(n):
    sumx+=i*x[i]-(n-i-1)*x[i]
sumx%=mod
for i in range(m):
    sumy+=i*y[i]-(m-i-1)*y[i]
sumy%=mod
print(sumx*sumy%mod)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
X=list(map(int,input().split()))
Y=list(map(int,input().split()))
mod=10**9+7

ans1=0
for k in range(1,n+1):
    ans1+=(2*k-1-n)*X[k-1]
    ans1%=mod
ans2=0
for k in range(1,m+1):
    ans2+=(2*k-1-m)*Y[k-1]
    ans2%=mod
print(ans1*ans2%mod)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
import sys
input = sys.stdin.readline
from functools import reduce
from itertools import starmap
n,m = map(int,input().split())
x = list(map(int,input().split()))
y = list(map(int,input().split()))

mulmod = lambda x,y : (x*y) % MOD
summod = lambda x,y : (x+y) % MOD
coefx = range(-(n-1),n+1,2)
xds = reduce(summod, starmap(mulmod, zip(x,coefx)))
coefy = range(-(m-1),m+1,2)
yds = reduce(summod, starmap(mulmod, zip(y,coefy)))

print((xds*yds) % MOD)

Submission status: Accepted

Solution code:
import numpy as np


def main():
    mod = 10 ** 9 + 7
    n, m = map(int, input().split())
    X = np.array(list(map(int, input().split())), dtype=np.int64)
    Y = np.array(list(map(int, input().split())), dtype=np.int64)

    dxs = X[1:] - X[:-1]
    left = np.arange(1, n)
    right = np.arange(n-1, 0, -1)
    x_pattern = left * right % mod
    x_sum = (dxs * x_pattern).sum() % mod

    dys = Y[1:] - Y[:-1]
    up = np.arange(1, m)
    down = np.arange(m-1, 0, -1)
    y_pattern = up * down % mod
    y_sum = (dys * y_pattern).sum() % mod

    print(x_sum * y_sum % mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    x = list(map(int,ipt().split()))
    y = list(map(int,ipt().split()))
    mod = 10**9+7

    #nCrをmodで割った余りを求める。Nに最大値を入れて使用。
    N = 10**5
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル
    def cmb(n,r,mod):
        if r<0 or r>n :
            return 0
        r = min(r,n-r)
        return g1[n]*g2[r]*g2[n-r]%mod
    for i in range(2,N+1):
        g1.append((g1[-1]*i)%mod)
        inverse.append((-inverse[mod % i]*(mod//i))%mod)
        g2.append((g2[-1]*inverse[-1])%mod)

    sx = 0
    px = x[0]
    for i,xi in enumerate(x[1:n:]):
        sx = (sx+((xi-px)%mod*(i+1)%mod*(n-i-1))%mod)%mod
        px = xi
    sy = 0
    py = y[0]
    for i,yi in enumerate(y[1:m:]):
        sy = (sy+((yi-py)%mod*(i+1)%mod*(m-i-1))%mod)%mod
        py = yi
    print(sx*sy%mod)


    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 10**9+7

def sum_interval_1d(N,X):
  # O(N)
  X_ = [X[i+1]-X[i] for i in range(N-1)]
  coef = list(range(1,N))[::-1]
  ret = (X_[0]*coef[0])%mod
  for i in range(1,N-1):
    coef[i] = (coef[i]+coef[i-1]-i)%mod
    ret = (ret + ((X_[i]*coef[i]) % mod)) % mod
  # print(X_, coef, ret)
  return ret

def solve():
  N,M = map(int, input().split())
  X = list(map(int, input().split()))
  Y = list(map(int, input().split()))
  x_sum = sum_interval_1d(N,X)
  y_sum = sum_interval_1d(M,Y)
  # print(x_sum,y_sum)
  ret = (x_sum*y_sum) % mod
  print(ret)
  
solve()

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
X = list(map(int,input().split()))
Y = list(map(int,input().split()))
DX = [X[i+1] - X[i] for i in range(n-1)]
DY = [Y[i+1] - Y[i] for i in range(m-1)]
mod = 10 ** 9 + 7

SUM_X = 0
SUM_Y = 0

for i in range(n-1):
    SUM_X += (i+1) * (n-1-i) * DX[i]
    SUM_X %= mod

for i in range(m-1):
    SUM_Y += (i+1) * (m-1-i) * DY[i]
    SUM_Y %= mod

ans = (SUM_X * SUM_Y) % mod

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
# ブロックの数は(m-1)*(n-1)
mod=pow(10,9)+7
ypoint=0
for i in range(m-1):
  ypoint+=(y[i+1]-y[i])*(m-i-1)*(i+1)
  ypoint%=mod
ans=0
for i in range(n-1):
  ans+=ypoint*(x[i+1]-x[i])*(n-i-1)*(i+1)
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
x = inl()
y = inl()
ax = 0
k = -n+1
for i in range(n):
    ax = (ax+k*x[i])%R
    k += 2
ay = 0
k = -m+1
for i in range(m):
    ay = (ay+k*y[i])%R
    k += 2
print((ax*ay)%R)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
*x, = map(int, input().split())
*y, = map(int, input().split())

acx = [0]*(n)
acy = [0]*(m)
acx2 = [0]*(n)
acy2 = [0]*(m)
MOD = 10**9+7

for i in range(1, n):
    acx2[i] = acx2[i-1]+i*(x[i]-x[i-1])
    acx2[i] %= MOD
for i in range(1, m):
    acy2[i] = acy2[i-1]+i*(y[i]-y[i-1])
    acy2[i] %= MOD

for i in range(1, n):
    acx[i] = (acx[i-1]+acx2[i])%MOD
for i in range(1, m):
    acy[i] = (acy[i-1]+acy2[i])%MOD

print(acx[-1]*acy[-1]%MOD)

Submission status: Accepted

Solution code:
from itertools import accumulate

n, m = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
mod = 10 ** 9 + 7
# X.sort()
# Y.sort()
AX = list(accumulate([0] + X))
AY = list(accumulate([0] + Y))
xsum = 0
for i in range(1, n):
    xsum += (AX[n] - AX[i]) - (n - i) * X[i - 1]
    xsum %= mod
ysum = 0
for i in range(1, m):
    ysum += (AY[m] - AY[i]) - (m - i) * Y[i - 1]
    ysum %= mod
ans = xsum * ysum
print(ans % mod)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()

MOD = 10 ** 9 + 7
N, M = inm()
X = inl()
Y = inl()
assert len(X) == N
assert len(Y) == M


def solve():
    xsum = [0] * N
    xsum[N - 1] = (X[N - 1] - X[N - 2]) % MOD
    for k in range(2, N):
        xsum[N - k] = xsum[N - k + 1] + k * (X[N - k] - X[N - k - 1])
        xsum[N - k] %= MOD

    ysum = [0] * M
    ysum[M - 1] = (Y[M - 1] - Y[M - 2]) % MOD
    for k in range(2, M + 1):
        ysum[M - k] = ysum[M - k + 1] + k * (Y[M - k] - Y[M - k - 1])
        ysum[M - k] %= MOD

    return sum(xsum[1:]) % MOD * (sum(ysum[1:]) % MOD) % MOD


print(solve())

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = sorted(list(map(int, input().split())))
y = sorted(list(map(int, input().split())))
tx = 0
ty = 0
sx = 0
sy = 0
for i in range(n):
  tx += i * x[i] - sx
  sx += x[i]
for i in range(m):
  ty += i * y[i] - sy
  sy += y[i]
print(tx * ty % 1000000007)

Submission status: Accepted

Solution code:
def main():
    MOD = 10**9 + 7
    N, M = list(map(int, input().split(' ')))
    X = list(map(int, input().split(' ')))
    Y = list(map(int, input().split(' ')))
    X.sort()
    Y.sort()
    heights = [Y[i + 1] - Y[i] for i in range(M - 1)]
    widths = [X[j + 1] - X[j] for j in range(N - 1)]
    # first row
    row_areas = [0 for _ in range(M - 1)]
    first_row_area, norm_first_row_area = 0, 0
    for j, w in enumerate(widths):
        first_row_area += (1 + 0) * (M - 0 - 1) * (j + 1) * (N - j - 1) * w * heights[0]
        first_row_area %= MOD
        norm_first_row_area += (j + 1) * (N - j - 1) * w
        norm_first_row_area %= MOD
    row_areas[0] = first_row_area
    # rest rows
    for i in range(1, M - 1):
        area = (i + 1) * (M - i - 1) * norm_first_row_area * heights[i]
        area %= MOD
        row_areas[i] = area
    # answer
    ans = 0
    for a in row_areas:
        ans += a
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N,M = map(int,input().split())
    X = list(map(int,input().split()))
    Y = list(map(int,input().split()))

    height = sum((Y[i + 1] - Y[i])*(i + 1)*(M - i - 1)%MOD for i in range(M - 1))%MOD
    ans = sum(height*(X[i + 1] - X[i])*(i + 1)*(N - i - 1)%MOD for i in range(N - 1))%MOD
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m = mi()
    X = lmi()
    Y = lmi()

    tmp = 0
    for j in range(m - 1):
        tmp = (tmp + (j + 1) * (m - j - 1) * (Y[j+1] - Y[j])) % mod
    
    ans = 0
    for i in range(n - 1):
        ans = (ans + (i + 1) * (n - i - 1) * (X[i+1] - X[i]) * tmp) % mod
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,M=map(int,input().split())
x=tuple(map(int,input().split()))
y=tuple(map(int,input().split()))
ans=1
tmp=0
for i in range(N):
    tmp+=x[i]*(i-(N-1-i))
    tmp%=MOD
ans*=tmp
tmp=0
for i in range(M):
    tmp+=y[i]*(i-(M-1-i))
    tmp%=MOD
ans*=tmp
ans%=MOD
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7

n, m = map(int, input().split())
xs = list(map(int, input().split()))
ys = list(map(int, input().split()))

weight_n = np.array([(i + 1) * (n - i - 1) % MOD for i in range(n - 1)]).astype(np.int64)
weight_m = np.array([(i + 1) * (m - i - 1) % MOD for i in range(m - 1)]).astype(np.int64)

dxs = np.array([xs[i+1] - xs[i] for i in range(n-1)]).astype(np.int64)
dys = np.array([ys[i+1] - ys[i] for i in range(m-1)]).astype(np.int64)

t_x = np.sum(weight_n * dxs % MOD) % MOD
t_y = np.sum(weight_m * dys % MOD) % MOD

print(t_x * t_y % MOD)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline().strip()

def calc(x,n):
    ans = 0
    for i,a in enumerate(x):
        ans += (2*i-n+1)*a
    return ans

n,m = map(int,input().split())
x = tuple(map(int,input().split()))
y = tuple(map(int,input().split()))

print(calc(x,n)*calc(y,m)%(int(1e9+7)))

Submission status: Accepted

Solution code:
def calc(x):
    ans = 0
    n = len(x)
    for i,a in enumerate(x):
        ans += i*a - (n-1-i)*a
    return ans


n,m = map(int,input().split())
x = tuple(map(int,input().split()))
y = tuple(map(int,input().split()))

print(calc(x)*calc(y)%(int(1e9+7)))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
MOD = 10**9 + 7
x = list(map(int, input().split()))
y = list(map(int, input().split()))

cumsum_x = [0] * N
cumsum_y = [0] * M
cumsum_x[0] = x[0]
cumsum_y[0] = y[0]
for i, xi in enumerate(x[1:], 1):
  cumsum_x[i] = (cumsum_x[i-1] + xi) % MOD

for i, yi in enumerate(y[1:], 1):
  cumsum_y[i] = (cumsum_y[i-1] + yi) % MOD

X = Y = 0
for i, xi in enumerate(x):
  X += (cumsum_x[-1] - cumsum_x[i] - (N - i - 1)*xi) % MOD
  X %= MOD

for i, yi in enumerate(y):
  Y += (cumsum_y[-1] - cumsum_y[i] - (M - i - 1)*yi) % MOD
  Y %= MOD

print(X*Y % MOD)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
n, m = n-1, m-1
x = list(map(int, input().split()))
y = list(map(int, input().split()))
mod = 10 ** 9 + 7
x.sort()
y.sort()

h, w = 0, 0
for i in range(n):
    h += (i + 1) * (n - i) * (x[i+1] - x[i])
    h %= mod

for j in range(m):
    w += (j + 1) * (m - j) * (y[j+1] - y[j])
    w %= mod

print(h * w % mod)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
xl = list(map(int, input().split())) 
yl = list(map(int, input().split())) 

xl = list(map(lambda x: x-xl[0],xl))
yl = list(map(lambda x: x-yl[0],yl))

xi=0
yi=0
mod = 10**9+7
xsum = sum(xl)
ysum = sum(yl)
for i in range(n):
    xi += (xsum - xl[i]*(n-i)) % mod
    xsum -= xl[i] 
    
for j in range(m):
    yi += (ysum - yl[j]*(m-j)) % mod
    ysum -= yl[j]

print(xi*yi % mod)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
MOD = 10 ** 9 + 7
# 縦軸の和、横軸の和を求めて、掛け合わせる。

# listから、和を求める


def calc(lis):
    num = len(lis)
    sum = 0
    for i in range(num):
        #sum += x[i] * (num - i - 1) - x[i] * (i)
        sum += lis[i] * i - (lis[i] * (num - i - 1))

    return sum
    '''
          lisSum = 0
          before = 0
          for i, val in enumerate(lis):
              lisSum += val
              if (i != 0):
                  temp = before + val
                  lisSum = temp
              before = val

          return int(lisSum)

      '''


xSum = calc(x)
ySum = calc(y)

ans = (xSum * ySum) % MOD
print(ans)


'''
def calc(list):

sum = 0
for i in range(n):
  temp = n - i
  for j in range(i+1, n):
    sum += list[i] - list[j]

二重ループにせずとも、
for i in range(n):
  sum += x[i]*(n-i-1) - x[1]*(i)

でOK
'''

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
mod = 10**9+7

x = sorted(list(map(int,input().split())))
y = sorted(list(map(int,input().split())))

X = 0
for i in range(n-1):
    X += (i+1)*(n-i-1)*(x[i+1]-x[i])%mod
    X %= mod

Y = 0
for i in range(m-1):
    Y += (i+1)*(m-i-1)*(y[i+1]-y[i])%mod
    Y %= mod

print(X*Y%mod)

Submission status: Accepted

Solution code:
MOD=10**9+7
n,m=map(int,input().split())
xlist=list(map(int,input().split()))
ylist=list(map(int,input().split()))

x0,y0=xlist[0],ylist[0]
for i in range(n):
  xlist[i]-=x0
for i in range(m):
  ylist[i]-=y0
#print(xlist)
#print(ylist)

xsum=0
for i in range(1,n):
  xsum+=xlist[i]*i
  xsum-=xlist[i]*(n-i-1)
  xsum%=MOD

ysum=0
for i in range(1,m):
  ysum+=ylist[i]*i
  ysum-=ylist[i]*(m-i-1)
  ysum%=MOD
  
print((xsum*ysum)%MOD)

Submission status: Accepted

Solution code:
MOD = 10**9+7

n,m = map(int,input().split())
x = list(map(int,input().split()))
y = list(map(int,input().split()))

x_dif = [b-a for a,b in zip(x,x[1:])]
y_dif = [b-a for a,b in zip(y,y[1:])]

def cumd(dif,line):
    d_sum = 0
    for i,d in enumerate(dif,1):
        d_sum += d * i * (line-i)%MOD
        d_sum %= MOD
    return d_sum

dx_sum = cumd(x_dif,n)
dy_sum = cumd(y_dif,m)

    
print(dx_sum * dy_sum % MOD)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

area_x = 0
for k in range(n):
    area_x += k * x[k] - (n - k-1) * x[k]

area_y = 0
for l in range(m):
    area_y += l * y[l] - (m - l-1) * y[l]

print((area_x * area_y) % (10**9 + 7))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))

mod = 10 ** 9 + 7
vx = sum((2 * (k + 1) - N - 1) * X[k] % mod for k in range(N)) % mod
vy = sum((2 * (k + 1) - M - 1) * Y[k] % mod for k in range(M)) % mod
print(vx * vy % mod)

Submission status: Accepted

Solution code:
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
n,m=map(int,input().split())
h=list(map(int,input().split()))
w=list(map(int,input().split()))
tate=0
yoko=0
p=10**9+7
for i in range(n-1):
    weight=((i+1)*(n-1-i))%p
    tate=(tate+weight*((h[i+1]-h[i])%p))%p
for i in range(m-1):
    weight=((i+1)*(m-1-i))%p
    yoko=(yoko+weight*((w[i+1]-w[i])%p))%p
print((tate*yoko)%p)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
mod = 10**9+7

def count(li):
    l = 1-len(li)
    cnt = 0
    for ind, i in enumerate(li):
        cnt += i*(l+2*ind)
    return cnt%mod

print((count(x)*count(y))%mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
# INF = float("inf")


def f(l):
    ret = 0
    for k in range(len(l)):
        ret += (2 * (k + 1) - len(l) - 1) * l[k]
    return ret % MOD


def main():
    n, m = map(int, input().split())
    x = list(map(int, input().split()))
    y = list(map(int, input().split()))
    ans = f(x) * f(y) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    MOD = 10 ** 9 + 7

    N, M = map(int, input().split())
    *x, = map(int, input().split())
    *y, = map(int, input().split())

    sx = 0
    for i, x_ in enumerate(x, 1):
        sx = (sx + x_ * ((i - 1) - (N - i))) % MOD

    sy = 0
    for i, y_ in enumerate(y, 1):
        sy = (sy + y_ * ((i - 1) - (M - i))) % MOD

    ans = sx * sy % MOD

    print(ans)


if __name__ == '__main__':
    main()

# ある矩形の面積は
# (x1-x0)(y1-y0)
# x,yの各要素はx1,x0,y1,y0として何回出現するか?
# 1-indexedで、i番目の要素が
# x1として数えられるのは,
# 相方のx0の候補数 = 1-indexedのx0のインデックス = i-1
# x0として数えられるのは、
# 相方のx1の候補数 = 1-indexedのN-x0のインデックス = N-i

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc058/tasks/arc071_b
# 定式化してみると、独立に計算できる部分と、
# 前処理で累積和を求めておけばループ内でO(1)に減る部分と、
# 愚直に計算する部分に減る

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


class ModInt:
    def __init__(self, x, MOD=10 ** 9 + 7):
        '''
        pypyじゃないと地獄みたいな遅さなので注意
        '''
        self.mod = MOD
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x, self.mod)
        else:
            return ModInt(self.x + other, self.mod)

    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x, self.mod)
        else:
            return ModInt(self.x - other, self.mod)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x, self.mod)
        else:
            return ModInt(self.x * other, self.mod)

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, self.mod - 2, self.mod), self.mod)
        else:
            return ModInt(self.x * pow(other, self.mod - 2, self.mod), self.mod)

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, self.mod), self.mod)
        else:
            return ModInt(pow(self.x, other, self.mod), self.mod)

    __radd__ = __add__

    def __rsub__(self, other):  # 演算の順序が逆
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x, self.mod)
        else:
            return ModInt(other - self.x, self.mod)

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x * pow(self.x, self.mod - 2, self.mod), self.mod)
        else:
            return ModInt(other * pow(self.x, self.mod - 2, self.mod), self.mod)

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, self.mod), self.mod)
        else:
            return ModInt(pow(other, self.x, self.mod), self.mod)


def read_ints():
    return list(map(int, read().split()))


from itertools import accumulate

n, m = read_ints()
X = read_ints()
Y = read_ints()
MOD = 10 ** 9 + 7


def mul_term(X: list, n):
    S = list(accumulate(reversed(X)))
    S.reverse()
    ret = ModInt(0)
    for i in range(n - 1):
        ret += S[i + 1] - (n - i - 1) * X[i]
    return ret


# print(mul_term(X, n), mul_term(Y, m))
print(mul_term(X, n) * mul_term(Y, m))