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

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

import numpy as np

r, c, k = map(int, input().split())
itm = [[0]*(c) for _ in range(r)]
for i in range(k):
    ri, ci, vi = map(int, input().split())
    itm[ri-1][ci-1] = vi

dp = np.zeros((3005, 3005, 4), dtype=np.int64)

for i in range(r):
    for j in range(c):
        nowv = itm[i][j]
        dp[i][j][3] = max(dp[i][j][3], dp[i][j][2] + nowv)
        dp[i][j][2] = max(dp[i][j][2], dp[i][j][1] + nowv)
        dp[i][j][1] = max(dp[i][j][1], dp[i][j][0] + nowv)

        dp[i+1][j][0] = max(dp[i+1][j][0], max(dp[i][j]))
        dp[i][j+1][0] = max(dp[i][j+1][0], dp[i][j][0])
        dp[i][j+1][1] = max(dp[i][j+1][1], dp[i][j][1])
        dp[i][j+1][2] = max(dp[i][j+1][2], dp[i][j][2])
        dp[i][j+1][3] = max(dp[i][j+1][2], dp[i][j][3])

print(max(dp[r-1][c-1]))


### FIXED CODE ###

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

r, c, k = map(int, input().split())
itm = [[0]*(c) for _ in range(r)]
for i in range(k):
    ri, ci, vi = map(int, input().split())
    itm[ri-1][ci-1] = vi

dp0 = [[0]*4 for c_ in range(3005)]
dp1 = [[0]*4 for c_ in range(3005)]

for i in range(r):
    for j in range(c):
        nowv = itm[i][j]
        dp0[j][3] = max(dp0[j][3], dp0[j][2] + nowv)
        dp0[j][2] = max(dp0[j][2], dp0[j][1] + nowv)
        dp0[j][1] = max(dp0[j][1], dp0[j][0] + nowv)

        dp0[j+1][0] = max(dp0[j+1][0], dp0[j][0])
        dp0[j+1][1] = max(dp0[j+1][1], dp0[j][1])
        dp0[j+1][2] = max(dp0[j+1][2], dp0[j][2])
        dp0[j+1][3] = max(dp0[j+1][3], dp0[j][3])

        dp1[j][0] = max(dp1[j][0], max(dp0[j]))
    dp0 = dp1.copy()

print(max(dp1[c-1]))
### BUGGY CODE ###


import bisect

def solve(N,A,B,C):

    # A=['3', '14', '159', '2', '6', '53']
    # B=['58', '9', '79', '323', '84', '6']
    # C=['2643', '383', '2', '79', '50', '288']
    A,B,C=list(map(int, A)),list(map(int, B)),list(map(int, C))
    A=sorted(A)
    B=sorted(B)
    C=sorted(C)
    # print(A)
    # print(B)
    # print(C)
    D = [0]*N
    E = [0]*N
    for i in range(N):
        a = A[i]
        # print(N-bisect.bisect_right(B,a))
        D[i]= N-bisect.bisect_right(B,a)
        #bはaより大きい数字が何個あるか分かれば良い
        #cはbの
    # print(D)

    for i in range(N):
        b = B[i]
        E[i] = N-bisect.bisect_right(C,b)
    
    # print(E)
    answer = 0
    for i in range(N):
        d=N-D[i]
        answer+=sum(E[d:])

    print(answer)

    
 
 
def main():
    N = int(input())
    A=input().rstrip().split()
    B=input().rstrip().split()
    C=input().rstrip().split()
    solve(N,A,B,C)

 
 
if __name__ == '__main__':
    main()

### FIXED CODE ###


import bisect

