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: Wrong Answer

Solution code:
n,m=map(int,input().split())
X=list(map(int,input().split()))
Y=list(map(int,input().split()))

dif_x=[(X[i+1]-X[i])*(i+1)*(n-i-1) for i in range(n-1)]
dif_y=[(Y[i+1]-Y[i])*(i+1)*(m-i-1) for i in range(m-1)]    

print(sum(dif_x)*sum(dif_y))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
a=0
for i in range(n):
    a+=i*p[i]-(n-i-1)*p[i]
b=0
for i in range(m):
    b+=i*q[i]-(m-i-1)*q[i]
print(a*b)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
a=0
for i in range(n):
    a+=i*p[i]-(n-i-1)*p[i]
b=0
for i in range(m):
    b+=i*q[i]-(n-i-1)*q[i]
print(a*b)

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7

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

sx = 0
sy = 0

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

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

print((sx*sy) % mod)

Submission status: Wrong Answer

Solution code:
nx,ny=map(int,input().split())
n_all=(nx-1)*(ny-1)
x=list(map(int,input().split()))
y=list(map(int,input().split()))
s=abs(x[-1]-x[0])*abs(y[-1]-y[0])
print((n_all*s)%(10**9+7))

Submission status: Wrong Answer

Solution code:
nx,ny=map(int,input().split())
n_all=(nx-1)*(ny-1)
x=list(map(int,input().split()))
y=list(map(int,input().split()))
print(x)
print(y)
s=abs(x[-1]-x[0])*abs(y[-1]-y[0])
print((n_all*s)%(10**9+7))

Submission status: Wrong Answer

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

p = 10 ** 9 + 7

ans = 0
xc = n // 2
yc = m // 2
n -= 1
m -= 1
h = Y[-1] - Y[0]
w = X[-1] - X[0]

if n % 2 == 0 and m % 2 == 0:
    ans = n * m * h * w

elif n % 2 == 1 and m % 2 == 1:
    xd = X[xc] - X[xc-1]
    yd = Y[yc] - Y[yc-1]
    ans = n * (m+1) * xd * (h - yd) + (n+1) * m * yd * (w - xd) + (n+1) * (m+1) * yd * xd + n * m * (w - xd) * (h - yd)

elif n % 2 == 1:
    d = X[xc] - X[xc-1]
    ans = (n * (m+1) * d + (w - d)) * h

elif n % 2 == 1:
    d = Y[yc] - Y[yc-1]
    ans = ((n+1) * m * d + (h - d)) * w

print(ans % p)

Submission status: Wrong Answer

Solution code:
mod=10**9+7
n,m=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
xl=0
yl=0
for i in range(1,n):
  l=i-1
  r=i+1
  while l>=0:
    xl=(xl+x[i]-x[l])%mod
    l-=1
  while r<n:
    xl=(xl+x[r]-x[i])%mod
    r+=1
for i in range(1,m):
  l=i-1
  u=i+1
  while l>=0:
    yl=(yl+y[i]-y[l])%mod
    l-=1
  while u<m:
    yl=(yl+y[u]-y[i])%mod
    u+=1
print(xl*yl%mod)

Submission status: Wrong Answer

Solution code:
import itertools


def main():
    n, m = map(int, input().split())

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

    x_len = 0
    y_len = 0

    for i in range(n):
        x_len += (2 * i - n + 1) * x[i] % (10 ** 9 + 7)
        print(x_len)

    for j in range(m):
        y_len += (2 * j - m + 1) * y[j] % (10 ** 9 + 7)
        print(y_len)

    print(x_len * y_len % (10 ** 9 + 7))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def get_sum_line(count, val_list):
    len_list = len(val_list)
    sum_line = 0
    for i in range(len_list):
        sum_line += val_list[i] * (i - (len_list - 1 - i))
    return sum_line

n, m = list(map(int, input().split()))
x_list = list(map(int, input().split()))
y_list = list(map(int, input().split()))

sum_x_line = get_sum_line(n, x_list)
sum_y_line = get_sum_line(m, y_list)

ans = int(sum_x_line * sum_y_line % (1e9 + 7))

print(ans)

Submission status: Wrong Answer

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

edge_x = []
for i in range(len(X) - 1):
    edge_x.append(abs(X[i + 1] - X[i]))

edge_y = []
for i in range(len(Y) - 1):
    edge_y.append(abs(Y[i + 1] - Y[i]))

