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

s=input()
a=0
now=1
l=[0]*2019
for i in list(s)[::-1]:
    a=(a+now*int(i))%2019
    l[a]+=1

    now*=10
ans=0
for i in l:
    ans+=(i-1)*i//2
print(ans+l[0])

### FIXED CODE ###

s=input()
a=0
now=1
l=[0]*2019
for i in list(s)[::-1]:
    a=(a+now*int(i))%2019
    l[a]+=1

    now*=10
    now%=2019
ans=0
for i in l:
    ans+=(i-1)*i//2
print(ans+l[0])
### BUGGY CODE ###

R,G,B,N = map(int,input().split())

ans = 0
balls = N
for r in range(0,(balls//R)+1):
  balls_r = balls - R*r
  for g in range(0,(balls//G)+1):
    balls_g = balls_r - G*g
    for b in range(0,(balls//B)+1):
      balls_b = balls_g - B*b

      if balls_b == 0:
        ans += 1

print(ans)

### FIXED CODE ###

R,G,B,N = map(int,input().split())

ans = 0
balls = N
for r in range(0,(balls//R)+1):
  balls_r = balls - R*r
  for g in range(0,(balls_r//G)+1):
    balls_g = balls_r - G*g
    if (balls_g >= 0) and (balls_g % B == 0):
      ans += 1

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

n,p = list(map(int,input().split()))
s = input()

if p == 2 or p == 5:
  ans = 0
  for i,c in enumerate(s):
    if int(c)%p == 0:
      ans += i+1
  print(ans)
  exit()

S = list(map(int,[x for x in s]))
M = list(map(lambda x:x%p, S[::-1]))

MM = [0]*(n+1)
for i,m in enumerate(M):
    MM[i+1] = m*10**(i+1) + MM[i]

M = list(map(lambda x:x%p, MM))

ans = 0
U = set(M)

for u in U:
  cnt = M.count(u)
  ans += (cnt*(cnt-1))//2

print(int(ans))

### FIXED CODE ###

n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (s*i +pre)%p
 
M = [0]*p
M[0] = 1
t = 1
now = 0
for i in S[::-1]:
    i = int(i)
    now += i*t
    now %= p
    M[now] += 1
    t = t*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)
### BUGGY CODE ###

from operator import itemgetter

N = int(input())
xyh = [list(map(int, input().split())) for _ in range(N)]
checked = [[False for _ in range(101)] for _ in range(101)]

xyh.sort(key=itemgetter(2), reverse=True)

q = [xyh[0]]
ans = []
while not ans:
    qq = []
    for s in q:
        x = s[0]
        y = s[1]
        for i, d in enumerate(xyh):
            if d[2] == 0:
                continue
            ch = abs(d[0] - x) + abs(d[1] - y) + d[2]
            if i == 0:
                chpre = ch
            if chpre != ch:
                break
        if chpre == ch:
            ans = [x, y, ch]
            break
        checked[x][y] = True
        nexts = [[x+1, y], [x-1, y], [x, y+1], [x, y-1]]
        for ne in nexts:
            nx = ne[0]
            ny = ne[1]
            if 0 <= nx <= 100 and 0 <= ny <= 100:
                if not checked[nx][ny]:
                    qq.append(ne)
    q = qq


print(' '.join([str(a) for a in ans]))
        
        



### FIXED CODE ###

N = int(input())
P = [list(map(int, input().split())) for _ in range(N)]

for cx in range(101):
    for cy in range(101):
        H = -1
        ok = True
        for x, y, h in P:
            if h == 0:
                continue
            Hi = abs(x-cx) + abs(y-cy) + h
            if H == -1:
                H = Hi
                continue
            if Hi != H:
                ok = False
                break
        if not ok:
            continue
        for x, y, h in P:
            if h != max(H-abs(cx-x)-abs(cy-y), 0):
                ok = False
        if ok:
            print(cx, cy, H)
            break
    if ok:
        break
### BUGGY CODE ###

import collections
from math import gcd
def main():
    n=int(input())
    c=collections.Counter()
    mod=10**9+7
    for _ in range(n):
        a,b=map(int,input().split())
        g=abs(gcd(a,b))
        if g==0:
            g=1
        a//=g
        b//=g
        c[(a,b)]+=1
    ans=1
    s=set()
    for i,j in c:
        if (i,j)==(0,0):
            continue
        if (i,j) not in s:
            s.add((i,j))
            s.add((-i,-j))
            s.add((-j,i))
            s.add((j,-i))
            ans*=(pow(2,c[(i,j)]+c[(-i,-j)],mod)+pow(2,c[(j,-i)]+c[(-j,i)],mod)-1)%mod
    print((ans-1+c[(0,0)])%mod)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import collections
from math import gcd
import sys
input=sys.stdin.readline
def main():
    n=int(input())
    c=collections.Counter()
    mod=10**9+7
    for _ in range(n):
        a,b=map(int,input().split())
        g=abs(gcd(a,b))
        if g==0:
            g=1
        a//=g
        b//=g
        c[(a,b)]+=1
    ans=1
    s=set()
    for i,j in c:
        if (i,j)==(0,0):
            continue
        if (i,j) not in s:
            s.add((i,j))
            s.add((-i,-j))
            s.add((-j,i))
            s.add((j,-i))
            ans*=(pow(2,c[(i,j)]+c[(-i,-j)],mod)+pow(2,c[(j,-i)]+c[(-j,i)],mod)-1)%mod
    print((ans-1+c[(0,0)])%mod)

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

n = int(input())
h_list = list(map(int,input().split()))
count = {}
for i in range(len(h_list)-1):
    if h_list[i] >= h_list[i+1]:
        count[i] = 0
        j = i
        while j < n-1:
            if h_list[j] >= h_list[j+1]:
                count[i] += 1
                j += 1

            else:
                break
if count:
    ls = sorted(count.items(), key=lambda x: x[1])
    print(ls[-1][1])
else:
    print(0)

### FIXED CODE ###

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

count = 0
bestcount = count
for i in range(n-1):
    if h_list[i] >= h_list[i+1]:
        count += 1
    else:
        bestcount = max(count,bestcount)
        count= 0
print(max(count,bestcount))
### BUGGY CODE ###

K, S = map(int, input().split())

cnt = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i + j + k == S:
                cnt += 1

print(cnt)


### FIXED CODE ###

K, S = map(int, input().split())

cnt = 0
for i in range(K+1):
    for j in range(K+1):
        if 0 <= S - (i + j) <= K:
            cnt += 1

print(cnt)
### BUGGY CODE ###

import sys
import itertools
ans=0
N=int(sys.stdin.readline())
S=sys.stdin.readline()

for i in itertools.combinations(range(N),3):
  if (i[0]+i[2])/2 ==i[1]:
    continue
  L=[S[i[0]],S[i[1]],S[i[2]]]
  if len(set(L))!=3:
    continue
  ans+=1
  
print(ans)    

### FIXED CODE ###

N=int(input())
S=input()

r_cnt=S.count('R')
g_cnt=S.count('G')
b_cnt=S.count('B')

ans=r_cnt*g_cnt*b_cnt

for i in range(N):
  for d in range(N):
    j=i+d
    k=j+d
    if k>=N:break
#等号がないと範囲外参照になる、0-indexだからk=S[N]は無い      
    if S[i]!=S[j] and S[i]!=S[k] and S[k]!=S[j]:
      ans-=1
      
print(ans)
### BUGGY CODE ###

import sys

# ?????§???????±??????????
def get_max(data):
    now_max = None
    for i in range(0, len(data)-1):
        start_val = data[i]
        for j in range(i+1, len(data)):
            if now_max is None or data[j]-start_val > now_max:
                now_max = data[j] - start_val
    return now_max

# ??\???????????????????????????
data = []
line_num = int(sys.stdin.readline().rstrip())
while True:
    input_data = sys.stdin.readline()
    if not input_data:
        break
    input_data = int(input_data.rstrip())
    data.append(input_data)

result = get_max(data)
print(result)

### FIXED CODE ###

import sys

line_num = int(sys.stdin.readline().rstrip())
maxv = -2000000000
minv = int(sys.stdin.readline().rstrip())

for i in range(1, line_num):
    rt = int(sys.stdin.readline())
    if rt - minv > maxv:
        maxv = rt - minv
    if rt < minv:
        minv = rt

print(maxv)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# D-Grid and Integers

from collections import defaultdict

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
RowIdx = set()
ColIdx = set()
Grid = defaultdict(list)
RowGrid = defaultdict(list)
ColGrid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	RowGrid[r].append(c)
	ColGrid[c].append(r)
	Grid[(r, c)] = a
	RowIdx.add(r)
	ColIdx.add(c)	

fresh = 1
while(fresh == 1):
	fresh = 0
	for row in RowIdx:
		if (len(RowGrid[row]) == 1):
			continue
		TempRow = RowGrid[row].copy()
		TempColGrid = ColGrid.copy()
		for pointer in TempRow:
			TempCol = TempRow.copy()
			TempCol.remove(pointer)
			for pair in TempCol:
				dif = Grid[(row, pointer)] - Grid[(row, pair)]
				ObjCol = TempColGrid[pointer].copy()
				ObjCol.remove(row)
				for obj in ObjCol:
					val = Grid[(obj, pointer)]- dif 
					if (val < 0):
						print("No")
						exit()
					if ((obj, pair) in Grid):
						if (val != Grid[(obj, pair)]):
							print("No");
							exit()
					else:
						Grid[(obj, pair)] = val
						RowGrid[obj].append(pair)
						ColGrid[pair].append(obj)
						fresh = 1
print("Yes")

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
VectorSet = set() 
Grid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	Grid[("R", r)].append((("C", c), a))
	Grid[("C", c)].append((("R", r), a))
	VectorSet.add(("R", r))
	VectorSet.add(("C", c))

def iteration(vector):
	VectorSet.discard(vector)
	for (v, a) in Grid[vector]:
		temp = a - VectorCover[vector]
		if (v in VectorCover):
			if(temp != VectorCover[v]):
				print("No")
				exit()
		else:
			VectorCover[v] = temp
			iteration(v) 

while(len(VectorSet) != 0):
	vector = VectorSet.pop()
	VectorCover = dict() 
	VectorCover[vector] = 0
	iteration(vector)
	minR = min(a for (p, a) in VectorCover.items() if (p[0] == "R"))
	minC = min(a for (p, a) in VectorCover.items() if (p[0] == "C"))
	if (minR + minC < 0):
		print("No")
		exit()

print("Yes")
### BUGGY CODE ###

import sys
import math
import heapq
import fractions

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()
a = LI()
lcmall = a[0]
for i in range(1, N):
    lcmall = lcmall * a[i] // fractions.gcd(lcmall, a[i])
# print(lcmall%DVSR)

# N=II()
# INL = LI()
# gcdall=INL[0]
# lcmall=INL[0]
# for i in INL:
#     gcdall = gcd(gcdall, i)%DVSR
#     lcmall = (((lcmall*i)%DVSR)*INV(gcd(lcmall, i)))%DVSR
# # print(lcmall)

res = 0
for i in a:
    # print(((lcmall*INV(i))%DVSR * i)%DVSR)
    res += (lcmall*INV(i))%DVSR
print(res%DVSR)


### FIXED CODE ###

import sys
import math
import heapq
import fractions

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()

primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]

INL=LI()
LCM={}
for i in INL:
    for p in primes:
        cnt = 0
        while i%p == 0:
            i //= p
            cnt += 1
        if not p in LCM: LCM[p] = 0
        LCM[p] = max(LCM[p], cnt)
    if i != 1:
        if not i in LCM: LCM[i] = 0
        LCM[i] = max(LCM[i], 1)

res = 0
LCMMOD = 1
for p, cnt in LCM.items():
    LCMMOD *= (p**cnt)
    LCMMOD %= DVSR

for i in INL:
    res += LCMMOD*INV(i)%DVSR

print(res%DVSR)
### BUGGY CODE ###

import bisect

n = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))

cnt = 0


for b in B :
    a_cnt = len(A[:bisect.bisect_left(A,b)])
    c_cnt = len(C[bisect.bisect_right(C,b):])
    cnt += a_cnt * c_cnt
    
print(cnt)

### FIXED CODE ###

import bisect

n = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))

cnt = 0


for j in range(n) :
    a = bisect.bisect_left(A,B[j])
    c = bisect.bisect_right(C,B[j])
    cnt += a * (n-c)
    
print(cnt)
### BUGGY CODE ###

from collections import deque

N,K,C=map(int,input().split())
S=input()

def check(S0):
    count=0
    index=0
    while count<K and index<N:
        if S0[index]=='o':
            count+=1
            index+=(C+1)
        else:
            index+=1
    if count==K:
        return 1
    return 0

if check(S)==0:
    print()
else:
    for i in range(N):
        if S[i]=='o':
            S0=S[:i]+'x'+S[i+1:]
            if check(S0)==0:
                print(i+1)

### FIXED CODE ###

N,K,C=map(int,input().split())
S=input()

def check0(S0):
    count=0
    index=0
    out=[0]*K
    while count<K and index<N:
        if S0[index]=='o':
            out[count]=index
            count+=1
            index+=(C+1)
        else:
            index+=1
    if count==K:
        return 1,out
    return 0,out

def checkend(S0):
    count=0
    index=N-1
    out=[0]*K
    while count<K and index>=0:
        if S0[index]=='o':
            out[K-1-count]=index
            count+=1
            index-=(C+1)
        else:
            index-=1
    if count==K:
        return 1,out
    return 0,out



flag0,out0=check0(S)
flagend,outend=checkend(S)
if flag0==1:
    for i in range(K):
        if out0[i]==outend[i]:
            print(out0[i]+1)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000000)


N, M, K = map(int, input().split())
mod = 998244353

DP = [[-1] * (K+1) for _ in range(N+1)]


def dpdp(n, k):
    if DP[n][k] != -1:
        return DP[n][k]
    if n-1 <= k:
        DP[n][k] = pow(M, n-1, mod)
        return pow(M, n-1, mod)
    if k == 0:
        DP[n][k] = pow(M-1, n-1, mod)
        return pow(M-1, n-1, mod)
    if n == 1:
        DP[n][k] = M % mod
        return M % mod

    return (dpdp(n-1, k-1) % mod + (M-1) * dpdp(n-1, k) % mod) % mod


print(dpdp(N, K) * M % mod)


### FIXED CODE ###

N, M, K = map(int, input().split())
mod = 998244353
ans = 0
nCi = [1]

for i in range(1, N+1):
    nCi.append(nCi[i-1]*(N-i) * pow(i, mod-2, mod) % mod)


for i in range(K+1):
    ans += M * pow(M - 1, N-1-i, mod) * nCi[i]
    ans %= mod

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

import numpy as np
room, route_count = map(int,input().split())
route = np.array([list(map(int,input().split())) for _ in range(route_count)])
 
object_nums = [1]
ans = np.array([0]*(room-1))
 
def mem_ans(ans, object_num, next_nums):
    mask_array = np.zeros(room-1, dtype=bool)
    mask_array[next_nums-2] = True
    ans[(ans==0) & mask_array] = object_num
    return ans
 
for object_num in object_nums:
    object_num_mask = np.any(route==object_num, axis=1)
    object_rows = route[object_num_mask]
    route = route[~object_num_mask]
    next_nums = object_rows[object_rows!=object_num]
    if next_nums is not None:
        ans = mem_ans(ans, object_num, next_nums)
        object_nums.extend(next_nums)
    else:
        break
 
if 0 in set(ans):
  print('No')
else:
  print('Yes')
  for i in ans:
    print(i)

### FIXED CODE ###

import networkx as nx
room, route_count = map(int,input().split())
route = [list(map(int,input().split())) for _ in range(route_count)]

G = nx.Graph()
G.add_nodes_from(range(1,room+1))
G.add_edges_from(route)
pre = nx.predecessor(G, 1)

print('Yes')
for i in range(2,room+1):
  print(pre[i][0])
### BUGGY CODE ###

a, b, k = (int(i) for i in input().split())  

for i in range(a, b + 1):
  if i < a + k or i > b - k:
    print(i)

### FIXED CODE ###

a, b, k = (int(i) for i in input().split())  

for i in range(a, min(a + k, b + 1)):
    print(i)
    
for i in range(max(a + k, b - k + 1), b + 1):
    print(i)
### BUGGY CODE ###

N, W = map(int, input().split())
I = [tuple(map(int, input().split())) for _ in range(N)]
w0 = I[0][0]

dp = [[[0 for k in range(N * 3 + 1)] for j in range(N + 1)] for i in range(N + 1)]

for i in range(N):
    w, v = I[i]
    for j in range(N):
        for k in range(3 * N + 1):
            if k - (w - w0) >= 0:
                dp[i + 1][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k - (w - w0)] + v)
            else:
                dp[i + 1][j + 1][k] = dp[i][j + 1][k]

res = 0


for j in range(N + 1):
    for k in range(3 * N + 1):
        if w0 * j + k <= W:
            res = max(res, dp[N][j][k])

print(res)

### FIXED CODE ###

N,W = map(int,input().split())
item = [list(map(int,input().split())) for i in range(N)]
w = item[0][0]

dp = [[[0 for k in range(3*N+1)] for j in range(N+1)] for i in range(N+1)]

for i in range(1,N+1):
    for j in range(1,i+1):
        for k in range(3*j+1):
            if item[i-1][0]-w <= k:
                dp[i][j][k] = max(dp[i-1][j-1][k-(item[i-1][0]-w)]+item[i-1][1],dp[i-1][j][k])
            else:
                dp[i][j][k] = dp[i-1][j][k]
                
ans = 0
for j in range(N+1):
    for k in range(3*N+1):
        if j*w+k <= W:
            ans = max(ans,dp[N][j][k])
            
print(ans)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,k = inpl()
value = [[0 for _ in range(m)] for i in range(n)]
for _ in range(k):
    a,b,c = inpl()
    value[a-1][b-1] = c
dp = [[[0 for _ in range(4)] for i in range(m)] for j in range(n)]
dp[0][0][1] = value[0][0]
for oy in range(n):
    for ox in range(m):
        for dy,dx in [(1,0),(0,1)]:
            ny = oy + dy
            nx = ox + dx
            if 0 <= ny < n and 0 <= nx < m:
                nva = value[ny][nx]
                if dx: #　横移動
                    for k in range(4):
                        dp[ny][nx][k] = max(dp[ny][nx][k], dp[oy][ox][k])
                        if k and nva:
                            dp[ny][nx][k] = max(dp[ny][nx][k], dp[oy][ox][k-1] + nva)
                else: #縦
                    dp[ny][nx][0] = max(dp[oy][ox])
                    if nva:
                        dp[ny][nx][1] = dp[ny][nx][0] + nva
print(max(dp[-1][-1]))

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,k = inpl()
value = [[0 for _ in range(m)] for i in range(n)]
for _ in range(k):
    a,b,c = inpl()
    value[a-1][b-1] = c
dp = [0] * (4*(m+1)*(n+1))
def ind(i,j,k): 
    return 4*(m+1)*i + 4*j + k
for i in range(n):
    for j in range(m):
        for k in range(3)[::-1]:
            dp[ind(i,j,k+1)] = max(dp[ind(i,j,k+1)], dp[ind(i,j,k)] + value[i][j])
        for k in range(4):
            dp[ind(i+1,j,0)] = max(dp[ind(i+1,j,0)], dp[ind(i,j,k)])
            dp[ind(i,j+1,k)] = max(dp[ind(i,j+1,k)], dp[ind(i,j,k)])
# print(dp)
mx = 0
for k in range(4):
    mx = max(mx, dp[ind(n-1,m-1,k)])
print(mx)
### BUGGY CODE ###


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

from collections import defaultdict

N, Q = map(int, input().split())
graph = [ [0 for _ in range(N)] for _ in range(N) ]
counts = [0] * N

def get_graph(N):
    tmp = [False] * N
    for i in range(N-1):
        a, b = map(int, input().split())

        # 1 - 3 - 2 みたいなケース
        if tmp[b-1]:
            graph[b-1][a-1] = 1
        else:
            graph[a-1][b-1] = 1
            tmp[b-1] = True

    return graph

graph = get_graph(N)
#print(graph)

# 指示はまとめる
dd = defaultdict(int)
for i in range(Q):
    p, x = map(int, input().split())
    dd[p] += x


def inc(p, x):
    # 0 index
    counts[p] += x

    for i in range(N):
        if graph[p][i] == 0:
            continue
        inc(i, x)

for P, X in dd.items():
    P -= 1
    inc(P, X)

print(*counts)


### FIXED CODE ###


import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion
n, q = map(int, input().split())

tree_index = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  tree_index[a].append(b) # a<bとは限らないため、双方向にする
  tree_index[b].append(a)

#print(tree_index)


ans = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x

def dfs(cur, par):
    for chl in tree_index[cur]:
      if chl == par: #parentとchildが等しい時はスキップ
        continue
      ans[chl] += ans[cur]
      dfs(chl, cur)
dfs(0, -1)
print(*ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

N = int(readline())
L = list(map(int,readline().split()))
L = sorted(L)

# 2本固定すると、もう一本として選べるのは、2本の和より長いものだけ
# これを二分探索で数える

#print(L)
import bisect
ans = 0
for i in range(N - 1):
  for j in range(i + 1,N):
    limit = L[i] + L[j]
    ng = len(L)
    ok = j
    while abs(ok - ng) > 1:
      mid = abs(ok + ng) // 2
      if L[mid] < limit:
        ok = mid
      else:
        ng = mid
#    print("i",i,"j",j,"L[i]",L[i],"L[j]",L[j],"limit",limit,ok - j)
    ans += ok - j
        
print(ans)

### FIXED CODE ###

import bisect
N=int(input())
L=sorted(list(map(int,input().split())))

ans=0
for i in range(N):
  for j in range(i+1,N):
    ans+=bisect.bisect_left(L,L[i]+L[j])-j-1

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

from itertools import combinations
 
x1 = int(input())
x2 = input()
RGB = {"R", "G", "B"}
 
print(sum([1 for i, rgb in zip(combinations(range(x1), 3), combinations(x2, 3)) if set(rgb) == RGB and (i[1] - i[0]) != (i[2] - i[1])]))

### FIXED CODE ###

from itertools import product

x1 = int(input())
x2 = input()

R_i = [i for i, x in enumerate(x2) if x == "R"]
G_i = [i for i, x in enumerate(x2) if x == "G"]
B_i = {i for i, x in enumerate(x2) if x == "B"}

R = len(R_i)
G = len(G_i)
B = len(B_i)

xs = map(sorted, product(R_i, G_i))

s = 0
for a in xs:
    k = a[1]*2 - a[0]  # 2j-i
    if k in B_i:
        s +=1
    i = a[0]*2 - a[1]  # 2j-k
    if i in B_i:
        s +=1
    j = (a[0] + a[1]) / 2
    if j.is_integer():
        j = int(j)
        if j in B_i:
            s +=1
print(R*G*B - s)
### BUGGY CODE ###

import numpy
n=input()
l=list(map(int, input().split()))
res=0
#print(f"le{len(l)}")
l.append(0)
l.reverse()
for i in range(len(l)): 
    #print(l[len(l)-1-i],numpy.cumsum(l)[len(l)-i-2])
    res+=l[len(l)-1-i]*numpy.cumsum(l)[len(l)-i-2]
    #print(f"{res}レス")
print(res%(10**9+7))

### FIXED CODE ###

import numpy
n=int(input())
l=list(map(int, input().split()))
res=0
mod=10**9+7
l.append(0)
l.reverse()
cum=numpy.cumsum(l)%mod
for i in range(n):
    res+=((l[n-i]%mod)*cum[n-i-1])%mod
print(res%mod)
### BUGGY CODE ###

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


### FIXED CODE ###

n = int(input())
nums = list(map(int, input().split()))
ans = 0
mod = 10**9 + 7
pres = [0]
for i in nums:
    pres.append(pres[-1] + i)
for i in range(n):
    temp = nums[i] * (pres[n] - pres[i+1])
    ans += temp
    ans %= mod
print(ans)