Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from itertools import product

def main():
    n = int(input())

    if n == 1:
        print(1)
        exit()

    if n % 2 == 0:
        ans = 2 * n - 1
        n *= 2
    else:
        ans = n - 1

    prime = [2, 3]
    for i in range(5, 32 * (10**6), 2):
        for p in prime:
            if p * p > i:
                prime.append(i)
                break

            if i % p == 0:
                break

    factors = []
    for p in prime:
        if p * p > n:
            if n > 1:
                factors.append(n)
            break

        if n % p == 0:
            cnt = 0
            while n % p == 0:
                cnt += 1
                n //= p
            factors.append(p ** cnt)

    for tf in product([True, False], repeat=len(factors)):
        a, b = 1, 1
        for i in range(len(factors)):
            if tf[i]:
                a *= factors[i]
            else:
                b *= factors[i]

        if a == 1 or b == 1:
            continue

        if a < b:
            a, b = b, a

        # Euclidean Algorithm
        # a*x - b*y = 1
        # quotient: 商
        l = []
        quo = []
        while a % b > 1:
            l.append(a)
            a = b
            quo.append(0)
            quo[-1], b = divmod(l[-1], b)
        x, y = 1, a//b
        flag = True
        while l:
            if flag:
                x += y * quo.pop()
                b = l.pop()
            else:
                y += x * quo.pop()
                a = l.pop()
            flag = not flag

        if ans > b * y:
            ans = b * y

    print(ans)

main()

### FIXED CODE ###

from itertools import product

def main():
    n = int(input())
    n_copy = n

    if n == 1:
        print(1)
        exit()

    if n % 2 == 0:
        ans = 2 * n - 1
        n *= 2
    else:
        ans = n - 1

    factors = []
    for p in range(2, n):
        if p * p > n:
            if n > 1:
                factors.append(n)
            break

        if n % p == 0:
            cnt = 0
            while n % p == 0:
                cnt += 1
                n //= p
            factors.append(p ** cnt)

    for tf in product([True, False], repeat=len(factors)):
        a, b = 1, 1
        for i in range(len(factors)):
            if tf[i]:
                a *= factors[i]
            else:
                b *= factors[i]

        if a == 1 or b == 1:
            continue

        if a < b:
            a, b = b, a

        # Euclidean Algorithm
        # a*x - b*y = 1
        # quotient: 商
        l = []
        quo = []
        while a % b > 1:
            l.append(a)
            a = b
            quo.append(0)
            quo[-1], b = divmod(l[-1], b)
        x, y = 1, a//b
        flag = True
        while l:
            if flag:
                x += y * quo.pop()
                b = l.pop()
            else:
                y += x * quo.pop()
                a = l.pop()
            flag = not flag

        if ans > b * y:
            ans = b * y

    print(ans)

main()
### BUGGY CODE ###

import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    lim = 60
    zero = [0 for _ in range(lim)]
    one = [0 for _ in range(lim)]

    for ai in a:
        for i in range(lim):
            if ai >> i & 1:
                one[i] += 1
            else:
                zero[i] += 1

    ans = 0
    for i in range(lim):
        ans += 2 ** i * zero[i] * one[i]
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    lim = 60
    zero = [0 for _ in range(lim)]
    one = [0 for _ in range(lim)]

    for ai in a:
        for i in range(lim):
            if ai >> i & 1:
                one[i] += 1
            else:
                zero[i] += 1

    ans = 0
    for i in range(lim):
        ans += 2 ** i * zero[i] * one[i]
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

N,M,P = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]

g = [[] for i in range(N)]
revg = [[] for i in range(N)]

for a,b,_ in ABC:
    a,b = a-1, b-1
    g[a].append(b)
    revg[b].append(a)

st = set([0])
stack = [0]
while stack:
    v = stack.pop()
    for to in g[v]:
        if to in st: continue
        st.add(to)
        stack.append(to)

revst = set([N-1])
stack = [N-1]
while stack:
    v = stack.pop()
    for to in revg[v]:
        if to in revst: continue
        revst.add(to)
        stack.append(to)

