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: Runtime Error

Solution code:
def sum(a, n):  
    cnt = dict() 
    ans = 0
    pre_sum = 0
    for i in range(n):  
        ans += (i * a[i]) - pre_sum  
        pre_sum += a[i]  

        if (a[i] - 1) in cnt: 
            ans -= cnt[a[i] - 1]  

        if (a[i] + 1) in cnt: 
            ans += cnt[a[i] + 1]  

        if a[i] not in cnt: 
            cnt[a[i]] = 0
        cnt[a[i]] += 1
      
    return ans  
  
  n = int(input())
  arr = list(map(int,input().split()))
  print(sum(arr,n))

Submission status: Runtime Error

Solution code:
#C
import numpy as np
n  = int(input())
a_ls = list(map(int, input().split()))

a_ls = (np.array([a_ls]))%(10**9+7)
a_ls2 = (np.array(a_ls).T)
tmp = np.dot(a_ls2, a_ls)%(10**9+7)
ans = int(((np.sum(tmp) - np.sum(np.diag(tmp)))/2)%(10**9+7))
print(ans)

Submission status: Runtime Error

Solution code:
# Efficient python 3 program to find sum 
# pair products in an array. 

# required function 
def findProductSum(A, n): 
	
	# calculating array sum (a1 + a2 ... + an) 
	array_sum = 0
	for i in range(0, n, 1): 
		array_sum = array_sum + A[i] 

	# calcualting square of array sum 
	# (a1 + a2 + ... + an)^2 
	array_sum_square = array_sum * array_sum 

	# calcualting a1^2 + a2^2 + ... + an^2 
	individual_square_sum = 0
	for i in range(0, n, 1): 
		individual_square_sum += A[i] * A[i] 

	# required sum is (array_sum_square - 
	# individual_square_sum) / 2 
	return (array_sum_square -
			individual_square_sum) / 2

# Driver code 
if __name__ == '__main__': 
  	n = int(input())
	A = list(map(int,input().strip().split()))[:n] 
	print(findProductSum(A, n)%1000000007)
	
# This code is contributed by 
# Sahil_Shelangia

Submission status: Runtime Error

Solution code:
def sum_a(array):
    total = 0
    for i in range(len(array)):
        total += array[i]**2
    return(total)

n = int(input())
a = list(map(int,input().split()))
import numpy as np

c = np.array(a)
d = np.array(a)

e = np.outer(c,d)

f = np.sum(e)
g = sum_a(a)

h = int((f-g)/2)
p = h%(10**9+7)
print(p)

Submission status: Runtime Error

Solution code:
n=int(input())
s=input()
p=list(s.split())
s1=0
s2=0
for i in range(0,n)
  s1=s1+int(p[i])
  s2=s2+(int(p[i])*int(p[i]))
k= ((s1**2)-s2)//2
k=k%1000000007

print(k)

Submission status: Runtime Error

Solution code:
n = input()
a_list = input().split(" ")

b = [int(a) for a in a_list]
max = 10**9 + 7

sum = 0
for i in range(0, len(b)-2):
  for j in range(i+1, len(b)-1):
    sum += b[i] * b[j]
    while sum => max:
      sum -= max
print(sum)

Submission status: Runtime Error

Solution code:
# Efficient python 3 program to find sum 
# pair products in an array. 

# required function 
def findProductSum(A, n): 
	
	# calculating array sum (a1 + a2 ... + an) 
	array_sum = 0
	for i in range(0, n, 1): 
		array_sum = array_sum + A[i] 

	# calcualting square of array sum 
	# (a1 + a2 + ... + an)^2 
	array_sum_square = array_sum * array_sum 

	# calcualting a1^2 + a2^2 + ... + an^2 
	individual_square_sum = 0
	for i in range(0, n, 1): 
		individual_square_sum += A[i] * A[i] 

	# required sum is (array_sum_square - 
	# individual_square_sum) / 2 
	return (array_sum_square -
			individual_square_sum) / 2

# Driver code 
if __name__ == '__main__': 
  	n = int(input())
	A = list(map(int,input().strip().split()))[:n] 
	print(findProductSum(A, n))
	