ret = 0
for x in edge_x:
    for y in edge_y:
        ret += x * y * len(edge_x) * len(edge_y)
        ret = ret % (10 ** 9 + 7)

print(ret)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import math

n, m = map(int, input().split())
l_x = list(map(int, input().split()))
l_y = list(map(int, input().split()))

x_dif = l_x[n - 1] - l_x[0]
y_dif = l_y[m - 1] - l_y[0]

ans = (x_dif * y_dif * (2 ** (n + m - 4))) % (10 ** 9 + 7)

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from random import *

def readln():
    _res = list(map(int,str(input()).split(' ')))
    return _res

def calc(x):
    n = len(x)
    res = 0
    for i in range(0,n):
        res = res + x[i] * i
        res = res - x[i] * (n - i - 1)
    return res

n,m = readln()
x = readln()
y = readln()
print(calc(x) * calc(y))

Submission status: Wrong Answer

Solution code:
INF=10**9+7
L=[int(i)-1 for i in input().split()]
x=[int(i)   for i in input().split()]
y=[int(i)   for i in input().split()]
x.sort()
y.sort()

X=[x[i+1]-x[i] for i in range(L[0])]
Y=[y[i+1]-y[i] for i in range(L[1])]

usingX=[0 for i in range(L[0])]
usingY=[0 for i in range(L[1])]

if L[0]%2==0:
	for i in range(L[0]):
		temp=min(i,L[0]-i-1)
		temp+=1
		usingX[i]+=int(temp*(temp+1)/2)
		#print(usingX)
		usingX[i]+=temp*int(L[0]/2-temp)
		#print(usingX)
		usingX[i]*=2
		#print()
else:
	for i in range(L[0]):
		temp=min(i,L[0]-i-1)
		temp+=1
		usingX[i]+=int(temp*(temp+1)/2)
		usingX[i]+=temp*int((L[0]-1)/2-temp)
		usingX[i]*=2
		
		usingX[i]+=temp
	#temp=int((L[0]-1)/2)
	#usingX[temp]-=(temp+1)*2


if L[1]%2==0:
	for i in range(L[1]):
		temp=min(i,L[1]-i-1)
		temp+=1
		usingY[i]+=int(temp*(temp+1)/2)
		#print(usingY)
		usingY[i]+=temp*int(L[1]/2-temp)
		#print(usingY)
		usingY[i]*=2
		#print()
else:
	for i in range(L[1]):
		temp=min(i,L[1]-i-1)
		temp+=1
		usingY[i]+=int(temp*(temp+1)/2)
		usingY[i]+=temp*int((L[1]-1)/2-temp)
		usingY[i]*=2
		
		usingY[i]+=temp
	#temp=int((L[1]-1)/2)
	#usingY[temp]-=(temp+1)*2	

print(usingX)
print(usingY)
for i in range(L[0]):
	X[i]*=usingX[i]
for j in range(L[1]):
	Y[j]*=usingY[j]
ans=sum(X)*sum(Y)
print(ans%INF)

Submission status: Wrong Answer

Solution code:
#coding:utf-8

[n, m] = map(int, raw_input().split(" "))
#n, m = 3,3
xs = map(int, raw_input().split(" "))
ys = map(int, raw_input().split(" "))
#xs = [1,3,4]
#ys = [1,3,6]

x_min, x_max = xs[0], xs[-1]
y_min, y_max = ys[0], ys[-1]
x_len = len(xs) - 2
y_len = len(ys) - 2

size = (x_max - x_min) * (y_max - y_min)
combs = pow(2, x_len + y_len)

result = size * combs
result = result % (pow(10, 9) + 7)
print result

Submission status: Wrong Answer

Solution code:
INF=10**9+7
L=[int(i) for i in input().split()]
x=[int(i) for i in input().split()]
y=[int(i) for i in input().split()]
x.sort()
y.sort()
"""
X=[x[i+1]-x[i] for i in range(L[0]-1)]
Y=[y[i+1]-y[i] for i in range(L[1]-1)]

allx=0
for i in range(L[0]-1):
	for j in range(L[0]-1-i):
		allx+=X[j]
		
ansX=x[-1]-x[0]
ansX*=L[0]-1
ansY=y[-1]-y[0]
ansY*=L[1]-1
"""
x=(x[-1]-x[0])%INF
ans=x
ans%=INF
ans*=L[0]-1
ans%=INF