use = st & revst
es = []
for a,b,c in ABC:
    a,b = a-1, b-1
    if a in use and b in use:
        es.append((a,b,c))

INF = float('inf')
d = [INF] * N
d[0] = 0
for i in range(N):
    for fr,to,c in es:
        cost = -(c-P)
        if d[to] > d[fr]+cost:
            d[to] = d[fr] + cost
            if i == N-1:
                print(-1)
                exit()

print(max(0,-d[-1]))

### FIXED CODE ###

N,M,P = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]

g = [[] for i in range(N)]
revg = [[] for i in range(N)]

for a,b,_ in ABC:
    a,b = a-1, b-1
    g[a].append(b)
    revg[b].append(a)

st = set([0])
stack = [0]
while stack:
    v = stack.pop()
    for to in g[v]:
        if to in st: continue
        st.add(to)
        stack.append(to)

revst = set([N-1])
stack = [N-1]
while stack:
    v = stack.pop()
    for to in revg[v]:
        if to in revst: continue
        revst.add(to)
        stack.append(to)

use = st & revst
es = []
for a,b,c in ABC:
    a,b = a-1, b-1
    if a in use and b in use:
        es.append((a,b,c))

INF = float('inf')
d = [INF] * N
d[0] = 0
for i in range(N):
    for fr,to,c in es:
        cost = -(c-P)
        if d[to] > d[fr]+cost:
            d[to] = d[fr] + cost
            if i == N-1:
                print(-1)
                exit()

print(max(0,-d[-1]))
### BUGGY CODE ###



n = 0
a = []

def format_input(filename = None):
	global n
	global a
	if filename == None:
		n = int(input())
		a = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(2, 2 * 10**5)
		a = [rng(1, i) for i in range(1, n)]
		print(n)
		print(' '.join(list(map(str, a))))

def get_answer():
	for i in range(1, n+1):
		print(a.count(i))

if __name__ == '__main__':
	format_input()

	get_answer()


### FIXED CODE ###



n = 0
a = []

def format_input(filename = None):
	global n
	global a
	if filename == None:
		n = int(input())
		a = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(2, 2 * 10**5)
		a = [rng(1, i) for i in range(1, n)]
		print(n)
		print(' '.join(list(map(str, a))))

def get_answer():
	count = [0] * (n+1)
	for i in a:
		count[i] += 1
	for i in range(1, n+1):
		print(count[i])

if __name__ == '__main__':
	format_input()

	get_answer()
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC = [list(map(int,input().split())) for _ in range(Q)]
for i in range(Q):
  A = [BC[i][1] if j == BC[i][0] else j for j in A]
  print(sum(A))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC = [list(map(int,input().split())) for _ in range(Q)]
total = sum(A)
dict = {}
for i in range(len(A)):
  if A[i] not in dict:
    dict[A[i]] = 1
  else:
    dict[A[i]] += 1
for i in range(Q):
  if BC[i][0] not in dict:
    dict[BC[i][0]] = 0
  if BC[i][1] not in dict:
    dict[BC[i][1]] = 0
  if dict[BC[i][0]] > 0:
    num = (BC[i][1] - BC[i][0]) * (dict[BC[i][0]])
    total += num
  print(total)
  dict[BC[i][1]] += dict[BC[i][0]]
  dict[BC[i][0]] = 0
### BUGGY 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()
     
