Problem:


Score : 300 points

Problem Statement

Given are N integers A_1,\ldots,A_N.

Find the sum of A_i \times A_j over all pairs (i,j) such that 1\leq i < j \leq N, modulo (10^9+7).

Constraints

2 \leq N \leq 2\times 10^5

0 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

Print \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} A_i A_j, modulo (10^9+7).

Sample Input 1

3
1 2 3

Sample Output 1

11

We have 1 \times 2 + 1 \times 3 + 2 \times 3 = 11.

Sample Input 2

4
141421356 17320508 22360679 244949

Sample Output 2

437235829



Sample input:
3
1 2 3


Sample output:
11

Submission status: Accepted

Solution code:
N = int(input())
A = input().split()

sum = 0
SUM = 0
for i in range(N-1, 0, -1):
    sum += int(A[i])
    SUM += int(A[i-1])*sum
ans = SUM%1000000007
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
m = 1000000007
ans = 0

b = [0]
for i in range(1,n+1):
  b.append((a[i-1] + b[i-1]) % m)
#print(a,b)
           
for i in range(n):
	p = b[n] - b[i+1]
	p *= a[i]
	p = p % m
	ans += p
	ans = ans % m
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A = input().split()

B = [0]
for i in range(N):
    B.append(B[i] + int(A[i]))

sum = 0
for i in range(N):
    sum += int(A[i]) * (B[N] - B[i+1])

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))
    p = 10**9 + 7
    ans = 0
    sumA = sum(A)

    for i, Ai in enumerate(A[:-1]):
        sumA -= Ai
        ans += Ai * sumA % p

    print(ans % p)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans=0
x=0
for i in range(n):
  ans += a[i] * x
  x +=a[i]
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
n=int(input())
vec=list(map(int,input().split()))
mod=10**9+7
wa=[i for i in vec]
for i in range(n-1):
  wa[i+1]+=wa[i]
ans=0
for i in range(n):
  ans += vec[i]*((wa[n-1]-wa[i])%mod)%mod
  ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
d=sum(a)**2
e=0
for i in range(0,len(a)):
    e=e+(a[i]*a[i])
