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

n = (int)(input())
s = [sorted(list(input())) for i in range(n)]
 
ans = 0
for i in range(n - 1):
  for j in range(i + 1, n):
    if s[i] == s[j]:
      ans += 1
print(ans)

### FIXED CODE ###

n = (int)(input())
s = sorted([sorted(list(input())) for i in range(n)])
 
ans = 0
temp = 1
for i in range(n - 1):
  if s[i] == s[i + 1]:
    temp += 1
  else:
    if temp != 1:
      ans += temp * (temp - 1) // 2
      temp = 1
else:
  if temp != 1:
    ans += temp * (temp - 1) // 2
    temp = 1
print(ans)
### BUGGY CODE ###

# abc 158
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

S = readline().strip().decode('utf-8')
Q = int(readline())

is_reversed = False

answer = S
for _ in range(Q):
    l = readline().decode('utf-8').split()
    if len(l) == 1:
        is_reversed = not is_reversed
    else:
        _, F, C = map(str, l)
        if F == "1":
            if is_reversed:
                answer = answer + C
            else:
                answer = C + answer
        else:
            if is_reversed:
                answer = C + answer
            else:
                answer = answer + C

if is_reversed:
    answer = "".join(list(reversed(answer)))
print(answer)

### FIXED CODE ###

# abc 158
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

S = readline().strip().decode('utf-8')
Q = int(readline())

is_reversed = False

import collections
answer = collections.deque(S)
for _ in range(Q):
    l = readline().decode('utf-8').split()
    if len(l) == 1:
        is_reversed = not is_reversed
    else:
        _, F, C = map(str, l)
        if F == "1":
            if is_reversed:
                answer.append(C)
            else:
                answer.appendleft(C)
        else:
            if is_reversed:
                answer.appendleft(C)
            else:
                answer.append(C)

if is_reversed:
    answer.reverse()
print("".join(answer))
### BUGGY CODE ###

h, w, d = map(int, input().split())
A = []
for _ in range(h):
    a = list(map(int, input().split()))
    A.append(a)

q = int(input())
LR = []
for _ in range(q):
    l, r = map(int, input().split())
    LR.append([l,r])

Inds = {x:[] for x in range(1, h*w+1)}
for j in range(h):
    for k in range(w):
        Inds[A[j][k]].append(j)
        Inds[A[j][k]].append(k)
# print(Inds)

for lr in LR:
    l = lr[0]
    r = lr[1]
    now = l
    ans = 0
    while now < r:
        # print('y is' + str(Inds[now-1][0]))
        # print('x is' + str(Inds[now-1][1]))
        ans += abs(Inds[now][0]-Inds[now+d][0]) + abs(Inds[now][1]-Inds[now+d][1])
        now += d
    print(ans)

### FIXED CODE ###

h, w, d = map(int, input().split())
A = []
for _ in range(h):
    a = list(map(int, input().split()))
    A.append(a)

q = int(input())
LR = []
for _ in range(q):
    l, r = map(int, input().split())
    LR.append([l,r])

Inds = {x:[] for x in range(1, h*w+1)}
for j in range(h):
    for k in range(w):
        Inds[A[j][k]].append(j)
        Inds[A[j][k]].append(k)

Dist = [-1 for _ in range(h*w+1)]
for i in range(1,h*w+1):
    if i <= d:
        Dist[i] = 0
    else:
        Dist[i] = Dist[i-d] + abs(Inds[i][0]-Inds[i-d][0]) + abs(Inds[i][1]-Inds[i-d][1])

for lr in LR:
    ans = Dist[lr[1]] - Dist[lr[0]]
    print(ans)
### BUGGY CODE ###


def main():

    MAX_VALUE = 10**6 + 5

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

    cnt = [0] * MAX_VALUE

    ans = 0

    for x in a:

        for i in range(x, MAX_VALUE, x):
            cnt[i] += 1

    for x in a:
        if cnt[x] == 1:
            ans += 1 

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###