y=(y[-1]-y[0])%INF
ans*=y
ans%=INF
ans*=L[0]-1
ans%=INF


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
x = list(map(int,input().split()))
y = list(map(int,input().split()))
from itertools import combinations
ans = 0
mod = 10**9 +7
for t1 in combinations(x,2):
    for t2 in combinations(y,2):
        ans += abs(t1[0]-t1[1])*abs(t2[0]-t2[1])
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def getlist():
	return list(map(int, input().split()))

const = 10 ** 9 + 7

#初期化
n, m = getlist()
x = getlist()
y = getlist()

#計算
ans = 0
for i in range(n - 1):
	for j in range(m - 1):
		ans += (x[i + 1] - x[i]) * (y[j + 1] - y[j]) * (i + 1) * (n - 1 - i) * (j + 1) * (m - 1 - j)
		ans %= const

print(ans)

Submission status: Time Limit Exceeded

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 = 0
for i in range(1, N):
    for j in range(1, M):
        sum += (X[i] - X[i-1]) * (Y[j] - Y[j-1]) * i * (N - i) * j * (M - j)
        sum %= MOD

print(sum)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

n,m = map(int,input().split())

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

sum = 0
for i in range(n-1):
  for j in range(m-1):
    h = x[i+1] - x[i]
    v = y[j+1] - y[j]
    sum = (sum + h*v*(i+1)*(n-i-1)*(j+1)*(m-j-1)) % mod


print(sum % mod)

Submission status: Time Limit Exceeded

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

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

sum = 0
for i in range(n-1):
  for j in range(m-1):
    h = x[i+1] - x[i]
    v = y[j+1] - y[j]
    sum += h*v*(i+1)*(n-i-1)*(j+1)*(m-j-1)

mod = 10 ** 9 + 7
print(sum % mod)

Submission status: Time Limit Exceeded

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

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

sum = 0
for i in range(n-1):
  for j in range(i+1,n):
    for k in range(m-1):
      for l in range(k+1,m):
        h = x[j] - x[i]
        v = y[l] - y[k]
        
        sum += h*v

mod = 10 ** 9 + 7
print(sum % mod)

Submission status: Time Limit Exceeded

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_sum = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        x_sum += x[j] - x[i]
        x_sum %= MOD

y_sum = 0
for i in range(m - 1):
    for j in range(i + 1, m):
        y_sum += y[j] - y[i]
        y_sum %= MOD

print( (x_sum * y_sum) % MOD )

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))

N, M = inpl()

X = inpl()
Y = inpl()

Sx = 0
Sy = 0

for i in range(N-1):
    for j in range(i+1, N):
        Sx += X[j] - X[i]

for i in range(M-1):
    for j in range(i+1, M):
        Sy += Y[j] - Y[i]

print((Sx*Sy)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from operator import mul

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

dXs = [0] * (n - 1)
for i in range(n - 1):
    dXs[i] = xs[i + 1] - xs[i]

dYs = [0] * (m - 1)
for j in range(m - 1):
    dYs[j] = ys[j + 1] - ys[j]

fXs = [(i + 1) * (n - i - 1) for i in range(n)]
fYs = [(j + 1) * (m - j - 1) for j in range(m)]

MOD = 10 ** 9 + 7
ans = 0
for dY, fY in zip(dYs, fYs):
    ans += dY * fY * sum(map(mul, dXs, fXs))
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

nm = raw_input()
nm = nm.split()
n,m = map(int,nm)

xl = raw_input()
xl = xl.split()
xl = map(int,xl)

yl = raw_input()
yl = yl.split()
yl = map(int,yl)

xl.sort()
yl.sort()

mod = 10**9+7
ans = 0

for i in range(n/2):
    for j in range(m/2):
        #print i,", ", j
        size = (xl[-(i+1)]-xl[i]) * (yl[-(j+1)]-yl[j])
        num = ((n-1)-i*2) * ((m-1)-j*2)
        ans += size * num % mod
    ans = ans % mod

print ans

Submission status: Time Limit Exceeded

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

nm = raw_input()
nm = nm.split()
n,m = map(int,nm)

xl = raw_input()
xl = xl.split()
xl = map(int,xl)

yl = raw_input()
yl = yl.split()
yl = map(int,yl)

xl.sort()
yl.sort()

ans = 0

mod = 10**9+7

xa = []
for i in range(n-1):
    xa.append(xl[i+1]-xl[i])

ya = []
for j in range(m-1):
    ya.append(yl[j+1]-yl[j])

for i in range(n-1):
    for j in range(m-1):
        num = ((n-1)+(i*(n-2-i)))*((m-1)+(j*(m-2-j)))
        size = xa[i] * ya[j]
        ans += size * num % mod
    ans = ans % mod

print ans

Submission status: Time Limit Exceeded

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

nm = raw_input()
nm = nm.split()
n,m = map(int,nm)

xl = raw_input()
xl = xl.split()
xl = map(int,xl)

yl = raw_input()
yl = yl.split()
yl = map(int,yl)

xl.sort()
yl.sort()

ans = 0

mod = 10**9+7

for i in range(n-1):
    for j in range(m-1):
        num = ((n-1)+(i*(n-2-i)))*((m-1)+(j*(m-2-j)))
        ans += (xl[i+1]-xl[i])*(yl[j+1]-yl[j])*num % mod
    ans = ans % mod

print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools


def main():
    n, m = map(int, input().split())

    X = list(map(int, input().split()))
    Y = list(map(int, input().split()))

    s = 0
    for x in itertools.combinations(X, 2):
        for y in itertools.combinations(Y, 2):
            x_len = x[0] - x[1]
            y_len = y[0] - y[1]
            s += x_len * y_len

    print(s % (10 ** 9 + 7))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    n, m = map(int, input().split())

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

    s = 0
    # x_len = 0
    # y_len = 0

    for e1 in itertools.combinations(x, 2):
        for e2 in itertools.combinations(y, 2):
            x_len = e1[0] - e1[1]
            y_len = e2[0] - e2[1]
            s += x_len * y_len

    print(s % (10 ** 9 + 7))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(x) for x in input().strip().split()]

