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

import bisect

def main():
    s = input()
    k = int(input())
    n = len(s)
    dp = []
    for l in range(n):
        for r in range(l + 1, n + 1):
            t = s[l:r]
            if t in dp: continue
            if len(dp) < k:
                bisect.insort(dp, t)
            elif t < dp[-1]:
                dp.pop()
                bisect.insort(dp, t)
    print(dp[-1])

main()


### FIXED CODE ###

import bisect

def main():
    s = input()
    k = int(input())
    n = len(s)
    dp = []
    for l in range(n):
        for r in range(l + 1, min(n + 1, l + 6)):
            t = s[l:r]
            i = bisect.bisect_right(dp, t)
            if i > 0:
                if t == dp[i - 1]: continue
            if len(dp) < k:
                bisect.insort(dp, t)
            elif t < dp[-1]:
                dp.pop()
                bisect.insort(dp, t)
    print(dp[-1])

main()
### BUGGY CODE ###

import bisect
import math

def dfs(v,visited):
  for u in m2[v]:
    if u in visited:
      continue
    visited.add(u)
    if(n2[u]==-1 or dfs(n2[u],visited)):
      n2[u]=v
      return True
  return False

n=int(input())
a=list(map(int,input().split()))
a.sort()
b=[]
kari=[]
ma=[]
m2=[]
n2=[]
vt=[]
vp=[]
visited=[]
ans=0
for i in range(n):
  kari=[]
  for j in range(20):
    for k in range(bisect.bisect_left(a,2**j-a[i]),bisect.bisect_right(a,2**j-a[i])):
      if(k==i):
        continue
      kari.append(k)
  ma.append(kari)
for i in range(n):
  kari=[]
  for j in range(n):
    if(j in ma[i]):
      kari.append(j+n)
  m2.append(kari)
for i in range(2*n):
  n2.append(-1)
print(sum(dfs(s,set())for s in range(n))//2)

### FIXED CODE ###

import collections
import math
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
c=collections.Counter(a)
ans=0
for i in a:
  j=int(math.log2(i))+1
  k=2**j-i
  if k in c.keys():
    if i==k and c[i]>1:
      c[i]-=2
      ans+=1
    elif i!=k and c[i]>0 and c[k]>0:
      c[i]-=1
      c[k]-=1
      ans+=1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
P = [(int(i)+1)/2 for i in input().split()]

wa_temp = 0
wa_max = 0.0
for i in range(N-K+1):
    wa_temp = sum(P[i:i+K])
    if wa_max < wa_temp:
        wa_max = wa_temp
print(wa_max)

### FIXED CODE ###

N, K = map(int, input().split())
P = [(int(i)+1)/2 for i in input().split()]

wa_temp = sum(P[0:K])
max_wa = wa_temp

for i in range(N-K):
    wa_temp = wa_temp - P[i] + P[i+K]
    if wa_temp > max_wa:
        max_wa = wa_temp
print(max_wa)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
count = 0
L.sort(reverse = True)
for i in range(N - 2):
    j = i + 1
    k = j + 1
    while L[i] < L[j] + L[k] and L[j] < L[i] + L[k]:
        count += 1
        if k == N - 1 and j == k - 1:
            break
        elif k == N - 1:
            j += 1
            k = j + 1
        elif k < N - 1:
            k += 1

print(count)


### FIXED CODE ###

from bisect import bisect_right
N = int(input())
L = list(map(int, input().split()))
count = 0
L.sort()
for i in range(N):
    for j in range(i):
        m = L[i] - L[j]
        k = bisect_right(L, m)
        n = max(0, j - k)
        count += n
print(count)
### BUGGY CODE ###

from bisect import bisect_right
N = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))
ans = 0
for i in A:
  for j in range(bisect_right(B,i),N):
    ans = ans + (N-bisect_right(C,B[j]))
print(ans)
    

### FIXED CODE ###

from bisect import bisect_right
from bisect import bisect_left

N = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))
ans = 0
for b in B:
  ans += (bisect_left(A, b) * (N-bisect_right(C, b)))

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

h, w = map(int, input().split())
s = ['']*(h+2)
s[0] = '#'*(w+2)
for i in range(1, h+1):
  s[i] = '#'+input()+'#'