def get_yakusu(n):
    ans = set()
    for i in range(1, int(math.sqrt(n)) + 2):
        if n % i == 0:
            if i != 1:
                ans.add(i)
            if n // i != i:
                ans.add(n // i)
    return ans

def main():
    N = I()
    cnt = 0
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    for n in yakusu:
        cpN = N
        while cpN % n == 0 and cpN > 0:
            cpN //= n
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()



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

def get_yakusu(n):
    ans = set()
    for i in range(1, int(math.sqrt(n)) + 2):
        if n % i == 0:
            if i != 1:
                ans.add(i)
            if n // i != i:
                ans.add(n // i)
    return ans

def main():
    N = I()
    cnt = 0
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    for n in yakusu:
        cpN = N
        loop = 0
        while True:
            loop += 1
            if loop > 100:
                break
            if cpN % n == 0:
                cpN = cpN // n
            else:
                break
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()
### BUGGY CODE ###

import itertools
n = int(input())
lis = [input() for _ in range(n)]
lis.sort()
choice = list(itertools.combinations(range(n), 3))
count = 0
for ch in choice:
    master = ['M','A','R','C','H']
    for c in ch:
        if lis[c][0] in master:
            master.remove(lis[c][0])
        else:
            break
        if len(master) == 2:
            count += 1
print(count)

### FIXED CODE ###

import collections
import itertools
n = int(input())
li = []
for i in range(n):
    li.append(input()[0])

c = collections.Counter(li)
c_li = [c['M'],c['A'],c['R'],c['C'],c['H']]
#print(li,c,c_li)

count = 0
combination = list(itertools.combinations([0,1, 2, 3,4], 3))
for co in combination:
    tmp = 1
    for c in co:
        if c_li[c] == 0:
            tmp = 0
            break
        tmp *= c_li[c]
    count += tmp
print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500000)

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

def gcd_list(li):
	if len(li) > 2:
		x = gcd(li[-1], li[-2])
		li = li[:-2] + [x]
		return gcd_list(li)
	else:
		return gcd(li[0], li[1])

N, X = map(int, input().split())

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

li = [abs(i - X) for i in x]

li = [i for i in li if i]

if len(li) == 1:
	print(li[0])
else:
	print(gcd_list(li))

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)

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

	if b:
		return gcd(b, a % b)
	else:
		return a

def gcd_list(li):
	if len(li) > 2:
		x = gcd(li[-1], li[-2])
		li = li[:-2] + [x]
		return gcd_list(li)
	else:
		return gcd(li[0], li[1])

N, X = map(int, input().split())

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

li = [abs(i - X) for i in x]

# li = [i for i in li if i]
# li = sorted(li)
if len(li) == 1:
	print(li[0])
else:
	ans = li[0]
	for i in range(1,N):
		ans = gcd(ans, li[i])
	print(ans)
### BUGGY CODE ###

n=int(input())
s=input()
res = 10**9
for i in range(n):
    tres = s[:i].count("W")+s[i+1:].count("E")
    res = min(tres,res)
print(res)

### FIXED CODE ###

n=int(input())
s=input()
res = s[1:].count("E")
tres = res
for i in range(1,n):
    if s[i] == "E":
        tres -= 1
    if s[i-1] == "W":
        tres += 1
    res = min(res,tres)
print(res)
### BUGGY CODE ###

n = input()
n = n[::-1]
n += '0'
cnt = 0
dp = [[float('inf')] * 2 for _ in range(len(n) + 1)]
dp[0][0] = 0
dp[0][1] = 1
for i in range(len(n)):
    a = int(n[i])
    dp[i + 1][0] = min(dp[i][0] + a, dp[i][1] + 10 - a)
    dp[i + 1][1] = min(dp[i][0] + a + 1, dp[i][1] + 10 - (a + 1))
print(min(dp[len(n)][0], dp[len(n)][1]))

### FIXED CODE ###

n = input()
n = n[::-1]
n += '0'
cnt = 0
tmp = 0
for i in range(len(n)):
    a = int(n[i])
    a += tmp
    if a == 5:
        cnt += a
        if int(n[i + 1]) >= 5:
            tmp = 1
        else:
            tmp = 0
    elif a < 5:
        cnt += a
        tmp = 0
    else:
        cnt += 10 - a
        tmp = 1
print(cnt)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()

# 和があればTrue
# dp = [False] * ((N + 1) * N // 2 + 1)
dp = defaultdict(int)