def main():

    MAX_VALUE = 10**6 + 5

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

    cnt = [0] * MAX_VALUE

    ans = 0

    for x in a:

        if cnt[x] != 0:
            cnt[x] = 2
            continue

        for i in range(x, MAX_VALUE, x):
            cnt[i]+=1

    for x in a:
        if cnt[x] == 1:
            ans += 1 

    print(ans)


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

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

X = int(input())

ans = float('inf')


def bfs(s, g):
    Q = [[s, 0]]

    while Q:
        p = Q.pop(0)
        time = p[1]
        if p[0] == g:
            return time
        else:
            time += 1
            Q.append([p[0]+time, time])
            Q.append([p[0]-time, time])
            Q.append([p[0], time])


print(bfs(0, X))


### FIXED CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

X = int(input())

ans = float('inf')
pos = 0
time = 0
while pos < X:
    time += 1
    pos = (time)*(time+1)//2

diff = pos - X
print(time)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

S = input()
cnt = 0

s = S
while True:
    c1, c2 = 0, 0
    ls = len(s)
    for i in range(ls-1):
        if s[i] == "0" and s[i+1] == "1":
            c1 += 1
        elif s[i] == "1" and s[i+1] == "0":
            c2 += 1
    if c1 == 0 and c2 == 0:
        break
    elif c1 >= c2:
        s = s.replace("01", "")
        cnt += c1*2
    else:
        s = s.replace("10", "")
        cnt += c2*2

print(cnt)

### FIXED CODE ###

# -*- coding: utf-8 -*-

S = input()

# 最終出力は1のみか0のみとなるはず
# つまり、0と1の個数をカウントし、その差分から答えが求められる

c0 = S.count("0")
c1 = S.count("1")

fin = abs(c0-c1)    # 最後に残る0か1の個数
res = len(S) - fin

print(res)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)
ok = 10**12
ng = -1


def check(time):
    shugyou = 0
    for i in range(N):
        if A[i]*F[i] > time:
            shugyou += A[i] - (time//F[i])
    return shugyou <= K


while ok - ng > 1:
    mid = (ok + ng)//2
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)
ok = 10**12
ng = -1


def check(time):
    shugyou = 0
    for i in range(N):
        if A[i]*F[i] > time:
            shugyou += A[i] - (time//F[i])
    return shugyou <= K


while ok - ng > 1:
    mid = (ok + ng)//2
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)
### BUGGY CODE ###

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

tmpList=QsList[:]
tmpList.sort()

AnsList=QsList[:]
for i in QsList:
  tmp=int(QsList.index(i))+1
  a=int(tmpList.index(i))
  AnsList[a]=tmp
  
print(*AnsList)

### FIXED CODE ###

n=int(input())
a = list(map(int,input().split()))
enumerate(a,1)
b=sorted(range(len(a)), key=lambda k: a[k])
for i in range(len(b)):
  print(b[i]+1)
### BUGGY CODE ###

n = int(input())
list = []
for i in range(n):
    list += [int(input())]

max_ = max(list)
for i in range(n):
    a = list[i]
    if a == max_:
        del list[i]
        ans = max(list)
        print(ans)
        list.insert(i,a)
    else:
        print(max_)


### FIXED CODE ###

n = int(input())
list = []
for i in range(n):
    list += [int(input())]

max_ = max(list)
for i in range(n):
    a = list[i]
    if a == max_:
        del list[i]
        ans = max(list)
        print(ans)
        list.insert(i,a)
        if ans == max_:
            for j in range(n-i-1):
                print(max_)
            break
    else:
        print(max_)
### BUGGY CODE ###

# -*- codinf: utf-8 -*-
N = int(input())
A = list(map(int, input().split()))
ans = 1
for a in A:
  ans *= a
if ans > 10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

# -*- codinf: utf-8 -*-
N = int(input())
A = list(map(int, input().split()))
ans = 1

for a in A:
  if a == 0:
    print(0)
    exit()

for a in A:
  ans *= a
  if ans > 10**18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

import sys
inf = float('inf')

n, m = map(int, sys.stdin.readline().split())
graph = [None] * m
for i in range(m):
  a, b = map(int, sys.stdin.readline().split())
  res = 0
  for c in map(int, sys.stdin.readline().split()):
    res |= 1 << (c - 1)
    graph[i] = (a, res)