s[h+1] = '#'*(w+2)

l=[[0]*(w+2) for _ in range(h+2)]
r=[[0]*(w+2) for _ in range(h+2)]
u=[[0]*(w+2) for _ in range(h+2)]
d=[[0]*(w+2) for _ in range(h+2)]
for i in range(1, h+1):
  for j in range(1, w+1):
    if s[i][j]=='.':
      l[i][j]=l[i][j-1]+1
  for j in range(w, 0, -1):
    if s[i][j]=='.':
      r[i][j]=r[i][j+1]+1
for j in range(1, w+1):
  for i in range(1, h+1):
    if s[i][j]=='.':
      u[i][j]=u[i-1][j]+1
  for i in range(h, 0, -1):
    if s[i][j]=='.':
      d[i][j]=d[i+1][j]+1
m=0
for i in range(1, h+1):
  for j in range(1, w+1):
    c=l[i][j]+r[i][j]+u[i][j]+d[i][j]-3
    if m<c:
      m=c
print(m)

### FIXED CODE ###

h, w = map(int, input().split())
s = ['']*(h+2)
s[0] = '#'*(w+2)
for i in range(1, h+1):
  s[i] = '#'+input()+'#'
s[h+1] = '#'*(w+2)

l=[[0]*(w+2) for _ in range(h+2)]
r=[[0]*(w+2) for _ in range(h+2)]
u=[[0]*(w+2) for _ in range(h+2)]
d=[[0]*(w+2) for _ in range(h+2)]
for i in range(1, h+1):
  for j in range(1, w+1):
    if s[i][j]=='.':
      l[i][j]=l[i][j-1]+1
  for j in range(w, 0, -1):
    if s[i][j]=='.':
      r[i][j]=r[i][j+1]+1
for j in range(1, w+1):
  for i in range(1, h+1):
    if s[i][j]=='.':
      u[i][j]=u[i-1][j]+1
  for i in range(h, 0, -1):
    if s[i][j]=='.':
      d[i][j]=d[i+1][j]+1
m=0
for i in range(1, h+1):
  for j in range(1, w+1):
    c=l[i][j]+r[i][j]+u[i][j]+d[i][j]-3
    if m<c:
      m=c
print(m)
### BUGGY CODE ###

def GCD(a,b):
    if b<a:
        c=a
        a=b
        b=c
    D=b//a
    if b==D*a:
        return a
    else:
        return GCD(b-a*D,a)

def sort_3(a,b,c):
    if b<a:
        d=a
        a=b
        b=d
    if c<b:
        d=c
        c=b
        b=d
    if b<a:
        d=a
        a=b
        b=d
    return [a,b,c]

def gcd(a,b,c):
    abc=sort_3(a,b,c)
    a=abc[0]
    b=abc[1]
    c=abc[2]
    return GCD(GCD(a,b),c) 

K=int(input())
sum=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            sum+=gcd(i,j,k)
print(sum)

### FIXED CODE ###

import math
K=int(input())
sum=0
for i in range(1,K+1):
    for j in range(1,K+1):
        tmp=math.gcd(i,j)
        for l in range(1,K+1):
            sum+=math.gcd(tmp,l)
print(sum)
### BUGGY CODE ###

S = input()
Q = int(input())

num_turn = 0

for i in range(Q):
    query = input()
    if query == '1':
        num_turn += 1
    else:
        _, f, c = query.split()
        f = int(f)
        if f == 1:
            if num_turn%2==0:
                S = c + S
            else:
                S = S + c
        else:
            if num_turn%2==0:
                S = S + c
            else:
                S = c + S

if num_turn%2==1:
    S = S[::-1]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())

num_turn = 0

front = []
end = []

for i in range(Q):
    query = input()
    if query == '1':
        num_turn += 1
    else:
        _, f, c = query.split()
        f = int(f)
        if f == 1:
            if num_turn%2==0:
                front.append(c)
            else:
                end.append(c)
        else:
            if num_turn%2==0:
                end.append(c)
            else:
                front.append(c)

S = list(S)
if num_turn%2==1:
    ans = end[::-1] + S[::-1] + front