def solve(N,A,B,C):

    # A=['3', '14', '159', '2', '6', '53']
    # B=['58', '9', '79', '323', '84', '6']
    # C=['2643', '383', '2', '79', '50', '288']
    A,B,C=list(map(int, A)),list(map(int, B)),list(map(int, C))
    A=sorted(A)
    B=sorted(B)
    C=sorted(C)
    # print(A)
    # print(B)
    # print(C)
    D = [0]*N
    # E = [0]*N
    # for i in range(N):
    #     a = A[i]
    #     # print(N-bisect.bisect_right(B,a))
    #     D[i]= N-bisect.bisect_right(B,a)
    #     #bはaより大きい数字が何個あるか分かれば良い
    #     #cはbの
    # # print(D)

    for i in range(N):
        b = B[i]
        D[i]=bisect.bisect_left(A,b)*(N-bisect.bisect_right(C,b))
        # print(b,'より小さいのは',bisect.bisect_left(A,b))
        # print(b,'より大きいのは',N-bisect.bisect_right(C,b))
    print(sum(D))
    # print(E)
    # answer = 0
    # for i in range(N):
    #     d=N-D[i]
    #     answer+=sum(E[d:])

    # print(answer)

    
 
 
def main():
    N = int(input())
    # A,B,C=0,0,0
    A=input().rstrip().split()
    B=input().rstrip().split()
    C=input().rstrip().split()
    solve(N,A,B,C)

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

#DAGの最長有向パスをトポロジカルソートで解く
N,M=map(int,input().split(' '))
x=[0]*M
y=[0]*M
z=[0]*(N+1)
for i in range(M):
    x[i],y[i]=map(int,input().split(' '))
n=[i for i in range(1,N+1)]
while len(n)>0:
    for i in n:
        if i not in y:
            n.remove(i)
            for j in range(M):
                if i==x[j]:
                    if z[y[j]]<=z[x[j]]:
                        z[y[j]]=z[x[j]]+1
                    x[j],y[j]=0,0
            break
print(max(z))

### FIXED CODE ###

from collections import defaultdict, deque

N, M = map(int, input().split())
es = [[int(x) for x in input().split()] for _ in range(M)]

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1
length=defaultdict(int)

q = deque(set(i for i in range(1,N+1))-set(ins.keys()))
length=defaultdict(int)
while q:
    v1 = q.popleft()
    for v2 in outs[v1]:
        ins[v2] -= 1
        if length[v2]<=length[v1]:
            length[v2]=length[v1]+1
        if ins[v2] == 0:
            q.append(v2)

print(max(length.values()))
### BUGGY CODE ###

from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, a, b, w):
        self.graph[a].append((b, w))


class Dijkstra(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[s] = 0

        self.Q = []
        heappush(self.Q, (self.dist[s], s))
        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, w in self.g[u]:
                alt = dist_u + w
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    heappush(self.Q, (alt, v))

    def s_d(self, goal):
        return self.dist[goal]


xs, ys, xg, yg = list(map(int, input().split()))
xyr = []
xyr.append([xs, ys, 0])
N = int(input())

for i in range(N):
    xyr.append(list(map(int, input().split())))
xyr.append([xg, yg, 0])

g_a = Graph()
for i in range(N + 1):
    for j in range(i + 1, N + 2):
        R = ((xyr[i][0] - xyr[j][0]) * (xyr[i][0] - xyr[j][0]) + (xyr[i][1] - xyr[j][1]) * (xyr[i][1] - xyr[j][1]))
        R = R ** 0.5
        if R > xyr[i][2] + xyr[j][2]:
            r = R - xyr[i][2] - xyr[j][2]
        else:
            r = 0
        g_a.add_edge(i, j, r)
        g_a.add_edge(j, i, r)

d_a = Dijkstra(g_a, 0)
print(d_a.s_d(N + 1))

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, a, b, w):
        self.graph[a].append((b, w))