# for k in range(N + 1, K - 1, -1):
q = [[10 ** 10 + i for i in range(0, N + 1)]]
# print(q)
while q:
    a = q.pop()
    # print(a)
    s = sum(a)
    # print(a)
    # print(s)
    dp[s] = True
    if len(a) > K:
        # K より大きければ続ける
        for i in range(len(a)):
            b = deepcopy(a)
            b.pop(i)
            q.append(b)
# print(sum(dp) % mod)
print(len(dp) % mod)


    






### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()

ans = 0
for i in range(K, N + 2):
    B = N * (N + 1) // 2 - (N - i) * (N - i + 1) // 2
    A = (i - 1) * i // 2
    ans += (B - A + 1)
print(ans % mod)
### BUGGY CODE ###

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

C.sort()

ans = 0

if N != 1:
    for i in range(N):
        ans += C[i] * (N + 1 - i) * (2 ** (N - 2))
        ans %= 10 ** 9 + 7
    ans *= 2 ** N
else:
    ans = C[0] * 2

ans %= 10 ** 9 + 7

print(ans)

### FIXED CODE ###

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

C.sort()

ans = 0

mod = 10 ** 9 + 7

pattern = (2 ** (N - 2)) % mod

if N != 1:
    for i in range(N):
        c = C[i]
        ans += c * (N + 1 - i) * pattern
        ans %= mod
    ans *= 2 ** N
else:
    ans = C[0] * 2

ans %= mod

print(ans)
### BUGGY CODE ###

N = int(input())
P = [int(i) for i in input().split(" ")]

ans = 0
for L in range(N-1):
    for R in range(L+1, N):
        ans += sorted(P[L:R+1], reverse=True)[1]
print(ans)

### FIXED CODE ###

N = int(input())
P = [int(i) for i in input().split(" ")]

# 各数字が何番目に入っているかを保存する
pos = [0] * (N + 1)
for i in range(N):
    pos[P[i]] = i + 1

l = [0]+[i for i in range(N + 1)]
r = [i + 1 for i in range(N + 1)] + [N + 1]

# 1から順番に見ていく
ans = 0
for i in range(1, N + 1):
    idx = pos[i]
    l1, r1 = l[idx], r[idx]
    l2, r2 = l[l1], r[r1]
    ans += i * ((l1 - l2) * (r1 - idx) + (idx - l1) * (r2 - r1))
    l[r1], r[l1] = l1, r1
print(ans)
### BUGGY CODE ###

from itertools import chain,combinations


N = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def _powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1, 0, -1))


def prod(iterable):
    ret = 1
    for i in iterable:
        ret *= i
    return ret


div_list = prime_factorize(N)
if(div_list) == 1:
    ans = sum(div_list) - 1
else:
    ans = N - 1
    power_set = _powerset(div_list)
    for p in power_set:
        left = prod(p)
        right = N // left
        ans = min(ans, left + right -2)


print(ans)




### FIXED CODE ###

import math
N = int(input())

nq = int(N ** (1/2))