else:
    ans = front[::-1] + S + end
print(''.join(ans))
### BUGGY CODE ###

from time import time
start = time()

# 解説放送の解法

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
def main():
  N,Q=map(int,input().split())
  *C,=map(int,input().split())
  q = [tuple(map(int,input().split())) for _ in range(Q)]

  # 重複度を数える。
  res=[]
  tmp_dict={}
  for i in range(N):
    if tmp_dict.get(C[i]) != None:
      #(クエリの種類、l, r）
      res.append((tmp_dict[C[i]]<<40) | (Q<<20) | i)
      del tmp_dict[C[i]]
    tmp_dict[C[i]] = i
    
  #assert time() - start < 0.1

  # クエリと合わせてソート。
  X = []
  for i in range(Q):
    l,r = q[i]
    # (元のクエリの順番、l, r)
    X.append(((l-1)<<40) | (i<<20) | r-1)

  #assert time() - start < 0.1
    
  X.extend(res) 
  X = sorted(X)
  
  #assert time() - start < 0.1

  # 平面走査
  bit = BIT(N)
  ans=[]
  mask = (1<<20) - 1
  for l in reversed(X):
    r = l & mask
    l >>= 20
    idx = l & mask
    l >>= 20
    if idx == Q:
      bit.add(r,1)
    else:
      ans.append((idx,r-l+1-bit.query(l-1,r)))

  # 元の順番にソートし直して出力
  print(*list(zip(*sorted(ans)))[1])
  
if __name__=="__main__":
  main()

### FIXED CODE ###

from time import time
start = time()

# 解説放送の解法

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
def main():
  N,Q=map(int,input().split())
  *C,=map(int,input().split())
  q = [tuple(map(int,input().split())) for _ in range(Q)]

  # 重複度を数える。
  res=[]
  tmp_dict={}
  for i in range(N):
    if tmp_dict.get(C[i]) != None:
      #(クエリの種類、l, r）
      res.append((tmp_dict[C[i]]<<40) | (Q<<20) | i)
      del tmp_dict[C[i]]
    tmp_dict[C[i]] = i

  # クエリと合わせてソート。
  X = []
  for i in range(Q):
    l,r = q[i]
    # (元のクエリの順番、l, r)
    X.append(((l-1)<<40) | (i<<20) | r-1)
    
  X.extend(res) 
  X = sorted(X)

  # 平面走査
  bit = BIT(N)
  ans=[0]*Q
  mask = (1<<20) - 1
  for l in reversed(X):
    r = l & mask
    l >>= 20
    idx = l & mask
    l >>= 20
    if idx == Q:
      bit.add(r,1)
    else:
      ans[idx] = r-l+1-bit.query(l-1,r)
      
  print(*ans)
  
if __name__=="__main__":
  main()
### BUGGY CODE ###

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

for i in range(n):
    b.append(a[i])
    b.reverse()

for j in b:
    print("{}".format(j), end=" ")

### FIXED CODE ###

from collections import deque

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


if n % 2 == 0:
    for i in range(n):
        if i % 2 != 0:  # 偶数なら前
            b.appendleft(a[i])
        else:
            b.append(a[i])
else:
    for j in range(n):
        if j % 2 == 0:  # 偶数なら後ろ
            b.appendleft(a[j])
        else:
            b.append(a[j])

print(*b)
### BUGGY CODE ###

import queue
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = float('inf')
q = queue.Queue()
vals = [[float('inf')]*w for _ in range(h)]

if s[0][0] == '#':
    q.put([0, 0, 1])
else:
    q.put([0, 0, 0])

while not q.empty():
    a = q.get()
    if a[0] == h-1 and a[1] == w-1:
        ans = min(ans, a[2])
        
    if a[0]+1 < h:
        if s[a[0]+1][a[1]] == '.':
            q.put([a[0]+1, a[1], a[2]])
            vals[a[0]+1][a[1]] = a[2]
        elif vals[a[0]][a[1]]+1 <= vals[a[0]+1][a[1]]:
            q.put([a[0]+1, a[1], a[2]+1])
            vals[a[0]+1][a[1]] = a[2]+1

    if a[1]+1 < w:
        if s[a[0]][a[1]+1] == '.':
            q.put([a[0], a[1]+1, a[2]])
        elif vals[a[0]][a[1]]+1 <= vals[a[0]][a[1]+1]:
            q.put([a[0], a[1]+1, a[2]+1])
            vals[a[0]][a[1]+1] = a[2]+1
