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: Time Limit Exceeded

Solution code:
a = list(map(int,input().split()))
x = list(map(int,input().split()))
y = list(map(int,input().split()))
xs = []
ys = []
for i in range(a[0]):
    for j in range(i):
        xs.append(x[i]-x[j])
for i in range(a[1]):
    for j in range(i):
        ys.append(y[i]-y[j])
ans = 0        
for i in xs:
    for j in ys:
        ans += i*j
        ans= ans%((10**9)+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
nm = input().split()
n = int(nm[0])
m = int(nm[1])
X = input().split()
Y = input().split()
S = 0
for i in range(n):
	for j in range(n - i):
		for k in range(m):
			for l in range(m - k):
				S += (int(X[i + j]) - int(X[i])) * (int(Y[k + l]) - int(Y[k]))
ans = S % 1000000007
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
    

fac = [-1] * (10**7+1)
inv = [-1] * (10**7+1)
finv = [-1] * (10**7+1)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

def main():
    n, m = LI()
    x = sorted(LI())
    y = sorted(LI())
    ans = 0
    for i in range(len(x)):
        k = i + 1
        ans += (k - 1 - n + k) * x[i]
    ysum = 0
    for j in range(len(y)):
        k = j + 1
        ysum += (k - 1 - m + k) * y[j]
    ans *= ysum
    ans %= mod
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline
in_n = lambda: int(input())
in_nn = lambda: map(int, input().split())
in_s = lambda: input().rstrip().decode('utf-8')
in_map = lambda: [s == ord('.') for s in input() if s != ord('\n')]

MOD = 10**9 + 7
INF = 8 * 10**18


def main():

    N, M = in_nn()
    X = list(in_nn())
    Y = list(in_nn())

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

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

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

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

    print(x_sum * y_sum % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

x=[]
y=[]

for i in range(len(xxx)-1):
    x.append(xxx[i+1]-xxx[i])

for i in range(len(yyy)-1):
    y.append(yyy[i+1]-yyy[i])

cnt=0
cnt2=0


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

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

print((cnt*cnt2)%mod)

Submission status: Accepted

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

xdl = []
ydl = []
for x2,x1 in zip(xl[1:],xl[:-1]):
    xdl.append(x2-x1)

for y2,y1 in zip(yl[1:],yl[:-1]):
    ydl.append(y2-y1)


MOD = 10**9+7
ys = 0
for i,d in enumerate(xdl):
    pattern = (i+1)*(n-1-i)
    ys += pattern*d
    ys%=MOD

# print(ys)
ans = 0

for i,d in enumerate(ydl):
    pattern = (i+1)*(m-1-i)
    ans += pattern*ys*d
    ans%=MOD

print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    n,m = LI()
    x = LI()
    y = LI()

    x.sort()
    y.sort()

    ysum = 0
    for j in range(1,m):
        ysum += j * (m-j) * (y[j]-y[j-1])

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

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

n, m = MAP()
x = LIST()
y = LIST()

def acc(A):
	acc = []
	tmp = 0
	for a in A:
		tmp += a
		tmp %= mod
		acc.append(tmp)
	return acc

def sum_combinations(A, k):
	A_acc = acc(A)
	A_sum = 0

	for i in range(k):
		tmp = (A_acc[-1] - A_acc[i]) %mod
		tmp = (tmp-A[i] * (k-1-i)%mod) %mod
		A_sum = (A_sum + tmp) %mod

	return A_sum

print(sum_combinations(x, n) * sum_combinations(y, m) %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

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

sy = 0

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

print((sx*sy)%mod)

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())

    def total(E):
        L = len(E)
        ret = 0
        for i, (frm, to) in enumerate(zip(E, E[1:]), start=1):
            ret = (ret + i * (L - i) * (to - frm)) % MOD
        return ret

    ans = total(X) * total(Y) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    n, m = read_ints()
    X = read_ints()
    Y = read_ints()
    areaX = [0]*n
    modulo = 10**9+7
    for i in range(1, len(X)):
        areaX[i] = (areaX[i-1]+i*(X[i]-X[i-1]))%modulo
    areaY = [0]*m
    for i in range(1, len(Y)):
        areaY[i] = (areaY[i-1]+i*(Y[i]-Y[i-1]))%modulo
    return (sum(areaX)*sum(areaY))%modulo


if __name__ == '__main__':
    print(solve())

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

xx = [x[i + 1] - x[i] for i in range(n - 1)]
yy = [y[i + 1] - y[i] for i in range(m - 1)]

print(sum(xx[i] * (i + 1) * (n - 1 - i) for i in range(n - 1)) *
      sum(yy[i] * (i + 1) * (m - 1 - i) for i in range(m - 1)) % MOD)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()
X = IL()
Y = IL()

nobeX = 0
for i in range(N-1):
  nobeX += (X[i+1]-X[i])*(i+1)*(N-1-i)
  nobeX %= MOD
nobeY = 0
for i in range(M-1):
  nobeY += (Y[i+1]-Y[i])*(i+1)*(M-1-i)
  nobeY %= MOD
print((nobeX*nobeY)%MOD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,M = MI()
X,Y = LI(),LI()
mod = 10**9+7

r = sum((i*(N-i)*(X[i]-X[i-1])) % mod for i in range(1,N))
r %= mod

ans = 0
for i in range(1,M):
    ans += r*i*(M-i)*(Y[i]-Y[i-1]) % mod
    ans %= mod

print(ans)

Submission status: Accepted

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

mod=10**9+7

xsum=list(accumulate(x))
ysum=list(accumulate(y))
xt=0
yt=0
for i in range(1,n):
    xt+=i*x[i]-xsum[i-1]
    xt%=mod

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

print(xt*yt%mod)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N,M = MI()
X = LI()
Y = LI()
mod = 10**9+7

r = sum((i*(N-i)*(X[i]-X[i-1])) % mod for i in range(1,N))
r %= mod

ans = 0
for i in range(1,M):
    ans += r*i*(M-i)*(Y[i]-Y[i-1]) % mod
    ans %= 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()))

mod = 10 ** 9 + 7

sx = 0
sy = 0
for i in range(n):
    sx = (sx + x[i] * i - x[i] * (n - 1 - i)) % mod
for i in range(m):
    sy = (sy + y[i] * i - y[i] * (m - 1 - i)) % mod
print(sx * sy % mod)

Submission status: Accepted

Solution code:
m, n = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
X.sort()
Y.sort()
mod = 10**9 + 7
ax = 0
ay = 0
for ix, (x, x_) in enumerate(zip(X, X[::-1])):
    if x >= x_:
        break
    ax += ((x_ - x) % mod) * (m - 2 * ix - 1) % mod
    ax %= mod
for iy, (y, y_) in enumerate(zip(Y, Y[::-1])):
    if y >= y_:
        break
    ay += ((y_ - y) % mod) * (n - 2 * iy - 1) % mod
    ay %= mod
print(ax * ay % mod)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
# x,yは既にソートされている
x = [0] + list(map(int, input().split()))
y = [0] + list(map(int, input().split()))

"""
図で考えるより、数式を眺めた方が見通しが良い

Σ_{1<=i<j<=n} Σ_{1<=k<l<=m} (x_j - x_i) (y_l - y_k)
（↓変数分離のような変形をする）
Σ_{1<=i<j<=n}(x_j - x_i) * Σ_{1<=k<l<=m}(y_l - y_k)

2つのΣは同じ形をしているので、左のΣの求め方を考えれば良い

n=5 で実験してみると、
x5-x4, x5-x3, x5-x2, x5-x1
x4-x3, x4-x2, x4-x1
x3-x2, x3-x1
x2-x1
+x_iは(i-1)個, -x_iは(n-i)個ある
i = 1,2,...,nについて計算すれば、O(n)で計算が可能
"""
tmp1 = 0
tmp2 = 0
for i in range(1, n + 1):
    tmp1 += (i - 1) * x[i] - (n - i) * x[i]
for j in range(1, m + 1):
    tmp2 += (j - 1) * y[j] - (m - j) * y[j]

mod = 10**9 + 7
ans = (tmp1 % mod) * (tmp2 % mod)
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

acmx=list(accumulate(x))
acmy=list(accumulate(y))
mod=10**9+7
sumx=0
for i in range(n-1):
    sumx+=acmx[n-1]-acmx[i]-(n-i-1)*x[i]
    sumx%=mod

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

print(sumx*sumy%mod)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
X = sorted([int(x) for x in input().split()])
Y = sorted([int(x) for x in input().split()])
mod = 1000000007

def diffSum(X): #Σ(X[j]-X[i]) 1<=i<j<=N
    l = len(X)
    Res = [(2*i-l+1)*X[i] for i in range(l)]
    return sum(Res)%mod

print(diffSum(X)*diffSum(Y)%mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
M = 10**9 + 7
def get_diffsum(X, M):
  left_sum = sum(X)
  left_count = len(X)
  ans = 0
  for x in X:
    left_sum -= x
    left_count -= 1
    ans += left_sum - left_count * x
    ans %= M
  return ans

print(get_diffsum(X, M) * get_diffsum(Y, M) % M)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    X = list(map(int, input().split()))
    Y = list(map(int, input().split()))

    XL = [X[i] - X[i - 1] for i in range(1, n)]
    YL = [Y[i] - Y[i - 1] for i in range(1, m)]

    cnt_X = [(i * (n - i)) % mod for i in range(1, n)]
    cnt_Y = [(i * (m - i)) % mod for i in range(1, m)]
    total_X = (sum([(XL[i] * cnt_X[i]) % mod for i in range(n - 1)])) % mod
    total_Y = (sum([(YL[i] * cnt_Y[i]) % mod for i in range(m - 1)])) % mod
    res = (total_X * total_Y) % mod
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

for n in range(N):
  a+=(2*n-N+1)*X[n]
  a%=mod

for m in range(M):
  b+=(2*m-M+1)*Y[m]
  b%=mod

print(a*b%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

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

print(main(n, x, mod) * main(m, y, mod) % mod)

Submission status: Accepted

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

Submission status: Accepted

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


def main():
    n, m = map(int, input().split())
    x = list(map(int, input().split()))
    y = list(map(int, input().split()))
    
    X = [x[i+1]-x[i] for i in range(n-1)]
    Y = [y[i+1]-y[i] for i in range(m-1)]
    
    mod = pow(10, 9)+7
    for i in range(n-1):
        X[i] = X[i]*(n-i-1)*(i+1)%mod
    
    sum_x = sum(X)%mod
    
    for i in range(m-1):
        Y[i] = Y[i]*(m-i-1)*(i+1)%mod
    
    sum_y = sum(Y)%mod
    
    
    ans = sum_x*sum_y%mod
    
    print(ans)
    
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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


def main():
    n, m = map(int, input().split())
    x = list(map(int, input().split()))
    y = list(map(int, input().split()))
    
    X = [x[i+1]-x[i] for i in range(n-1)]
    Y = [y[i+1]-y[i] for i in range(m-1)]
    
    mod = pow(10, 9)+7
    for i in range(n-1):
        X[i] = X[i]*(n-i-1)*(i+1)%mod
    
    sum_x = sum(X)%mod
    
    ans = 0
    for j in range(m-1):
        ans += sum_x*Y[j]*(m-j-1)*(j+1)%mod
        ans %= mod
    
    print(ans)
    
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import product,combinations
MOD = 10**9+7

def solve(X,Y):
    DX = [a-b for a,b in zip(X[1:],X)]
    DY = [a-b for a,b in zip(Y[1:],Y)]
    a = sum((i+1)*(len(DX)-i)*dx for i,dx in enumerate(DX))
    b = sum((i+1)*(len(DY)-i)*dy for i,dy in enumerate(DY))
    return (a*b)%MOD


def naive(X,Y):
    a = 0
    for (x1,x2),(y1,y2) in product(combinations(X,2), combinations(Y,2)):
        a += (x2-x1)*(y2-y1)
        a %= MOD
    return a

from random import randrange
from itertools import accumulate

def test():
    for _ in range(10000):
        X = list(accumulate([randrange(1,8) for _ in range(3)]))
        Y = list(accumulate([randrange(1,8) for _ in range(2)]))
        a1 = solve(X,Y)
        a2 = naive(X,Y)
        if a1 != a2:
            print(X,Y)
            print(a1)
            print(a2)
            return

if __name__ == '__main__':
    # test()
    N,M = map(int,input().split())
    X = tuple(map(int,input().split()))
    Y = tuple(map(int,input().split()))
    print(solve(X,Y))
    # print(naive(X,Y))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = [x for x in map(int, input().split())]
y = [y for y in map(int, input().split())]
sum_x = 0
sum_y = 0
ans = 0
for i in range(n):
    sum_x += (2*i - n + 1) * x[i] 
for j in range(m):
    sum_y += (2*j - m + 1) * y[j]
ans = sum_x * sum_y
print(ans%1000000007)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

def main():
    n, m = map(int, input().split())
    X = list(map(int, input().split()))
    Y = list(map(int, input().split()))
    """
    各長方形を１つ１つの矩形に分解することで、もともと線で区切られていた
    最小の長方形たちが個別に何回足されるかを見る。
    長方形が縦に(m-1)個、横に(n-1)個並んでいるとして、(i, j)の位置にある長方形は
        i * (m - i) * j * (n - j)
    回足される。
    これをシグマ計算するとx, y方向独立に解いてよいことがわかる。
    """
    x = 0
    for j in range(1, n):
        coeff = j * (n - j) % mod
        x += coeff * (X[j] - X[j - 1]) % mod
        x %= mod
    y = 0
    for i in range(1, m):
        coeff = i * (m - i) % mod
        y += coeff * (Y[i] - Y[i - 1]) % mod
        y %= mod
    print(x * y % mod)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
xs = list(map(int, input().split()))
ys = list(map(int, input().split()))
vx = 0
vy = 0
M  = 10**9+7
for i in range(n-1):
    vx += (xs[i+1]-xs[i]) * (i+1) * (n-i-1)
    vx %= M
for i in range(m-1):
    vy += (ys[i+1]-ys[i]) * (i+1) * (m-i-1)
    vy %= M
ans = (vx*vy)%M
print(ans%M)

Submission status: Accepted

Solution code:
x,y=map(int, input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
A,B=sorted(A)[::-1],sorted(B)[::-1]
mod=10**9+7
X,Y=0,0
for i in range(x):
  d=A[i]*(x-i)-A[i]*(i)-A[i]
  X+=d
  X%=mod
for i in range(y):
  d=B[i]*(y-i)-B[i]*(i)-B[i]
  Y+=d
  Y%=mod
print(X*Y%mod)

Submission status: Accepted

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

n, m = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
MOD = 10**9+7
xacc, yacc = [0], [0]

for i in range(n-1):
    xacc.append((xacc[-1]+x[i+1]-x[i])%MOD)

for i in range(m-1):
    yacc.append((yacc[-1]+y[i+1]-y[i])%MOD)

X, t = 0, 0

for i in range(1, n):
    X += i*xacc[i]-t
    X %= MOD
    t += xacc[i]

Y, t = 0, 0

for i in range(1, m):
    Y += i*yacc[i]-t
    Y %= MOD
    t += yacc[i]

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

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

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

ans = SX*SY
print(ans%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()))
xx=[x[i+1]-x[i] for i in range(n-1)]
yy=[y[i+1]-y[i] for i in range(m-1)]
xsum=sum(xx[i]*(i+1)*(n-1-i) for i in range(n-1))%mod
ysum=sum(yy[i]*(i+1)*(m-1-i) for i in range(m-1))%mod
print(xsum*ysum%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


n, m = map(int, input().split())
X = [int(i) for i in input().split()]
Y = [int(i) for i in input().split()]

Sx, Sy = 0, 0

for i in range(n-1):
    Sx += (X[i+1]-X[i])*(i+1)*(n-1-i)

for k in range(m-1):
    Sy += (Y[k+1]-Y[k])*(k+1)*(m-1-k)

print((Sx*Sy) % 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の辺もすべてのyの辺をかけて合計することから、
分配法則を適用して
ans = (xの取りうる辺の総和)x(yの取りうる辺の総和)
となる
したがって、各辺の総和を効率的に求められれば良い
一旦xに着目し、各点の組合せでできる辺の総和を求める。
ここで、x_iとx_i+1の区間は他の辺の部分としてカウントされる回数は
(i+1)*(n-i-1) 0-indexed
したがって、差数列に回数を畳みこんで辺の総和が求まる
yも同様に総和を求め、積を取れば良い
"""

x_diff = [x[i]-x[i-1] for i in range(1, n)]
y_diff = [y[i]-y[i-1] for i in range(1, m)]

x_sum = 0
for i, dx in enumerate(x_diff):
    x_sum = (x_sum + (dx * (i+1) * (n-i-1))%mod)%mod
y_sum = 0
for i, dy in enumerate(y_diff):
    y_sum = (y_sum + (dy * (i+1) * (m-i-1))%mod)%mod

print((x_sum*y_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()))
mod = pow(10, 9) + 7
a, b = [0] * (n - 1), [0] * (m - 1)
c, s = n - 1, 0
for i in range(n - 1):
    s += c
    a[i] = s
    c -= 2
c, s = m - 1, 0
for i in range(m - 1):
    s += c
    b[i] = s
    c -= 2
sumx, sumy = 0, 0
for i in range(n - 1):
    sumx += (a[i] * (x[i + 1] - x[i]))
    sumx %= mod
for i in range(m - 1):
    sumy += (b[i] * (y[i + 1] - y[i]))
    sumy %= mod
ans = sumx * sumy % mod
print(ans)

Submission status: Accepted

Solution code:
mod=1000000007
N,M=map(int,input().split())
s=0
k=0
L=list(map(int,input().split()))
R=list(map(int,input().split()))
for i in range(N):
  s+=L[i]*(2*i-N+1)
for j in range(M):
  k+=R[j]*(2*j-M+1)
print((k%mod*s%mod)%mod)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
aj=0
xsum=0
mod1,mod2=10**9+7,998244353
mod=mod1
for j in range(1,n):
    aj=(aj+j*(x[j]-x[j-1])%mod)%mod
    xsum=(xsum+aj)%mod
bj=0
ysum=0
for j in range(1,m):
    bj=(bj+j*(y[j]-y[j-1])%mod)%mod
    ysum=(ysum+bj)%mod

print(xsum*ysum%mod)

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

n,m = MI()
x,y = LI(),LI()
mod = 10**9+7

n,m = n-1,m-1
dx = [x[i+1]-x[i] for i in range(n)]
dy = [y[i+1]-y[i] for i in range(m)]

if n % 2 == 0:
    rx = [i*(n+1-i) for i in range(1,n//2+1)] + [i*(n+1-i) for i in range(n//2,0,-1)]
else:
    rx = [i*(n+1-i) for i in range(1,n//2+2)] + [i*(n+1-i) for i in range(n//2,0,-1)]
if m % 2 == 0:
    ry = [i*(m+1-i) for i in range(1,m//2+1)] + [i*(m+1-i) for i in range(m//2,0,-1)]
else:
    ry = [i*(m+1-i) for i in range(1,m//2+2)] + [i*(m+1-i) for i in range(m//2,0,-1)]

a = 0
for i,j in zip(dx,rx):
    a += i*j
    a %= mod
b = 0
for i,j in zip(dy,ry):
    b += i*j
    b %= mod

print((a*b) % mod)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, M = getNM()
X = getList()
Y = getList()

X.sort(reverse = True)
Y.sort(reverse = True)
XP, YP = 0, 0
for i in range(N):
  XP += (N - 1 - i * 2) * X[i]
  XP %= mod
for i in range(M):
  YP += (M - 1 - i * 2) * Y[i]
  YP %= mod

print((XP * YP) % mod)

Submission status: Accepted

Solution code:
import sys

def main():
    p=10**9+7
    def totsum(l,n):
        s=0
        t=0
        for i in range(n//2):
            t=t+l[-1-i]-l[i]
            s=(s+t) % p
        s=(2*s-(1-n&1)*t) % p
        return s
    n,m=map(int,input().split())
    x=list(map(int,sys.stdin.readline().strip().split()))
    y=list(map(int,sys.stdin.readline().strip().split()))
    
    print((totsum(x,n)*totsum(y,m))%p)
    
    # for j in range(2,m):
    #     ns=(s*(y[j]-y[j-1])) % p
    #     tot2=(tot2 + j*ns) % p
    #     tot1=(tot2+tot1) % p
    # print(tot1)

if __name__=='__main__':
    main()

Submission status: Accepted

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

#普通に考えるのであればnC2 * mC2

# 累積和使えばあるx_iを選んだときの横の長さの和(もう１本のx_iとの距離の合計)は分かる
mod = 10**9 + 7
# H = x[-1] - x[0]
# W = y[-1] - y[0]
# S = H*W % mod
# S *= (n-1)*(m-1)
# if n >= 4:
#     h = x[-2] - x[1]
#     S -= h*W * 2
# if m >= 4:
#     w = y[-2] - y[1]
#     S -= H*w * 2
H = 0
W = 0
for i in range(n//2):
    w = x[n-1-i] - x[i]
    if i == n//2 - 1:
        if n % 2 == 1:
            w *= 2
    else:
        w *= n-2*i-1
    W += w
    W %= mod
for j in range(m // 2):
    h = y[m-1-j] - y[j]
    if j == m//2 - 1:
        if m % 2 == 1:
            h *= 2
    else:
        h *= m-1-2*j
    H += h
    H %= mod
S = H*W

print(S % mod)

Submission status: Accepted

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

## 0,x1,x2,x3
## S = (x1 + x2 + x3 + (x2-x1) + (x3-x1) + (x3-x2)) * ...
##.  = (3*x3 + x2 - x1 - 3* 0)
##.  = ((3-0) + (2-1) + (1-2) + (0-3)
mod = int(1e9+7)
X.sort(reverse=True)
Y.sort(reverse=True)
XP,YP = 0,0
for i in range(N):
  XP += (N-1-i*2) * X[i] 
  XP %= mod
for i in range(M):
  YP += (M-1-i*2) * Y[i] 
  YP %= mod
  
print((XP * YP)%mod)

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

def f(V):
  vsum = 0
  for i in range(1, len(V)):
    vsum += (((V[i] - V[i - 1]) % DIV) * ((i * (len(V) - i)) % DIV)) % DIV
    vsum %= DIV
  return vsum
  
print((f(X) * f(Y)) % DIV)