# This code is contributed by 
# Sahil_Shelangia

Submission status: Runtime Error

Solution code:
#C
import numpy as np
n  = int(input())
a_ls = list(map(int, input().split()))

a_ls = (np.array([a_ls]))%(10**9+7)
a_ls2 = (np.array(a_ls).T)
tmp = np.dot(a_ls2, a_ls)
ans = int(((np.sum(tmp) - np.sum(np.diag(tmp)))/2)%(10**9+7))
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
s=input()
p=list(s.split())
s1=0
s2=0
for i in range(0,n)
  s1=s1+int(p[i])
  s2=s2+(int(p[i])*int(p[i]))
k= ((s1**2)-s2)//2
k=k%1000000007
//abcdef
print(k)

Submission status: Runtime Error

Solution code:
N = int(input())

numbers = list(map(int, input().split()))

modulo = 1000000007
S = 0

for i in range(N-1):
	for j in range(i+1, N):
      S += numbers[i]*numbers[j]
      
print(S%modulo)

Submission status: Runtime Error

Solution code:
#include<iostream>
using namespace std;
int main()
{
    // 整数の入力
    int N;
    cin >> N;
  　
    vector<int> vec(N);
	for (int i = 0; i < N; i++) {
		cin >> vec.at(i); 
	}
  	
  	long long ans = 0;
  	for (int i=0; i < N; i++){
    	for (int j=i; j < N; j++){
        	if(i!=N)
          		sum_ans = N.at(i)*N.at(j) % (10**9+7); 
        }
     }
    // 出力
    cout << sum_ans << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
import numpy as np
ans=0
n=int(input())
li=list(map(int,input().split()))
for i in range(1,n):
    L=li
    k=np.cumsum(L[:i])
    ans+=k*li[i]
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
def findProductSum(A, n): 
      
    # calculating array sum (a1 + a2 ... + an) 
    array_sum = 0
    for i in range(0, n, 1): 
        array_sum = array_sum + A[i] 
  
    # calcualting square of array sum 
    # (a1 + a2 + ... + an)^2 
    array_sum_square = array_sum * array_sum 
  
    # calcualting a1^2 + a2^2 + ... + an^2 
    individual_square_sum = 0
    for i in range(0, n, 1): 
        individual_square_sum += A[i] * A[i] 
  
    # required sum is (array_sum_square - 
    # individual_square_sum) / 2 
    return ((array_sum_square - 
            individual_square_sum) / 2)%1000000007

if __name__ == '__main__': 
    n = int(input())
    arr=list()
    for i in range(n):
      arr.append(int(input()))
    print(int(findProductSum(arr, n)))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fi first
#define se second
#define MOD 1000000007
int main(){
	ll a, cnt=0, ans=0;
	cin>>a;
	ll arr[a];
	for (ll i=0; i<a; i++) cin>>arr[i], cnt+=arr[i];
	for (ll i=0; i<a-1; i++){
		cnt-=arr[i];
		ans+=arr[i]*cnt;
		ans%=MOD;
	}
	cout<<ans<<endl;
}
//    ll a, ans=0;
//    cin>>a;
//    ll arr[a+1], ps[a+1];
//    for (ll i=1; i<=a; i++) cin>>arr[i];
//    ps[0]=0;
//    for (ll i=1; i<=a; i++) ps[i]=ps[i-1]+arr[i];
//    for (ll i=1; i<a; i++){
//        ans+=(arr[i]*((ps[a]-ps[i])%MOD))%MOD;
//        ans%=MOD;
//    }
//    cout<<ans<<endl;

Submission status: Runtime Error

Solution code:
import numpy as np
n = input()
a  = numpy.array([n])
s = 0
t = 0
for i in range(n):
  a[i] = input()
  s += a[i]
  t += a[i]*a[i]

l = ((s*s - t) // 2) % 1000000007

print(l)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
prod = [A[i]*A[j] i for in range(N-1) j for in range(i+1, N)]
print(sum(prod))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np
n = input()
a  = numpy.array([n])
s = 0
t = 0
for i in range(n):
  s += a[i]
  t += a[i]*a[i]

l = ((s*s - t) // 2) % 1000000007

print(l)

Submission status: Runtime Error

Solution code:
def sum_a(array):
    total = 0
    for i in range(len(array)):
        total += array[i]**2
    return(total)

n = int(input())
a = list(map(int,input().split()))
import numpy as np

c = np.array(a)
d = np.array(a)

e = np.outer(c,d)

f = np.sum(e)
g = sum_a(a)

print((int((f-g)/2)%(10**9+7)))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def findProductSum(A, n): 
      
    # calculating array sum (a1 + a2 ... + an) 
    array_sum = 0
    for i in range(0, n, 1): 
        array_sum = array_sum + A[i] 
  
    # calcualting square of array sum 
    # (a1 + a2 + ... + an)^2 
    array_sum_square = array_sum * array_sum 
  
    # calcualting a1^2 + a2^2 + ... + an^2 
    individual_square_sum = 0
    for i in range(0, n, 1): 
        individual_square_sum += A[i] * A[i] 
  
    # required sum is (array_sum_square - 
    # individual_square_sum) / 2 
    return ((array_sum_square - 
            individual_square_sum) / 2)%1000000007

if __name__ == '__main__': 
    n = int(input())
    arr=list()
    for i in range(n):
      arr.append(int(input()))
    print(findProductSum(arr, n))

Submission status: Runtime Error

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

mod = 10**9+7
sum_a = sum(a)%mod
sum_a2 = sum_a**2%mod

for i in range(n):
    sum_a2 -= (a[i]**2)
    sum_a2 %= mod
    
if sum_a2%2 == 0:
    ans = sum_a2//2
else:
    ans = ((ans+mod)//2)%mod

print(ans)

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin

def main():
    n = int(stdin.readline().rstrip())
    ls = list(map(int, stdin.readline().split()))
    lsm = list(set(ls))
    m = len(lsm)
    ans = 0
    for i in range(n-1):
        for j in range(i+1, n):
            ans = (ans + lsm[i] * lsm[j]) % (10**9 + 7)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

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

ans = 0

for i in range(N):
	ans = (ans +  A[i] * numpy.sum(A[i+1:N])) % (10**9+7)

print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
S=list(input().split())
A=[int(n) for n in S]
ans=int(0)
for i in A:
    for j in B:
        ans += i*j
print(ans)

Submission status: Runtime Error

Solution code:
n= int(input())
a= [int(i) for i in input().split()]
pref=[0]*n
pref[0] = a[0]%m
for i in range(1,n):
    pref[i] =  (pref[i-1]+a[i])%m
m = 10**9+7
ans = 0
#print(pref)
for i in range(n-1):
    ans+= (a[i]%m *((pref[n-1]-pref[i])%m))%m
    ans = ans%m
print(ans)
#437235829

Submission status: Runtime Error

Solution code:
#C
import numpy as np
n  = int(input())
a_ls = list(map(int, input().split()))

a_ls = np.array([a_ls])
a_ls2 = np.array(a_ls).T
tmp = np.dot(a_ls2, a_ls)
ans = int(((np.sum(tmp) - np.sum(np.diag(tmp)))/2)%(10**9+7))
print(ans)

Submission status: Runtime Error

Solution code:
a=input()
a = np.array(list(map(int, input().split())))
count=1
tmp=0
for i in a[:-1]:
    tmp=(tmp+i*(a[count:]).sum())%(10**9+7)
    count+=1
print(tmp)

Submission status: Runtime Error

Solution code:
counter = 0
lis = []
N = int(input())
A = list(map(int, input().split()))
for pair in itertools.combinations(A, 2):
    lis.append(pair)
for n in lis:
    counter += n[0] * n[1]
print(counter%1000000007)

Submission status: Runtime Error

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

for i in range(1, n):
    ans += li[0]*li[i]
    check = ans

check = ans
for i in range(1, n):
    check -= li[i] * li[i-1]
    check /= li[i-1]
    check *= li[i]
    ans += check
    ans %= mod

print(int(ans))

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
b = []
for i in range(n):
  for j in range(n):
    b.append((a[i] % (10 ** 9 + 7)) * (a[j] % (10 ** 9 + 7)))
print(sum(b) % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
4
141421356 17320508 22360679 244949

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
a = list(map(int,input().split()))
sum = 0
aa = np.array(a).reshape(1,n)
mat = np.dot(aa.T,aa)
s = np.sum(mat)
for i in range(n):
  s -= a[i]*a[i]
sum = int(s/2)
sum = sum % (10**9+7)

print(sum)

Submission status: Runtime Error

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

B = [0]*N

num = 0
for i in reversed(range(N)):
    B[i] = A[i] + num
    num = B[i]
    
ans = 0
for i in range(N-1):
    ans += A[i]*B[i+1] 

print(ans%1000000007)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
  
using namespace std;
 
#define endl "\n"
#define JAM(x) cout<< #x <<" = "<<x<<"\n"
#define II() ( { int a ; read(a) ; a; } )
#define LL() ( { ll a ; read(a) ; a; } )
#define DD() ({double a; scanf("%lf", &a); a;})
 
 
//Fast Reader
template<class T>inline bool read(T &x){
    int c=getchar();int sgn=1;
    while(~c&&c<'0'||c>'9'){if(c=='-')sgn=-1;c=getchar();}
    for(x=0;~c&&'0'<=c&&c<='9';c=getchar())x=x*10+c-'0'; 
    x*=sgn; return ~c;
}
 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> PII;
typedef vector<PII> VPI;
 
const int INF=2e9;
const int MX=100005;
const int MOD=1000000007;
const double PI=acos(-1.0);




long long int power(long long int a,long long int b)
{
    a %= MOD;
    long long int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
bool isprime(int n)
{
    if(n==1)
    return 0;
    int i;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        return false;
    }
    return true;
}



/*_______________________________________________*/





int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    long int m=(1000000007);
    long int a[n];
    long int sm=0,i;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    long long int ans=0;
    for(i=n-1;i>=0;i--)
    {
        ans=(ans+(sm*a[i]+m)%m+m)%m;
        sm=((sm+a[i])%m)%m;
    }
    cout<<ans;
}

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys

import numpy as np


def main():
    def readline() -> str:
        s = sys.stdin.readline()
        return s.rstrip()

    n: int = int(readline())
    a: np.ndarray = np.array(tuple(int(a_i) for a_i in readline().split())).reshape((1, -1))

    prime: int = 10**9 + 7

    a_up: np.ndarray = np.triu(a.T @ a % prime, k=1)
    print(np.sum(a_up) % prime)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

ans=0
for k in range(n-1):
    for j in range(i+1,n):
        ans+=(i[k]*i[j])%(10**9+7)

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

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(map(int,input().split()))
s=0
for i in range(0,n-1):
  for j in range(i+1,n+1):
  x=l[i]*l[j]
  s=s+x
print(s)

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(map(int,input().split()))
s=0
for i in range(0,n-1):
  for j in range(i+1,n):
  x=l[i]*l[j]
  s=s+x
print(s)

Submission status: Runtime Error

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

total = 0
before = 0
for i in range(len(As) - 1):
    if i == 0:
        total = total + As[i] * sum(As[i+1:])
        before = As[i] * sum(As[i+1:])
    else:
        total = total + (((before / As[i-1]) - As[i]) * As[i])
        before = (((before / As[i-1]) - As[i]) * As[i])

total = total % (10**9 + 7)

print(int(total))

Submission status: Runtime Error

Solution code:
n=int(input())
a=[]
for i in range(n):
  num=int(input())
  a.append(num)
ans=0
for i in range(0,n-1):
  for j in range(i+1,n):
    ans+=a[i]*a[j]

print(ans)

Submission status: Runtime Error

Solution code:
34I=lambda:list(map(int,input().split()))
mod=10**9+7
n,=I()
l=I()
pre=l.copy()
suf=l.copy()
for i in range(n-2,-1,-1):
	suf[i]+=suf[i+1]
ans=0
#print(suf)
for i in range(n-1):
	ans+=(l[i]*suf[i+1])
	ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys

import numpy as np


def main():
    def readline() -> str:
        s = sys.stdin.readline()
        return s.rstrip()

    n: int = int(readline())
    a: np.ndarray = np.array(tuple(int(a_i) for a_i in readline().split())).reshape((1, -1))

    a_up: np.ndarray = np.triu(a.T @ a, k=1)
    print(np.sum(a_up))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def resolve():
    import itertools
    import numpy as np

    n = int(input())
    A = np.asarray(list(map(int, input().split())))
    s = sum(A)
    print((s**2 - sum(A**2))//2 % (10**9 + 7))

resolve()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(i) for i in input().split()]

sum1 = 0
sum2 = 0

for _ in a:
  sum1 += _
  sum2 += (a*a)
sum1 = (sum1 * sum1)
print(sum1 - sum2)

Submission status: Runtime Error

Solution code:
n = int(input())
lis = list(map(int, input().split())
sum = 0
for i in lis:
   for j in lis:
        sum += i * j
print(sum % 1000000009)

Submission status: Runtime Error

Solution code:
mod = int(1e9 + 7)

def pw(b, ex):
    if ex == 0: return 1
    if ex == 1: return b
    if ex & 1: return b % mod * pw((b*b) % mod, ex >> 1) % mod
    return pw((b*b) % mod, ex >> 1) % mod

n = int(input())
x = list(map(int,input().split()))
st = 0
en = 0

for i in x:
    st = (st + i) % mod
    en = (en + (i * i) % mod) % mod

ans = int((st * st - en + mod) % mod)
ans = int(ans * int(pw(2, mod - 2)) % mod) % mod
print (int(ans))

mod = int(1e9 + 7)

def pw(b, ex):
    if ex == 0: return 1
    if ex == 1: return b
    if ex & 1: return b % mod * pw((b*b) % mod, ex >> 1) % mod
    return pw((b*b) % mod, ex >> 1) % mod

n = int(input())
x = list(map(int,input().split()))
st = 0
en = 0

for i in x:
    st = (st + i) % mod
    en = (en + (i * i) % mod) % mod

ans = int((st * st - en + mod) % mod)
ans = int(ans * int(pw(2, mod - 2)) % mod) % mod
print (int(ans))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n=input()
n=int(n)
arr=list(map(int,input().rstrip().split()))
for i in range(len(arr)):
    for j in range(i+1,len(arr)):
        Sum=(Sum+(arr[i]*arr[j]))%1000000007

print(Sum)

Submission status: Runtime Error

Solution code:
num = int(input())
ar = list(map(int,input().split()))
mod = 10**9 + 7
somee = sum(arr)
ans = 0
for i in range(num):
    ans+=(somee-ar[i])*ar[i]
print((ans//2)%mod)

Submission status: Runtime Error

Solution code:
import numpy as np
n=int(input())
a=list(map(int,input().split()))
aa=[x*x for x in a]
c=sum(sum(np.outer(a,a)))
c-=sum(aa)
c=c//2
print(c%(10**9+7))

Submission status: Runtime Error

Solution code:
n = int(input())
p = input().split()
product = 0
    for i in range(n): 
        for j in range(i+1,n): 
            product = product + int(p[i])*int(p[j]) 
print(product)

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
b = []
for i in range(n):
  for j in range(n):
    b.append((a[i] % (10 ** 9 + 7)) * (a[j] % (10 ** 9 + 7)))
print(sum(b))

Submission status: Runtime Error

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

ans = 0
sum_arr = sum(arr)

for x in arr:
    ans += x * (sum_arr - x) // 2
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
import numpy
n = int(input())
a = [int(x) for x in input().split()]
MOD = 10**9 +7
x = numpy.array(a)
result = ((x.sum()**2 - x.dot(x)) // 2)%MOD
        
print(result)
# print(s%MOD)

Submission status: Runtime Error

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

sA = sum(As) % (10 ** 9 + 7)
print((sA * sA - sum( (A * A % (10 ** 9 + 7) for A in As) ) ) * pow(2, -1, 10 ** 9 + 7) % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(map(int,input().split()))
su=l[0]
ans=0
for i in range(1,n):
    ans+=su*l[i]
    ans%=mod
    su+=l[i]
    su%=mod
print(ans)