def main():
  dp = [[0] * (1 << n) for _ in range(m + 1)]
  for i in range(1, 1 << n):
    dp[0][i] = inf

  for i in range(m):
    for j in range(1 << n):
      dp[i+1][j] = min(dp[i][j ^ (j & graph[i][1])] + graph[i][0], dp[i][j])

  ans = dp[m][(1<<n)-1]
  print(-1 if ans == inf else ans)

if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys
inf = float('inf')

n, m = map(int, sys.stdin.readline().split())
graph = [None] * m
for i in range(m):
  a, b = map(int, sys.stdin.readline().split())
  res = 0
  for c in map(int, sys.stdin.readline().split()):
    res |= 1 << (c - 1)
    graph[i] = (a, res)


def main():
  dp = [[0] * (1 << n) for _ in range(m + 1)]
  for i in range(1, 1 << n):
    dp[0][i] = inf

  for i in range(m):
    for j in range(1 << n):
      dp[i+1][j] = min(dp[i][j ^ (j & graph[i][1])] + graph[i][0], dp[i][j])

  ans = dp[m][(1<<n)-1]
  print(-1 if ans == inf else ans)

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

#  --*-coding:utf-8-*--

def sumOfDigits(n):
    a = 0

    while n > 0:
        a += n%10
        n //= 10

    return a


def f(n):
    while n%2 == 0:
        n //= 2

    while n%5 == 0:
        n //= 5

    a = {}
    qs = set()
    x = sumOfDigits(n)

    for i in range(1, min(n, 10)):
        a[i] = i
        qs.add(i)

    while len(qs) > 0:
        q = qs.pop()
        q2 = q*10
        v = a[q]
        
        for i in range(0, min(x-v, 10)):
            q3 = (q2 + i)%n
            v2 = v + i

            if not q3 in a or v2 < a[q3]:
                a[q3] = v2
                qs.add(q3)
                    
            if q3 == 0 and v2 < x:
                x = v2

    return x


def test():
    assert f(6) == 3
    assert f(41) == 5
    assert f(79992) == 36


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


if __name__ == '__main__':
    main()


### FIXED CODE ###

#  --*-coding:utf-8-*--

import heapq

def sumOfDigits(n):
    a = 0

    while n > 0:
        a += n%10
        n //= 10

    return a


def f(n):
    while n%2 == 0:
        n //= 2

    while n%5 == 0:
        n //= 5

    vs = [None]*n
    qs = []
    x = sumOfDigits(n)

    for i in range(1, min(n, 10)):
        vs[i] = i
        heapq.heappush(qs, (i, i))

    while len(qs) > 0:
        _, q = heapq.heappop(qs)
        q2 = q*10
        v = vs[q]
        
        for i in range(0, min(x-v, 10)):
            q3 = (q2 + i)%n
            v2 = v + i
            v3 = vs[q3]

            if v3 == None or v2 < v3:
                vs[q3] = v2
                heapq.heappush(qs, (v2, q3))
                    
            if q3 == 0 and v2 < x:
                x = v2

    return x


def test():
    assert f(6) == 3
    assert f(41) == 5
    assert f(79992) == 36


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


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