print(((d-e)//2)%1000000007)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

mod = 10**9 + 7
S = sum(A)%mod
ans = 0

for x in A:
    S -= x
    S %= mod
    ans += S * x
    ans %= mod

ans %= mod
print(ans)

Submission status: Accepted

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

cur = sum(A)
ans = 0
for ai in A:
    cur -= ai
    ans += ((cur % mod) * ai) % mod
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

P = 10**9 + 7

ans = 0
tmp = 0
for num in A:
    tmp += num
    tmp %= P
for num in A:
    ans += (num*tmp)%P
    ans -= pow(num, 2, P)
    ans %= P

ans = ans * pow(2, P-2, P)
ans %= P
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a = list(map(int,input().split()))
def p(val):
    print(val)
 
sho = 10**9 +7
a1 = sum(a)**2
b1 = list(map(lambda y:y**2,a))
b2=sum(b1)
result = ((a1-b2)//2)% sho
p(result)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))

ans = 0
MOD = 10**9+7
total = sum(A)

for i in range(N-1):
    tmp = A[i]
    total -= tmp
    ans += (tmp * total) % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

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

sq = 0
for i in range(len(A)):
    sq += A[i] ** 2

print((((sum(A)) ** 2 - sq) // 2) % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
M = 10**9+7

N, A = int(input()), list(map(int, input().split()))

sum_A = list()

sum_val = 0

for idx in range(len(A)-1, -1, -1):
    sum_val += A[idx]
    sum_A.append(sum_val)

sum_A.reverse()

ret = 0

for idx in range(0, len(A)):
    ret += A[idx]*(sum_A[idx] - A[idx])
    ret %= M

print('{}'.format(ret))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque
from functools import *
from fractions import Fraction as f
from copy import *
from bisect import *	
from heapq import *
#from math import *
from itertools import permutations ,product
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
def inc(d,c):
	d[c]=d[c]+1 if c in d else 1
def bo(i):
	return ord(i)-ord('A')	
def li():
	return [int(xx) for xx in input().split()]
def fli():
	return [float(x) for x in input().split()]	
def comp(a,b):
	if(a>b):
		return 2
	return 2 if a==b else 0		
def gi():	
	return [xx for xx in input().split()]
def fi():
	return int(input())
def pro(a): 
	return reduce(lambda a,b:a*b,a)		
def swap(a,i,j): 
	a[i],a[j]=a[j],a[i]	
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())			
def gh():
	sys.stdout.flush()
def isvalid(i,j):
	return 0<=i<n and 0<=j<n	
def bo(i):
	return ord(i)-ord('a')	
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)


t=1

while t>0:
	t-=1
	n=fi()
	a=li()
	s=sum(a)
	c=0
	mod=10**9+7
	mod2=pow(2,mod-2,mod)
	for i in range(n):	
		c=(c+(s-a[i])*a[i])%mod
	print((c*mod2)%mod)

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.read()
    data = list(map(int, input.split()))

    n = data[0]
    data = data[1:]

    sum = 0
    for i in data:
        sum += i
    ans, cnt = 0, 0

    for i in data:
        # cnt += i
        sum -= i
        ans += sum * i
        ans = ans % 1000000007
        # print(ans,sum)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# p = list(map(int, input().split()))
# a, b, c = map(int, input().split())
# n = int(input())
# s = input()
# print(i, end=" ")


n = int(input())
a = list(map(int, input().split()))
ans = 0
mod = 1000000007
sum = 0
for i in range(n):
    sum = sum + a[i]
    sum = sum % mod
    
for i in range(n):
    sum = sum - a[i]
    if sum < 0:
        sum = sum + mod
    ans = ans + a[i] * sum
    ans = ans % mod
print(ans)

Submission status: Accepted

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

mod = 10**9 + 7
class mint:
  def __init__(self, x):
    self.x = x % mod
  def __str__(self): return str(self.x)
  __repr__ = __str__
  def __add__(self, other):
    return(
      mint(self.x + other.x) if isinstance(other, mint) else
      mint(self.x + other)
    )
  def __sub__(self, other):
    return(
      mint(self.x - other.x) if isinstance(other, mint) else
      mint(self.x - other)
    )
  def __mul__(self, other):
    return(
      mint(self.x * other.x) if isinstance(other, mint) else
      mint(self.x * other)
    )
  def __truediv__(self,  other):
    return (
      mint(
        self.x * pow(other.x, mod - 2, mod)
      ) if isinstance(other, mint) else
      mint(self.x * pow(other, mod - 2, mod))
    )
  def __pow__(self, other):
    return (
      mint(pow(self.x, other.x, mod)) if isinstance(other, mint) else
      mint(pow(self.x, other, mod))
    )
  __radd__ = __add__
  def __rsub__(self, other):
    return(
      mint(other.x - self.x) if isinstance(other, mint) else
      mint(other - self.x)
    )
  __rmul__ = __mul__
  def __rtruediv__(self, other):
    return (
      mint(
        other.x * pow(self.x, mod - 2, mod)
      )if isinstance(other, mint) else
      mint(other * pow(self.x, mod - 2, mod))
    )
  def __rpow__(self, other):
    return (
      mint(pow(other.x, self.x, mod)) if isinstance(other, mint) else
      mint(pow(other, self.x, mod))
    )

n = int(input())
a = list(map(int, input().split()))
sum = [0] * n
sum[0] = a[0]
for i in range(n): 
  if (i==0): continue
  sum[i] += a[i] + sum[i-1]
ans = 0
for i in range(n-1):
  ans += mint(a[i] * (sum[n-1] - sum[i]))
print(ans)

Submission status: Accepted

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

def SumOfProductParis(n):
    if n == 0:
        return 0
    elif n == 1:
        return A[0]
    else:
        result = 0
        temp = sum(A)
        result = temp**2
        for i in range(n):
            result -= A[i]**2
        return (result//2)%(10**9+7)

N = int(input())
A = list(map(int, input().split()))

print(SumOfProductParis(N))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 0
suma = sum(A)
for i in range(N-1):
    suma -= A[i]%(10**9+7)
    ans += (A[i] * suma )%(10**9+7)
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
MOD = 1000000007
 
N = int(input())
A = list(map(int, input().split())) 
 
ans = 0
s = sum(A)
 
for a in A:
    s -= a
    ans += (a * s)

ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = [0]*n
ss = 0
mod = 10**9+7
for i in range(n):
  ss += a[i]
  s[i] = ss
a.reverse()
ans = 0
for i in range(n-1):
  ans += (a[i]*s[n-2-i])%mod
print (ans%mod)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a_list = list(map(int, input().split()))

    mod = 1000000007
    sum_left = sum(a_list[1:])
    answer = 0
    for i in range(n-1):
        answer += (a_list[i] * sum_left) % mod
        sum_left -= a_list[i+1]
    print(int(answer % mod))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
mod = 10**9 + 7
n, *A = map(int, open(0).read().split())
B = [b % mod for b in accumulate(A[::-1])][::-1][1:]
s = 0
for a, b in zip(A, B):
  s += a*b
  s %= mod
print(s)

Submission status: Accepted

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

pa = [0]
for i in a:
    pa.append(i + pa[-1])

ans = 0
for i, v in enumerate(a):
    ans += (v * (pa[-1] - pa[i + 1])) % mod
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
mod=1000000007
n=int(input())
x=list(map(int,input().split()))
cl=[1]
for i in range(1,n):
    cl.append(cl[i-1]+x[i])
sum=0
for i in range(n-1):
    sum+= x[i]*(cl[n-1]-cl[i])
    sum%=mod

print(sum)

Submission status: Accepted

Solution code:
N=input()
A=list(map(int,input().split()))
count1=0
count2=0
for a in A[0:]:
    count1=count1+a
    count2=count2+a**2

B=(count1**2-count2)//2
C=B%(10**9+7)
print(C)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(c) for c in input().split() if int(c) > 0]
    MOD = int(10**9+7)
 
    mono = 0
    bi = 0
    for x in A:
        mono += x
        #mono %= MOD
        bi += x**2
        #bi %= MOD
    ans = (mono**2 - bi)//2
    ans %= MOD
    print(ans)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
MOD=10**9+7 #先に書いておく

s=[0] #sのリスト(累積和)
for i in range(0,N): #累積和を作る
    s.append(s[i]+A[i])

sum=0
for j in range(0,N): #合計をだす
    sum+=A[j]*(s[N]-s[j+1])

ans=sum%MOD #10^9+7で割った余りが答え
print(ans)

Submission status: Accepted

Solution code:
import itertools

def main():
    N = int(input())
    A = [int(c) for c in input().split() if int(c) > 0]
    MOD = int(10**9+7)

    mono = 0
    bi = 0
    for x in A:
        mono += x
        #mono %= MOD
        bi += x**2
        #bi %= MOD
    ans = (mono**2 - bi)//2
    ans %= MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 1_000_000_007

csum = [0] * (n + 1)
for i in range(n):
    csum[i + 1] = csum[i] + As[i]

ans = 0
for i in range(n - 1):
    ans += As[i] * (csum[n] - csum[i + 1]) % MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
n = int(input())

a = list(map(int,input().split()))
ans = 0
s = sum(a)
for i in range(n-1):
    ans += (s - a[i]) * a[i]
    ans %= 10**9+7
    s -= a[i]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
MOD = 1000000007
S = sum(A) % MOD
ans = 0

for x in A:
    S -= x
    S %= MOD
    ans += S * x
    ans %= MOD
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 0
mod = (10 ** 9 + 7)
total = sum(a)
for i in range(n):
    total -= a[i]
    ans = (ans + total * a[i]) % mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
sum_a = 0
result = 0
for i in range(n):
  sum_a += a[i]
for j in range(n):
  sum_a -= a[j]
  result += sum_a * a[j]
print(result % (10**9 + 7))

Submission status: Accepted

Solution code:
n=int(input())
hoge=list(map(int,input().split()))
ans=0
wa=hoge[0]
for i in range(1,n):
  ans+=wa*hoge[i]
  ans=ans%(10**9+7)
  wa+=hoge[i]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

mod = 1000000007
S = {}
S[0] = A[0]
for i in range(1, len(A)):
    S[i] = S[i-1] + A[i]

ans = 0
for i in range(len(A)):
    sum = S[len(S)-1] - S[i]
    ans += A[i] * sum
print(ans%mod)

Submission status: Accepted

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

s1 = (sum(nums) - nums[0]) % (10**9 + 7)
sums = [s1]
for i in range(1,n):
  s = sums[i-1] - nums[i]
  s %= 10**9 + 7
  sums.append(s)

ans = 0
for i in range(n):
  temp = nums[i] * sums[i] % (10**9 + 7)
  ans += temp

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

Submission status: Accepted

Solution code:
n = int(input())
MOD = 10 ** 9 + 7
a = [int(i) for i in input().split()]


total = sum(a) % MOD
kotae = 0
for i in range(n-1):
    total -= a[i]
    if(total < 0):
        total += MOD
    kotae += a[i] * total
    kotae = kotae % MOD


print(kotae)

Submission status: Accepted

Solution code:
N = int(input())
A = input().split()

toA = 0
for i in range(N):
    A[i] = int(A[i])
    toA += A[i]

ans = 0
for i in range(0, N):
    toA -= A[i]
    ans += A[i]*toA

print(ans % 1000000007)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split(" ")))
print(int((sum(a)**2-sum([i**2 for i in a]))//2)%int(10**9+7))

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest

modn=1000000007

def resolve():
    n = input()
    inputs = list(map(int, input().split()))
    sum_value = sum(inputs)% modn
    ans=0
    for i in range(len(inputs)-1):
        v = inputs[i]
        sum_value = sum_value - v
        add_value = (v * sum_value) % modn
        ans+=add_value
        ans = ans%modn
    print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
1 2 3"""
        output = """11"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4
141421356 17320508 22360679 244949"""
        output = """437235829"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()