ans = N -1
for i in range(1, nq + 1):
    if N % i == 0:
        tmp = i + (N // i) -2
        ans = min(ans, tmp)

print(ans)
### BUGGY CODE ###

s = input()
dp = [[0 for _ in range(0,4)] for _ in range(0,len(s)+1)]
dp[len(s)][3] = 1
dp[len(s)][0] = 0
dp[len(s)][1] = 0
dp[len(s)][2] = 0
abc = ["A","B","C"]
for i in range(len(s)-1,-1,-1):
    m = 1
    if s[i] ==  "?":
        m=3
    dp[i][3] += m * dp[i+1][3]

for i in range(len(s)-1,-1,-1):
    for j in range(0,3):
        m1,m2 = 1,0
        if s[i] == "?":
            m1,m2 = 3,1
        if s[i] == abc[j]:
            m1,m2 = 1,1
        dp[i][j] += m1 * dp[i+1][j] + m2 * dp[i+1][j+1]
        dp[i][j] %= (10**9 + 7)
# for i in range(len(s),-1,-1):
#     print(dp[i])
print(dp[0][0] % (10**9 + 7))


### FIXED CODE ###

s = input()
dp = [0 for _ in range(0,4)]
dp[3] = 1
dp[0] = 0
dp[1] = 0
dp[2] = 0
abc = "ABC".index
mod = 10**9 + 7
for i in range(len(s)-1,-1,-1):
    if s[i] == "?":
        dp = [
        (dp[0]*3+ dp[1])%mod
        ,(dp[1]*3+ dp[2])%mod
        ,(dp[2]*3 + dp[3])%mod
        ,(dp[3]*3)%mod
        ]
    else:
        num = abc(s[i])
        dp[num] += dp[num+1] % mod
print(dp[0] %mod)
### BUGGY CODE ###

N = int(input())

tmp = []
counter = 0
for i in range(N):
    new_str = ''.join(list(sorted(str(input()))))
    if i != 0:
        counter += tmp.count(new_str)
    tmp.append(new_str)

    #for j in range(i):
    #    if str(new_str) == str(tmp[j]):
    #        counter += 1

print(counter)

### FIXED CODE ###

N = int(input())

tmp = []
counter = 0
for i in range(N):
    new_str = ''.join(sorted(str(input())))
    
    #if i != 0:
    #    counter += tmp.count(new_str)
    tmp.append(new_str)

import collections
c = collections.Counter(tmp)

#new_str_list = [i for i in new_str = ''.join(list(sorted(str(input()))))]
#print(new_str_list)

    #for j in range(i):
    #    if str(new_str) == str(tmp[j]):
    #        counter += 1
value = list(c.values())
#print(value)

for j in value:
    for k in range(j):
        counter += k

print(counter)
### BUGGY CODE ###

import functools
import operator

n=int(input())

m=list(map(int,input().split()))
result = functools.reduce(operator.mul, m)

if result<=pow(10,18):
  print(result)
else:
  print(-1)

### FIXED CODE ###

import sys

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

ans=1
if 0 in m:
  print(0)
  sys.exit()

for i in range(n):
  ans=ans*m[i]
  if ans>pow(10,18):
    print(-1)
    sys.exit()

if ans<=pow(10,18):
  print(ans)
### BUGGY CODE ###

S = input()
T = input()
l = len(S)
right = True
for c in range(26):
    st = set()
    for i in range(l):
        if ord(T[i]) == ord('a') + c:
            st.add(S[i])
    if len(st) > 1:
        right = False
for c in range(26):
    st = set()
    for i in range(l):
        if ord(S[i]) == ord('a') + c:
            st.add(T[i])
    if len(st) > 1:
        right = False
print("Yes" if right else "No")

### FIXED CODE ###

S = input()
T = input()
l = len(S)
right = True
dic = {}
for i in range(l):
    if T[i] not in dic:
        dic[T[i]] = set()
    dic[T[i]].add(S[i])
for key, st in dic.items():
    if len(st) > 1:
        right = False
dic = {}
for i in range(l):
    if S[i] not in dic:
        dic[S[i]] = set()
    dic[S[i]].add(T[i])
for key, st in dic.items():
    if len(st) > 1:
        right = False
print("Yes" if right else "No")
### BUGGY CODE ###

n = int(input())
a = []
result = 0
a += [int(num) for num in input().split()]

for i in range(n-1):
    for j in range(i+1,n):
        result += a[i]*a[j]

print(result%1000000007)

### FIXED CODE ###

n = int(input())
A = [int(i) for i in input().split()]
cum_sum = [0]
ans,sum = 0,0

# 累積和を求める
for i in range(len(A)):
    cum_sum.append(cum_sum[i]+A[i])

for i in range(n):
    # A[i+1]+A[i+2]+...+A[n]を累積和で求める
    sum = (cum_sum[n]-cum_sum[i+1])%1000000007
    # A[i]*(A[i+1]+A[i+2]+...+A[n])の処理
    # なおA[i+1]=A[j],A[i+2]=A[j+2]...である
    ans += A[i]*sum
    # 1000000007で割る
    ans %= 1000000007   
print(ans)