print(ans)


### FIXED CODE ###

import queue
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = float('inf')
q = queue.Queue()
vals = [[float('inf')]*w for _ in range(h)]
vals[0][0] = 0
q.put([0, 0])

while not q.empty():
    a = q.get()
    for i, j in ((1, 0), (0, 1)):
        x, y = a[0]+i, a[1]+j
        if 0 <= x < h and 0 <= y < w:
            if s[x][y] == '#' and s[a[0]][a[1]] == '.':
                if vals[x][y] > vals[a[0]][a[1]]+1:
                    vals[x][y] = vals[a[0]][a[1]]+1
                    q.put([x, y])
            elif vals[x][y] > vals[a[0]][a[1]]:
                vals[x][y] = vals[a[0]][a[1]]
                q.put([x, y])
ans = vals[-1][-1]
if s[0][0] == '#':
    ans += 1

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

iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    i = 2
    iS = iM ** 0.5 + 1
    aRet = []
    while i < iS or i <= iM  :
        iCounter = 0
        while iM % i == 0:
            iM = iM // i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        i += 1
    #if aRet == [] : aRet = [1]
    return aRet

#ABC042Dの流用
#二分累乗法 iDを法として
def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY

aP = fPrimeCounter(iM)
if aP == [] :
    print (1)
else:
    iMax = max(aP) + iN - 1
    aM = [1] * (iMax + 1)
    #階乗 iD を法とした
    for i in range(1,iMax + 1):
        aM[i] = aM[i-1] * i  % iD
    aInvM = [1]* (iMax + 1)
    aInvM[iMax] = fBiPow(aM[iMax],iD-2,iD)
    #階乗の逆元 iD を法とした
    for i in range(iMax,0,-1):
        aInvM[i-1] = aInvM[i]*i % iD

    iRet = 1
    for i in aP:
        # i + iN -1  C  iN -1
        iRet *= aM[i+iN-1] * aInvM[iN-1] * aInvM[i] % iD
    iRet %= iD
    print(iRet)


### FIXED CODE ###

iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    i = 2
    iS = int(iM ** 0.5) + 1
    aRet = []
    while i < iS or iM != 1:
        iCounter = 0
        while iM % i == 0:
            iM = iM // i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        i += 1

    return aRet

#二分累乗法 iDを法として
def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY

aP = fPrimeCounter(iM)
if aP == [] :
    print (1)
else:
    iMax = max(aP) + iN - 1
    aM = [1] * (iMax + 1)
    #階乗 iD を法とした
    for i in range(1,iMax + 1):
        aM[i] = aM[i-1] * i  % iD
    aInvM = [1]* (iMax + 1)
    aInvM[iMax] = fBiPow(aM[iMax],iD-2,iD)
    #階乗の逆元 iD を法とした
    for i in range(iMax,0,-1):
        aInvM[i-1] = aInvM[i]*i % iD

    iRet = 1
    for i in aP:
        # i + iN -1  C  iN -1
        iRet *= aM[i+iN-1] * aInvM[iN-1] * aInvM[i] % iD
    iRet %= iD
    print(iRet)
### BUGGY CODE ###

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

for _ in range(M):
    b,c = [int(x) for x in input().split()]
    for i in range(b):
        A.append(c)

A.sort(reverse=True)

ans = sum(A[:N])
print(ans)


### FIXED CODE ###

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort(reverse=True)

CB = []
for i in range(M):
    b, c = [int(x) for x in input().split()]
    CB.append((c, b))
CB.sort(reverse=True)


L = []
for cb in CB:
    if len(L) >= N:
        break
    L.extend([cb[0]] * cb[1])

newA = A + L
newA.sort(reverse=True)

newA = newA[0:N]
ans = sum(newA)

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