n,m=map(int,input().split())
g=[set() for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  g[a].add(b)
  g[b].add(a)

start=0
spath={0}
path=[0]
todo=[0]
next=g[0].pop()
spath.add(next)
path.append(next)
while g[path[-1]]|spath!=spath:
  next=g[path[-1]].pop()
  if next not in spath:
    spath.add(next)
    path.append(next)
rpath=[0]
while g[rpath[-1]]|spath!=spath:
  next=g[rpath[-1]].pop()
  if next not in spath:
    spath.add(next)
    rpath.append(next)
rpath.reverse()
rpath.pop()
rpath+=path
rpath=[i+1 for i in rpath]
print(len(rpath))
print(*rpath,sep=' ')


### FIXED CODE ###

n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  x,y=x-1,y-1
  g[x].append(y)
  g[y].append(x)

path=[g[0][0]]
pathr=[0]
#path=[12,4]
setpath=set([0,g[0][0]])
while True:
  flg=True
  for nv in g[path[-1]]:
    if nv not in setpath:
      flg=False
      path.append(nv)
      setpath.add(nv)
      break
  for nv in g[pathr[-1]]:
    if nv not in setpath:
      flg=False
      pathr.append(nv)
      setpath.add(nv)
      break
  if flg:break

print(len(path)+len(pathr))
pathr.reverse()
pathr+=path
path=[str(pi+1) for pi in pathr]
print(' '.join(path))
#print(path)
#print(setpath)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0]*n
count = 0

for i in range(k):
  for j in range(n):
    for k in range(n):
      if a[k] >= abs(k-j):
        b[j] += 1
  a = b  
  b = [0]*n
  if a[0] == n:
    count += 1
  if count ==2 :
    break
  else:
    continue
  break
    
print(*a)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[0]*n
c=[0]*n
cnt=0
while cnt<min(k,101):
  cnt+=1
  for i in range(n):
    b[max(0,i-a[i])]+=1
    if i+a[i]<n-1:
      b[i+a[i]+1]-=1
    c[0]=b[0]
  for j in range(n-1):
    c[j+1]=c[j]+b[j+1]
  a=c
  b=[0]*n
  c=[0]*n
print(*a)
### BUGGY CODE ###

#Flog1を使うが，配列のオーバーフローを無視できるやり方をする．

#1:初期化
N, K = map(int,input().split())
h_list = list(map(int, input().split()))
inf = float("inf")
dp = [inf]*(N+110) #Kが100までなので余分に入れて安全！
h = [0]*(N+110)
for i in range(N):
    h[i] = h_list[i]

#2:初期値
dp[0] = 0

#3:dp実行部(配るDP)
for i in range(N):
    for k in range(1,K+1):
        dp[i+k] = min(dp[i+k], dp[i] + abs(h[i] - h[i+k]))
    

#4:出力
print(dp[N-1])

### FIXED CODE ###

# -*- coding: utf-8 -*- 
def cost(h,N,K):
    dp=[0]*N
    dp[1]=abs(h[0]-h[1])
    for i in range(2,N):
        tmp=[abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i)]
        dp[i]=min(tmp)
    return dp[-1]

N,K=map(int,input().split())
h=[int(num) for num in input().split()]

print(cost(h,N,K))
### BUGGY CODE ###

import sys,collections,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[list(S()) for _ in range(h)]

  ans=0
  _visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j,0))
      visited=copy.deepcopy(_visited)
      while len(q)>0:
        y,x,c=q.popleft()
        visited[y][x]=c

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if 0<=ny<h and 0<=nx<w:
            if field[ny][nx]=='#':
              continue
            if visited[ny][nx]!=-1:
              continue
            q.append((ny,nx,c+1))
      ans=max(ans,c)
  return ans

# main()
print(main())


### FIXED CODE ###

import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      visited[i][j]=0
      _ans=0
      while q:
        y,x=q.popleft()

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if not 0<=ny<h:
            continue
          if not 0<=nx<w:
            continue
          if field[ny][nx]=='#':
            continue
          if visited[ny][nx]!=-1:
            continue
          _ans=visited[y][x]+1
          visited[ny][nx]=_ans
          q.append((ny,nx))
      ans=max(ans,_ans)
  return ans

# main()
print(main())
### BUGGY CODE ###

n,m = map(int,input().split())
o = [int(input()) for _ in range(m)]
#print(o)
mod = (10**9)+7
dp = [1]+[0]*(n)

for i in range(1,n+1):
  dp[i] = (dp[i-1]+dp[i-2])%mod
  if i in o:
    dp[i] = 0
  #print(i,dp)
#print(dp)
print(dp[-1])


### FIXED CODE ###

n,m = map(int,input().split())
o = set(int(input()) for _ in range(m))
#print(o)
mod = (10**9)+7
dp = [0]*(n+1)
dp[0] = 1

for i in range(1,n+1):
  dp[i] = (dp[i-1]+dp[i-2])%mod
  if i in o:
    dp[i] = 0
  #print(i,dp)