x_list = input().strip().split()
y_list = input().strip().split()

area = 0
for x1 in x_list:
    for x2 in x_list[x_list.index(x1):]:
        for y1 in y_list:
            for y2 in y_list[y_list.index(y1):]:
                area += (int(x2)-int(x1)) * (int(y2)-int(y1))

print(area % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(x) for x in input().strip().split()]

x_list = [int(x) for x in input().strip().split()]
y_list = [int(y) for y in input().strip().split()]

area = 0
for x1 in x_list:
    for x2 in x_list[x_list.index(x1):]:
        for y1 in y_list:
            for y2 in y_list[y_list.index(y1):]:
                area += (x2-x1) * (y2-y1)

print(area % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
kr=list(map(int,input().split()))
n,m=kr[0],kr[1]
x=list(map(int,input().split()))
y=list(map(int,input().split()))
gs=0
lx,ly=len(x),len(y)
for i in range(lx//2):
    for j in range(ly//2):
        s=0
        s+=(x[i+1]-x[i])*(y[j+1]-y[j])%1000000007
        if lx%2==1 or i!=(lx//2)-1:
            s+=(x[lx-i-1]-x[lx-i-2])*(y[j+1]-y[j])%1000000007
        if ly%2==1 or j!=(ly//2)-1:
            s+=(x[i+1]-x[i])*(y[ly-j-1]-y[ly-j-2])%1000000007
        if lx%2==1 or i!=(lx//2)-1:
            if ly%2==1 or j!=(ly//2)-1:
                s+=(x[lx-i-1]-x[lx-i-2])*(y[ly-j-1]-y[ly-j-2])%1000000007
        s*=(i+1)*(lx-i-1)*(j+1)*(ly-j-1)%1000000007
        gs=(gs+s)%1000000007
print(gs)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

input_line = sys.stdin.readline()
nm = input_line.split()
n = nm[0]
m = nm[1]

div = int(1e9 + 7)

input_line = sys.stdin.readline()
xn = [int(v) for v in input_line.split()]

input_line = sys.stdin.readline()
ym = [int(v) for v in input_line.split()]

i = 0
j = 0
S = 0
for i in range(len(xn) - 1):
	sx = xn[i]
	for j in range(len(ym) - 1):
		sy = ym[j]

		for ii in range(i + 1, len(xn)):
			for jj in range(j + 1, len(ym)):
				S += abs((sx - xn[ii]) * (sy - ym[jj]))

S %= div

print(int(S))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import numpy as np
input()
x=list(map(int,input().split()))
y=list(map(int,input().split()))
dx=np.array([abs(i-j) for i,j in combinations(x,2)])
dy=np.array([abs(i-j) for i,j in combinations(y,2)])
result=dx.reshape(-1,1)*dy
ans=0
mod=10**9+7
for r in result:
    for ri in r:
        if ans-mod>0:ans-=mod
        ans+=ri%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF=10**9+7
L=[int(i) for i in input().split()]
x=[int(i) for i in input().split()]
y=[int(i) for i in input().split()]
x.sort()
y.sort()

X=[x[i+1]-x[i] for i in range(L[0]-1)]
Y=[y[i+1]-y[i] for i in range(L[1]-1)]

usingX=[0 for i in range(L[0])]
usingY=[0 for i in range(L[1])]

ansx=0
for i in range(1,L[0]+1):#width
	for j in range(L[0]-i):#starting
		for k in range(i):#block
			ansx+=X[j+k]
			#print(i,j,k)
ansy=0
for i in range(1,L[1]+1):
	for j in range(L[1]-i):
		for k in range(i):
			ansy+=Y[j+k]
print(ansx*ansy%INF)

#print(ansx)
#print(ansy)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

def solve2(Xs, Ys):
    cell_num = (len(Xs) - 1) * (len(Ys) - 1)
    if len(Xs) < 2 or len(Ys) < 2:
        return 0

    area = (Xs[-1] - Xs[0]) * (Ys[-1] - Ys[0])
    ans = area * cell_num
    ans %= MOD
    return ans

def solve(Xs, Ys):
    if len(Xs) <= 3 and len(Ys) <= 3:
        return solve2(Xs, Ys)

    ans = solve2(Xs, Ys)
    for i in range(1, len(Xs) // 2):
        ans += solve2(Xs[i:-i], Ys)
        ans %= MOD
    for i in range(1, len(Ys) // 2):
        ans += solve2(Xs, Ys[i:-i])
        ans %= MOD
    ans += solve(Xs[1:-1], Ys[1:-1])
    ans %= MOD
    return ans

N, M = map(int, input().split())
Xs = list(map(int, input().split()))
Ys = list(map(int, input().split()))
print(solve(Xs, Ys))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
input()
x=list(map(int,input().split()))
y=list(map(int,input().split()))
dx=[abs(x[i]-x[j]) for i in range(len(x)) for j in range(i+1,len(x))]
dy=[abs(y[i]-y[j]) for i in range(len(y)) for j in range(i+1,len(y))]
result=[i*j for i in dx for j in dy]
print(sum(result)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
n, m = [ int(i) for i in input().split()]
x = [int(i) for i in input().split()]
y = [int(i) for i in input().split()]
xl = []
yl = []
for i in range(n):
    for j in range(i):
        xl.append(x[i] - x[j])
for i in range(m):
    for j in range(i):
        yl.append(y[i] - y[j])

ans = 0
for xx in xl:
    for yy in yl:
        ans += xx * yy
        ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import combinations
MOD = 10**9+7
n, m = [ int(i) for i in input().split()]
x = [ int(i) for i in input().split()]
y = [ int(i) for i in input().split()]

ans = 0
for xl in combinations(x, 2):
    for yl in combinations(y, 2):
        ans += abs(xl[1] - xl[0]) * abs(yl[1] - yl[0])
        ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
input()
x=list(map(int,input().split()))
y=list(map(int,input().split()))
result=[]
for x1,x2 in combinations(x,2):
    for y1,y2 in combinations(y,2):
        result.append((x2-x1)*(y2-y1))
print(sum(result)%(10**9+7))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7
ans = 0

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

print ans % MOD

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N, M = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = [int(i) for i in input().split()]
y = [int(i) for i in input().split()]
mod = 10**9+7
a = 0
for i, j, k in zip(range(n), x[:-1], x[1:]):
    a += abs(j-k) * (i+1)*(n-1-i)
b = 0
for i, j, k in zip(range(m), y[:-1], y[1:]):
    b += abs(j-k) * (i+1)*(m-1-i)
a %= mod
b %= mod
print(a*b % mod)

Submission status: Accepted

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

sx=0
sy=0
mod=10**9+7

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

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

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

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

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

ans *= uni_x
ans %= mod

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

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

MOD = 10**9+7

dx = [i-j for i,j in zip(x[1:],x)]
rx = 0
for i in range(n-1):
    rx += dx[i]*(i+1)%MOD*(n-i-1)%MOD

dy = [i-j for i,j in zip(y[1:],y)]
ry = 0
for i in range(m-1):
    ry += dy[i]*(i+1)%MOD*(m-i-1)%MOD

print(rx*ry%MOD)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
*xlines, = map(int, input().split())
*ylines, = map(int, input().split())

modulo = 10 ** 9 + 7
vs = 0
for i in range(len(xlines) - 1):
    vs += (xlines[i + 1] - xlines[i]) * (1 + i) * (len(xlines) - i - 1)
    vs %= modulo

s = 0
for j in range(len(ylines) - 1):
    s += vs * (ylines[j + 1] - ylines[j]) * (1 + j) * (len(ylines) - j - 1)
    s %= modulo
print(s)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# input
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
m, n = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
x.sort()
y.sort()
fx = [0]
fy = [0]
mod = 10 ** 9 + 7
x_sum = 0
y_sum = 0
for i in range(m - 2, -1, -1):
    fx.append((fx[-1] + (x[i + 1] - x[i]) * (m - 1 - i)) % mod)
    x_sum += fx[-1]
    x_sum %= mod
for i in range(n - 2, -1, -1):
    fy.append((fy[-1] + (y[i + 1] - y[i]) * (n - 1 - i)) % mod)
    y_sum += fy[-1]

    y_sum %= mod
print(x_sum * y_sum % mod)

Submission status: Accepted

Solution code:
n,m=[int(_) for _ in input().split()]

x=[int(_) for _ in input().split()]
y=[int(_) for _ in input().split()]

sumx=0
sumy=0
for i in range(n):
  sumx+=(2*i-n+1)*x[i]
  sumx%=1000000007
  #print(sumx)
for i in range(m):
  sumy+=(2*i-m+1)*y[i]
  sumy%=1000000007
  #print(sumy)
print((sumx*sumy)%1000000007)

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

dif_x=[(X[i+1]-X[i])*(i+1)*(n-i-1) for i in range(n-1)]
dif_y=[(Y[i+1]-Y[i])*(i+1)*(m-i-1) for i in range(m-1)]    

print(sum(dif_x)*sum(dif_y)%MOD)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)

def sort(a):
	a.sort()

def rev(a):
	a.reverse()

def sd():
	return int(input())

def _sd():
	return map(int,input().split())

def sa():
	return list(map(int,input().split()))

def ss():
	return input()

def sf():
	return float(input())
 
def main():
	n,m=_sd()
	X=sa()
	Y=sa()
	sum_x=int(0)
	sum_y=int(0)
	mod=int((1e+9)+7)
	for i in range(1,n+1):
		sum_x+=(i+i-n-1)*X[i-1]
		sum_x%=mod
	for i in range(1,m+1):
		sum_y+=(i+i-m-1)*Y[i-1]
		sum_y%=mod
	print((sum_x*sum_y)%mod)
main()

Submission status: Accepted

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

MOD = 10 ** 9 + 7

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

def eq6_1(x):
    n = len(x)
    res = 0
    for j in range(n):
        res += j * x[j]
        res %= MOD
    for i in range(n):
        res -= (n - i - 1) * x[i]
        res %= MOD
    return res

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

MOD = 1000000007

w = sum(
  (x[i+1] - x[i]) * (i + 1) * (n - 1 - i) % MOD 
  for i
  in range(n-1)
) % MOD 

h = sum(
  (y[i+1] - y[i]) * (i + 1) * (m - 1 - i) % MOD 
  for i
  in range(m-1)
) % MOD 

print(w*h % 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()))
ansx=0
cum=x[0]
for i in range(1,n):
    ansx+=(i*x[i]-cum+mod)%mod
    ansx%=mod
    cum+=x[i]
ansy=0
cum=y[0]
for i in range(1,m):
    ansy+=(i*y[i]-cum+mod)%mod
    ansy%=mod
    cum+=y[i]
#print(ansx,ansy)
print((ansx*ansy)%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.sort()
y.sort()

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

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

print((X*Y)%mod)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

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

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10 ** 9 + 7
def main():
    n, m = MI()
    xx = LI()
    yy = LI()
    byi = mint(0)
    byj = mint(0)
    for j in range(m - 1):
        byj += (j + 1) * (m - j - 1) * (yy[j + 1] - yy[j])
    for i in range(n - 1):
        byi += (xx[i + 1] - xx[i]) * (i + 1) * (n - i - 1)
    print(byi * byj)

main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
n, m = map(int, input().split())
print((sum(map(lambda x, y: (2 * y - n + 1) * int(x), input().split(), range(n))) * sum(map(lambda x, y: (2 * y - m + 1) * int(x), input().split(), range(m))) % mod + mod) % mod)