import sys
sys.setrecursionlimit(10 ** 9)
n,m = map(int, input().split())
ab = []
c = [set() for i in range(n)]

for i in range(m):
  a = list(map(int, input().split()))
  a.sort()
  x,y = a[0]-1,a[1]-1
  c[x].add(y)
  c[y].add(x)

def dfs(s):
  if vis[s] == False:
    ary.append(s)
    vis[s] = True
    for j in c[s]:
      dfs(j)



vis = [False for i in range(n)]

ans= []

for i in range(n):
  ary = []
  dfs(i)
  if len(ary) == 0:
    continue
  ans.append(len(ary))

print (len(ans)-1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
n,m = map(int, input().split())
ab = []
c = [set() for i in range(n)]

for i in range(m):
  a = list(map(int, input().split()))
  a.sort()
  x,y = a[0]-1,a[1]-1
  c[x].add(y)
  c[y].add(x)

def dfs(s):
  if vis[s] == False:
    ary.append(s)
    vis[s] = True
    for j in c[s]:
      dfs(j)

vis = [False for i in range(n)]

ans= []

for i in range(n):
  ary = []
  dfs(i)
  if len(ary) == 0:
    continue
  ans.append(len(ary))

print (len(ans)-1)
### BUGGY CODE ###

from collections import deque

H, W = map(int, list(input().split()))
Ch, Cw = map(int, list(input().split()))
Ch -= 1
Cw -= 1
Dh, Dw = map(int, list(input().split()))
Dh -= 1
Dw -= 1
S = [list(input()) for _ in range(H)]

dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]

INF = pow(10, 10)
seen = [[INF] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw])

while q:
    th, tw = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1:
            continue
        if S[nh][nw] == '#':
            continue
        if seen[nh][nw] <= seen[th][tw]:
            continue
        seen[nh][nw] = seen[th][tw]
        q.append([nh, nw])
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            if dh2 == 0 and dw2 == 0:
                continue
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1:
                continue
            if S[nh][nw] == '#':
                continue
            if seen[nh][nw] <= seen[th][tw] + 1:
                continue
            seen[nh][nw] = seen[th][tw] + 1
            q.append([nh, nw])

if seen[Dh][Dw] is INF:
    print(-1)
else:
    print(seen[Dh][Dw])

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh, Dw = map(int, input().split())
Dh -= 1
Dw -= 1
S = [input() for _ in range(H)]

dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]

INF = pow(10, 10)
seen = [[INF] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw])

while q:
    th, tw = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= seen[th][tw]:
            continue
        seen[nh][nw] = seen[th][tw]
        q.append([nh, nw])
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            if dh2 == 0 and dw2 == 0:
                continue
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= seen[th][tw] + 1:
                continue
            seen[nh][nw] = seen[th][tw] + 1
            q.appendleft([nh, nw])

if seen[Dh][Dw] is INF:
    print(-1)
else:
    print(seen[Dh][Dw])
### BUGGY CODE ###

s = input()
MOD = 10**9+7

dp = [[0 for i in range(13)] for i in range(len(s)+1)]
dp[0][0] = 1

for i in range(len(s)):
  if s[i]=='?':
    for k in range(10):
      for j in range(13):
        dp[i+1][(j*10+k)%13] = (dp[i+1][(j*10+k)%13] + dp[i][j])%MOD
  else:
    t = int(s[i])
    for j in range(13):
      dp[i+1][(j*10+t)%13] = (dp[i+1][(j*10+t)%13] + dp[i][j])%MOD
print(dp[len(s)][5])

### FIXED CODE ###

s = input()
MOD = 10**9+7

dp = [[0 for i in range(13)] for i in range(len(s)+1)]
dp[0][0] = 1

for i in range(len(s)):
  if s[i]=='?':
    for k in range(10):
      for j in range(13):
        dp[i+1][(j*10+k)%13] = (dp[i+1][(j*10+k)%13] + dp[i][j])%MOD
  else:
    t = int(s[i])
    for j in range(13):
      dp[i+1][(j*10+t)%13] = (dp[i+1][(j*10+t)%13] + dp[i][j])%MOD
print(dp[len(s)][5])
### BUGGY CODE ###