#print(dp)
print(dp[-1])
### BUGGY CODE ###

from collections import deque

def bfs(AB,N,M):
    #initialize route guide
    g=[0 for n in range(N)]
    g[0]=1
    
    q=deque([1])
    while q:
        x=q.popleft()
        for m in range(M):
            if AB[m][0]==x and g[AB[m][1]-1]==0:
                q.append(AB[m][1])
                g[AB[m][1]-1]=x
            elif AB[m][1]==x and g[AB[m][0]-1]==0:
                q.append(AB[m][0])
                g[AB[m][0]-1]=x
    ok=True if 0 not in g else False
    return ok,g
    
def main():
    #normal input
    N,M=map(int,input().strip().split())
    AB=[list(map(int,input().strip().split())) for _ in range(M)]
    
    ok,g=bfs(AB,N,M)
    
    print("Yes" if ok else "No")
    if ok:
        for n in range(1,N):
            print(g[n])
    
    
    return

if __name__=="__main__":
    main()

### FIXED CODE ###

from collections import deque

def bfs2(g,n,m):
    pre=[0 for _ in range(n+1)]
    pre[1]=1
    q=deque([1])
    while q:
        x=q.popleft()
        for i in range(len(g[x])):
            if pre[g[x][i]]==0:
                q.append(g[x][i])
                pre[g[x][i]]=x
    return pre

def main2():
    #normal input
    n,m=map(int,input().strip().split())
    g=[[] for _ in range(n+1)]
    for _ in range(m):
        a,b=map(int,input().strip().split())
        g[a].append(b)
        g[b].append(a)
        
    pre=bfs2(g,n,m)
    
    print("Yes" if 0 not in pre[1:] else "No")
    for i in range(2,len(pre)):
        print(pre[i])

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

N=int(input())
L=list(map(int, input().split()))
S=0
L.sort()
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if L[i]+L[j]>L[k]:
                S+=1
            else:
                break
print(S)

### FIXED CODE ###

import bisect

N=int(input())
L=sorted(list(map(int, input().split())))
S=0

for i in range(N):
    for j in range(i+1,N):
        S+=bisect.bisect_left(L,L[i]+L[j])-j-1
print(S)
### BUGGY CODE ###

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



def main():
    a_added = [a[i] + i for i in range(n)]
    a_substracted = [j - a[j] for j in range(n)]
    c = 0
    
    for i in range(n-1):
        for j in range(i+1, n):
            if a_added[i] == a_substracted[j]:
                c += 1 

    print(c)
main()

### FIXED CODE ###

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

L = [i+A[i] for i in range(N)]
R = [i-A[i] for i in range(N)]

p = {}
m = {}
for i in range(N):
    if L[i] not in p:
        p[L[i]] = 1
    else:
        p[L[i]] += 1
for i in range(N):
    if R[i] not in m:
        m[R[i]] = 1
    else:
        m[R[i]] += 1

lower = max(min(p), min(m))
upper = min(max(p), max(m))
ans = 0
for x in range(lower, upper + 1):
    if x in p and x in m:
        ans += p[x] * m[x]

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

# -*- coding: utf-8 -*-
k=int(input())
if k%7==0:
  l=9*k/7
else:
  l=9*k
if l%2==0 or l%5==0:
  print(-1)
i=1
s=10
while True:
  j=s%l
  if j==1:
    print(i)
    break
  i+=1
  s=j*10

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
k=int(input())
if k%2==0 or k%5==0:
  print(-1)
  sys.exit()
s=7
for i in range(k):
  m=s%k
  if m==0:
    print(i+1)
    break
  s=m*10+7
### BUGGY CODE ###

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

dic = {}
for ai in a:
    if ai not in dic:
        dic[ai] = 0
    dic[ai] += 1

ans = 0