class Dijkstra(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[s] = 0

        self.Q = []
        heappush(self.Q, (self.dist[s], s))
        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, w in self.g[u]:
                alt = dist_u + w
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    heappush(self.Q, (alt, v))

    def s_d(self, goal):
        return self.dist[goal]


xs, ys, xg, yg = list(map(int, input().split()))
xyr = []
xyr.append([xs, ys, 0])
N = int(input())

for i in range(N):
    xyr.append(list(map(int, input().split())))
xyr.append([xg, yg, 0])

g_a = Graph()
for i in range(N + 1):
    for j in range(i + 1, N + 2):
        R = ((xyr[i][0] - xyr[j][0]) * (xyr[i][0] - xyr[j][0]) + (xyr[i][1] - xyr[j][1]) * (xyr[i][1] - xyr[j][1]))
        R = R ** 0.5
        if R > xyr[i][2] + xyr[j][2]:
            r = R - xyr[i][2] - xyr[j][2]
        else:
            r = 0
        g_a.add_edge(i, j, r)
        g_a.add_edge(j, i, r)

d_a = Dijkstra(g_a, 0)
print(d_a.s_d(N + 1))
### BUGGY CODE ###

MOD = 1000000007
n = int(input())
aas = list(map(int, input().split()))
KET = 60
arr_0 = [0]*KET
arr_1 = [0]*KET
for i in aas:
    bits = format(i,'060b')
    for j in reversed(range(KET)):
        if bits[j] == '0':
            arr_0[KET-j-1] += 1
        else:
            arr_1[KET-j-1] += 1
res = 0
for i in range(KET):
    res += (arr_0[i]%MOD * arr_1[i]%MOD)%MOD * pow(2,i,MOD)
    res %= MOD
print(res)

### FIXED CODE ###

MOD = 1000000007
n = int(input())
aas = list(map(int, input().split()))
KET = 60
arr_0 = [0]*KET
arr_1 = [0]*KET
for i in aas:
    bits = format(i,'060b')
    for j in reversed(range(KET)):
        if bits[j] == '0':
            arr_0[KET-j-1] += 1
        else:
            arr_1[KET-j-1] += 1
res = 0
for i in range(KET):
    res += (arr_0[i]%MOD * arr_1[i]%MOD)%MOD * pow(2,i,MOD)
    res %= MOD
print(res)
### BUGGY CODE ###

h,w,k = map(int, input().split())
sx,sy,gx,gy = map(lambda x: int(x)-1, input().split())
board = [list(map(lambda x: int(x=="."), input())) for i in range(h)]
inf = 1<<30
DP = [[inf for j in range(w)] for i in range(h)]
DP[sx][sy] = 0

from collections import deque
que = deque([(sx,sy)])

dxdy = [(0,1),(1,0),(0,-1),(-1,0)]
while que:
    x,y = que.popleft()
    for dx,dy in dxdy:
        nx,ny = x,y
        for i in range(k):
            nx += dx
            ny += dy
            if not(0<=nx<h and 0<=ny<w and board[nx][ny] and DP[nx][ny] >= DP[x][y]+1):
                break
            DP[nx][ny] = min(DP[nx][ny], DP[x][y]+1)
            que.append((nx,ny))
ans = DP[gx][gy]
if ans == inf:
    ans = -1
print(ans)


### FIXED CODE ###

h,w,k = map(int, input().split())
sx,sy,gx,gy = map(lambda x: int(x)-1, input().split())
board = [list(map(lambda x: int(x=="."), input())) for i in range(h)]
inf = 1<<30
DP = [[inf for j in range(w)] for i in range(h)]
DP[sx][sy] = 0

from collections import deque
que = deque([(sx,sy)])

dxdy = [(0,1),(1,0),(0,-1),(-1,0)]
while que:
    x,y = que.popleft()
    for dx,dy in dxdy:
        nx,ny = x,y
        for i in range(k):
            nx += dx
            ny += dy
            if not(0<=nx<h and 0<=ny<w and board[nx][ny] and DP[nx][ny] >= DP[x][y]+1):
                break
            # コストが変わらない場合は無視か...
            if DP[nx][ny] == DP[x][y]+1:
                continue
            DP[nx][ny] = DP[x][y]+1
            que.append((nx,ny))
ans = DP[gx][gy]
if ans == inf:
    ans = -1
print(ans)
### BUGGY CODE ###



N=int(input())

S_list = []
S_count = []
max = 1
for i in range(N):
    s = input()
    temp_list = []
    temp_list.append(s)
    #if s in S_list:
    if not set(S_list).isdisjoint(set(temp_list)):   
        index = S_list.index(s)
        #S_count.append(S_count[index]+1)
        S_count[index] += 1
        if max < S_count[index]:
            max = S_count[index]
    else:
        S_list.append(s)
        S_count.append(1)
        #if max < S_count[i]:
        #    max = S_count[i]
     
#print(S_list)
#print(S_count)
#print(max)
S_max = []
for j in range(len(S_list)):
    if S_count[j] == max:
        S_max.append(S_list[j])

S_max.sort()
for k in range(len(S_max)):
    print(S_max[k])

### FIXED CODE ###



N=int(input())

S_list = []
S_count = []
max = 1
temp_list = []
#for i in range(N):
#    s = input()
#    temp_list.append(s)
S_dict = {}
for i in range(N):
    s = input()
    if s in S_dict.keys():
        S_dict[s] += 1
        if max < S_dict[s]:
            max = S_dict[s]
    else:
        S_dict[s] = 1
    
     
#print(S_list)
#print(S_count)
#print(max)
S_max = []
for j in S_dict:
    if S_dict[j] == max:
        S_max.append(j)

S_max.sort()
for k in range(len(S_max)):
    print(S_max[k])
### BUGGY CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]

ans=0
ab.sort()
m=bin(k)
# print(m)
klst=[m]
for i in range(2,len(m)):
    if m[i]=="1":
        klst.append(m[:i]+"0"+"1"*(len(m)-i-1))

# print(klst)
for i in klst:
    tmp=0
    for j in range(n):
        a,b=ab[j]
        m=bin(a)
        if int(i,0)>=a:
            for l in range(min(len(m),len(i))):
                if i[-1-l]=="0" and m[-1-l]=="1":
                    break
            else:
                tmp+=b
    ans=max(ans,tmp)
print(ans)

### FIXED CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]

ans=0
ab.sort()
m=bin(k)
# print(m)
klst=[m]
for i in range(2,len(m)):
    if m[i]=="1":
        klst.append(m[:i]+"0"+"1"*(len(m)-i-1))

# print(klst)
for i in klst:
    tmp=0
    for j in range(n):
        a,b=ab[j]
        if a|int(i,0)==int(i,0):
            tmp+=b
    ans=max(ans,tmp)
print(ans)
### BUGGY CODE ###

from itertools import combinations
N, X, Y = map(int, input().split())

result = []
for i, j in combinations(range(1, N+1), 2):
    jy = abs(Y-j)
    ix = abs(X-i)
    if (j-i)<=(jy+ix+1):
        result.append(j-i)
    else:
        result.append(jy+ix+1)
print(N)
for i in range(1, N-1):
    print(result.count(i+1))

### FIXED CODE ###

from itertools import combinations
N, X, Y = map(int, input().split())

result = [0]*N
for i, j in combinations(range(1, N+1), 2):
    mins = min([j-i, abs(Y-j)+abs(X-i)+1])
    result[mins] += 1
    
for i in range(1, N):
    print(result[i])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
    b.append([a[i],i])
b.sort()
b = b[::-1]
#print(b)
dp = [[0]* (n+1) for i in range(n+1)]
cnt = 0
for i,j in b:
    for k in range(cnt+1):
        dp[cnt-k][k+1] = max(dp[cnt-k][k] + abs(n-1-j-k)*i,dp[cnt-k][k+1])
        dp[cnt-k+1][k] = max(dp[cnt-k][k] + abs(j-(cnt-k))*i,dp[cnt-k+1][k])
    cnt+=1
ans = 0
for k in range(n):
    ans = max(ans,dp[n+1-k-1][k])
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
    b.append([a[i],i])
b.sort()
b = b[::-1]
#print(b)
dp = [[0]* (n+1) for i in range(n+1)]
cnt = 0
for i,j in b:
    for k in range(cnt+1):
        dp[cnt-k][k+1] = max(dp[cnt-k][k] + abs(n-1-j-k)*i,dp[cnt-k][k+1])
        dp[cnt-k+1][k] = max(dp[cnt-k][k] + abs(j-(cnt-k))*i,dp[cnt-k+1][k])
    cnt+=1
ans = 0
for k in range(n):
    ans = max(ans,dp[n+1-k-1][k])
print(ans)
### BUGGY CODE ###

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


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


def main():
    from collections import defaultdict
    n, m = input_int_list()
    A = sorted(input_int_list())
    d = defaultdict(int)
    for a in A:
        d[a] += 1
    for _ in range(m):
        b, c = input_int_list()
        for key in sorted(d.keys()):
            if key >= c or b == 0:
                break
            else:
                if d[key] >= b:
                    tmp = b
                    d[key] -= tmp
                    b -= tmp
                    d[c] += tmp
                else:
                    d[c] += d[key]
                    b -= d[key]
                    d[key] = 0
    ans = 0
    for k, v in d.items():
        ans += k * v

    print(ans)

    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
# sys.setrecursionlimit(100000)
import heapq


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


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


def main():
    from collections import Counter
    # 計算量 O(n*log_n + m*log_m)

    # 入力
    n, m = input_int_list()
    hq = list(Counter(input_int_list()).items())  # O(n)
    # 最小値管理にPriorityQueueを使う

    heapq.heapify(hq)  # O(n*log_n)

    queries = []
    for _ in range(m):
        queries.append(input_int_list())

    queries.sort(key=lambda x: x[1], reverse=True)  # O(m * log_m)

    # cが大きい数字から処理したほうが効率的になる
    for b, c in queries:
        while b > 0:
            k, v = heapq.heappop(hq)
            if k >= c:
                heapq.heappush(hq, (k, v))
                break
            else:
                if v == b:
                    heapq.heappush(hq, (c, b))
                    b = 0
                elif v > b:
                    heapq.heappush(hq, (c, b))
                    heapq.heappush(hq, (k, v - b))
                    b = 0
                elif b > v:
                    heapq.heappush(hq, (c, v))
                    b -= v
    ans = 0
    for k, v in hq:
        ans += k * v

    print(ans)

    return


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

n,x,m = map(int, input().split()) 
ans = 0
x_list = []

for _ in range(n):
    x_list.append(x)
    ans += x
    x = x**2 % m
    if x == 0:
        ans = sum(x_list)
        break
    if x == 1:
        ans = sum(x_list) + (n-len(x_list))
        break
    if x_list.count(x) == 1:
        after_list = x_list[x_list.index(x):(len(x_list))]
        if x_list.index(x) == 0:
            if (n // len(x_list)) == 0:
                ans = sum(x_list) * (n // len(x_list))
            else:
                ans = sum(x_list) * (n // len(x_list)) + sum(x_list[0:((n % len(x_list)))])
        else:
            if (n-x_list.index(x)) % len(after_list) == 0:
                ans = sum(after_list) * ((n-x_list.index(x)) // len(after_list)) + sum(x_list[0:(x_list.index(x))])
            else:
                ans = sum(after_list) * ((n-x_list.index(x)) // len(after_list)) + sum(after_list[0:(((n-x_list.index(x)) % len(after_list)))]) + sum(x_list[0:(x_list.index(x))])
        break

print(ans)

### FIXED CODE ###

N, X, M = map(int, input().split())
 
def next_f(a):
    return a * a % M
 
visited = [None] * M
sum_at_visit = [None] * M
loop_done = False
 
time = 1
ans = 0
x = X
while time <= N:
    if not loop_done and visited[x] is not None:
        # found cycle                                                                                                                                         
        loop_len = time - visited[x]
        loop_sum = ans + x - sum_at_visit[x]
        loops = (N-loop_len-time) // loop_len
        time += loop_len * loops
        ans += loop_sum * loops
        loop_done = True
    ans += x
    visited[x] = time
    sum_at_visit[x] = ans
    time += 1
    x = next_f(x)
print(ans)
### BUGGY CODE ###

# sys.stdin.readline()
import sys
input = sys.stdin.readline

n,k = map(int,input().split())
l=list(map(int,input().split()))
l2 = [(1+i)/2 for i in l]
kitai=0
for idx in range(n)[:n - k + 1]:
    summary=sum(l2[idx:idx + k])
    if (kitai < summary):
       kitai = summary
print(kitai)

### FIXED CODE ###

# sys.stdin.readline()
import sys
input = sys.stdin.readline
def main():
    n,k = map(int,input().split())
    l=list(map(int,input().split()))
    l2 = [(1+i)/2 for i in l]
    kitai=sum(l2[0:k])
    tmp = kitai
    for idx in range(n)[:n - k]:
        tmp -= l2[idx]
        tmp += l2[idx+k]
        if (kitai < tmp):
           kitai = tmp
    print(kitai)
main()
### BUGGY CODE ###

from cython import longlong
from itertools import combinations
N: longlong
A: longlong
N = int(input())
A = list(map(int, input().split()))
_sum = 0
k = 10**9+7
com = combinations(A,2)
for AA in com:
    _sum += (AA[0]*AA[1])%k
    _sum %= k
print(_sum)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 1000000007
S = 0
_sum = 0
for i in range(N):
    S += A[i]
    S %= mod
for i in range(N):
    S -= A[i]
    if S<0:
        S += mod
    _sum += A[i]*S
    _sum %= mod

print(_sum)
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
xs = sorted(x)
for i in range(n):
    xa = xs[::]
    xa.remove(x[i])
    print(xa[n // 2 - 1])

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
xs = sorted(x)
a = xs[n // 2 - 1]
b = xs[n // 2]
for i in x:
    if i <= a:
        print(b)
    else:
        print(a)
### BUGGY CODE ###

n = int(input())
lst = list(map(int, input().split()))
mult = 1

for i in lst:
    mult *= i

if mult > 10 ** 18:
    print(-1)
    exit()
else:
    print(mult)

### FIXED CODE ###

n = int(input())
lst = sorted(list(map(int, input().split())))
mult = 1

for i in lst:
    mult *= i
    if 10**18 < mult:
        print(-1)
        exit()
else:
    print(mult)
### BUGGY CODE ###

N = int(input())
x = list(map(int, input().split()))
s = 0

for i in range(N-1):
  for j in range(i+1,N):
    s = s + x[i]*x[j]
s = s % 1000000007

print(s)


### FIXED CODE ###

N = int(input())
x = list(map(int, input().split()))
s = sum(x) - x[0]
ans = 0

for i in range(N-1):
  ans = ans + x[i]*s
  s = s - x[i+1]
ans = ans % 1000000007
  
  
print(ans)
### BUGGY CODE ###

s = input()
invs = s[::-1]

MOD = 10 ** 9 + 7
 
dp = [[0]*13 for _ in range(len(s))]

if invs[0]=='?':
    for i in range(10): # 0~9までは1 10~12は0のまま
        dp[0][i] = 1
else:
    dp[0][int(invs[0])] = 1

mul = 10
for order in range(1,len(s)):
    for j in range(13):
        if invs[order] == '?':
            for number in range(10):
                dp[order][ (j+number * mul )%13  ]  += dp[order-1][j]%MOD
        else:
            number = int(invs[order])
            dp[order][(j+number * mul )%13 ]  += dp[order-1][j]%MOD
        dp[order][(j+number * mul )%13 ] %= MOD
    mul *= 10
    mul %= 13
print(dp[-1][5]%MOD)

### FIXED CODE ###

s = input()
invs = s[::-1]

MOD = 10 ** 9 + 7
 
dp = [[0]*13 for _ in range(len(s))]

if invs[0]=='?':
    for i in range(10): # 0~9までは1 10~12は0のまま
        dp[0][i] = 1
else:
    dp[0][int(invs[0])] = 1

mul = 10
for order in range(1,len(s)):
    for j in range(13):
        if invs[order] == '?':
            for number in range(10):
                dp[order][ (j+number * mul )%13  ]  += dp[order-1][j]%MOD
        else:
            number = int(invs[order])
            dp[order][(j+number * mul )%13 ]  += dp[order-1][j]%MOD
        dp[order][(j+number * mul )%13 ] %= MOD
    mul *= 10
    mul %= 13
print(dp[-1][5]%MOD)
### BUGGY CODE ###

import collections

def choose(c):
  return c * (c - 1) // 2

n = int(input())
a = [int(e) for e in input().split()]
cnt = collections.Counter(a)

for i in a:
  temp = cnt.copy()
  temp[i] -= 1
  print(sum([choose(c) for c in temp.values()]))
 

### FIXED CODE ###

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

import collections

cnt = collections.Counter(s)
ans = sum([(v * (v-1)) // 2 for k, v in cnt.items()])

for i in range(len(s)):
  print(ans - cnt[s[i]] + 1)