import numpy as np
N = int(input())
array = list(map(int,input().split()))
ans = 0
for i in range(N-1):
  ans += array[i]*np.sum(array[i+1:N])  
print( ans%(10**9+7) )

### FIXED CODE ###

N = int(input())
array = list(map(int,input().split()))
ans = 0
kuso = sum(array)
for i in range(N-1):
  kuso -= array[i]
  ans += array[i]*kuso  
print( ans%(10**9+7) )
### BUGGY CODE ###

def main():
    X, Y, A, B, C = tuple(map(int, input().split()))
    P = tuple(map(int, input().split()))
    Q = tuple(map(int, input().split()))
    R = tuple(map(int, input().split()))

    P = sorted(P, reverse=True)
    Q = sorted(Q, reverse=True)
    R = sorted(R, reverse=True)

    x = P[:X]
    y = Q[:Y]

    for r_i in R:
        if r_i < min(x[-1], y[-1]):
            break
        else:
            if x[-1] < y[-1]:
                x[-1] = r_i
                # x = sorted(x, reverse=True)
                x.sort(reverse=True)
            else:
                y[-1] = r_i
                # y = sorted(y, reverse=True)
                y.sort(reverse=True)

    print(sum(x) + sum(y))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    X, Y, A, B, C = tuple(map(int, input().split()))
    P = tuple(map(int, input().split()))
    Q = tuple(map(int, input().split()))
    R = tuple(map(int, input().split()))

    P = sorted(P, reverse=True)
    Q = sorted(Q, reverse=True)
    R = sorted(R, reverse=True)

    x = P[:X]
    y = Q[:Y]

    saikyo = sorted(x + y + R, reverse=True)
    print(sum(saikyo[:(X + Y)]))


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

import itertools
import math
import fractions
import functools
k = int(input())
h_list = []



def gcd(numbers):
    return functools.reduce(fractions.gcd, numbers)

for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            h_list.append([i,j,l])

sum = 0
for i in range(len(h_list)):
    sum += gcd(h_list[i])

print(sum)

### FIXED CODE ###

import itertools
import math
import fractions
import functools

K = int(input())
 
res = 0
for i in range(1, K+1):
  for j in range(1, K+1):
    gcd1 = math.gcd(i, j)
    for k in range(1, K+1):
      if gcd1 == 1:
        res += 1
      else:
        res += math.gcd(gcd1, k)
print(res)
### BUGGY CODE ###

A, B, C, K = map(int, input().split(" "))
max_val = 0
for cnt in range(K):
    if A >= cnt+1:
        max_val += 1
        continue
    elif B >= cnt+1-A:
        continue
    else:
        max_val -= 1
print(max_val)

### FIXED CODE ###

A, B, C, K = map(int, input().split(" "))
if K-A <= 0:
    print(K)
else:
    if K - (A + B) <= 0:
        print(A)
    elif K == A+B+C:
        print(A-C)
    else:
        print(A - (K-(A+B)))
### BUGGY CODE ###

import math

def comb(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

if K >= 2:
  A.sort(reverse = True)
  ans = 0
  for i in range(N - K + 1):
    for j in range(i + K - 1, N):
      ans += (A[i] - A[j]) * comb(j - i - 1, max(0, K - 2))
      ans %= MOD
  print(ans)
else:
  print(0)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

kai1 = [1, 1]
kai2 = [1, 1]
inverse = [0, 1]
for i in range(2, N + 1):
  kai1.append((kai1[-1] * i) % MOD)
  inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
  kai2.append((kai2[-1] * inverse[-1]) % MOD)


def comb(n, r):
  if r < 0 or r > n:
    return 0
  r = min(r, n - r)
  return (kai1[n] * kai2[r] * kai2[n - r]) % MOD

if K >= 2:
  A.sort(reverse = True)
  maxS = 0
  minS = 0
  for i in range(N - K + 1):
    maxS += A[i] * comb(N - i - 1, K - 1)
    maxS %= MOD
  A.sort()
  for i in range(N - K + 1):
    minS += A[i] * comb(N - i - 1, K - 1)
    minS %= MOD
  print((maxS - minS) % MOD)
else:
  print(0)