for ai in a:
    cnt = 0
    f = 1
    for i in range(1, int(ai**0.5)+1):
        if ai % i == 0:
            d = i
            if d in dic:
                cnt += dic[d]
            if d == ai:
                cnt -= 1
            if cnt > 0:
                f = 0
                break
            if i != ai // i:
                d = ai // i
                if d in dic:
                    cnt += dic[d]
                if d == ai:
                    cnt -= 1
                if cnt > 0:
                    f = 0
                    break

    ans += f

print(ans)
    

            




### FIXED CODE ###

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

a.sort()
am = a[-1]

memo = [0] * (am+1)

for ai in a:
    memo[ai] = 1

p = -1

for ai in a:
    if ai == p:
        memo[ai] = 0
        continue
    for j in range(2, am // ai + 1):
        memo[ai * j] = 0
    p = ai

print(sum(memo))
### BUGGY CODE ###

import itertools
n=int(input())
a=list(map(int, input().split()))
ans=0

for v in itertools.combinations(a, 2):
    ans += v[0]*v[1]

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

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
ans=0

s=sum(a)

for i in range(1,len(a)+1):
    ans += a[i-1] * (s-a[i-1])
    s = s-a[i-1]
    ans = ans % (10 ** 9 + 7)

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

from itertools import combinations

n, k = map(int, input().split())

lst = {i for i in range(0, n+1)}
re = 0
for i in range(k, n+1):
    temp = set(combinations(lst, i))
    tt = {sum(j) for j in temp}
    re += len(tt)

print(re+1)

### FIXED CODE ###

import sys
n, k = map(int, sys.stdin.readline().split())
ans = 0
mod = 10**9+7
for i in range(k, n+2):
    ans += (n-i+1)*i + 1
ans %= mod
print(ans)
### BUGGY CODE ###

import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque
import bisect


MOD = 10 ** 9 + 7

N, M = [int(x) for x in input().split()]

# KenList = [{} for _ in range(N)]
KenList = [[] for _ in range(N)]


PYlist = [None] * M
for i in range(M):
    P, Y = [int(x) for x in input().split()]
    P = P - 1
    PYlist[i] = (P, Y)
    KenList[P].append((i, Y))


for i in range(N):
    KenList[i] = sorted(KenList[i], key=lambda x: x[1])

for i in range(M):
    ken = PYlist[i][0]
    idx = 0
    kl = KenList[ken]
    for j in range(len(kl)):
        if kl[j][0] == i:
            idx = j
            break
    print("{0:06d}{1:06d}".format(ken+1, idx+1))


sys.exit(0)


### FIXED CODE ###

import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque
import bisect


MOD = 10 ** 9 + 7

N, M = [int(x) for x in input().split()]

KenList = [[] for _ in range(N)]

PYlist = [None] * M
for i in range(M):
    P, Y = [int(x) for x in input().split()]
    P = P - 1
    PYlist[i] = (P, Y)
    KenList[P].append((i, Y))


for i in range(N):
    KenList[i] = sorted(KenList[i], key=lambda x: x[1])

cityOrder = [None] * N
for i in range(N):
    kl = KenList[i]
    dic = {}
    for j in range(len(kl)):
        city = kl[j][0]
        dic[city] = j
    cityOrder[i] = dic


for i in range(M):
    ken = PYlist[i][0]
    kl = KenList[ken]
    idx = cityOrder[ken][i]
    # for j in range(len(kl)):
    #     if kl[j][0] == i:
    #         idx = j
    #         break

    print("{0:06d}{1:06d}".format(ken+1, idx+1))


sys.exit(0)
### BUGGY CODE ###

a, b = map(int, input().split())
common = []
for i in range(1, min(a, b) + 1):
    if a % i == 0 and b % i == 0:
        common.append(i)

count = 1
for i in range(1, len(common)):
    for j in range(1, i):
        if common[i] % common[j] == 0:
            break
    else:
        count += 1
print(count)


### FIXED CODE ###

import fractions
import math
a, b = map(int, input().split())
greatest = fractions.gcd(a, b)

factor = [1]
max_iter = int(math.sqrt(greatest)) + 1
for i in range(2, max_iter):
    while greatest % i == 0:
        greatest //= i
        factor.append(i)
if greatest != 1:
    factor.append(greatest)
factor = set(factor)
print(len(factor))