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

import sys
input=sys.stdin.readline

def main():
    N, M, K = list(map(int, input().split()))

    MOD = 998244353

    class Comb:
        def __init__(self, N):
            self.fac = [1] * (N+1)
            for i in range(2, N+1): self.fac[i] = self.fac[i-1] * i % MOD

        def __call__(self, n, r):
            return self.comb(n, r)

        def comb(self, n, r):
            if r < 0 or r > n: return 0
            return (self.fac[n] * pow(self.fac[r], MOD-2, MOD)) % MOD * pow(self.fac[n-r], MOD-2, MOD) % MOD

        def permutation(self, n, r):
            if r == 0: return 1
            return self.fac[n] * pow(self.fac[n-r], MOD-2, MOD) % MOD

    comb = Comb(N)

    ans = 0

    for i in range(K+1):
        n = (comb(N-1, i) * M) % MOD * pow(M-1, N-1-i, MOD) % MOD
        ans += n
        ans %= MOD

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
    N, M, K = list(map(int, input().split()))

    MOD = 998244353

    class Comb:
        def __init__(self, N):
            self.fac = [1] * (N+1)
            for i in range(2, N+1): self.fac[i] = self.fac[i-1] * i % MOD

        def __call__(self, n, r):
            return self.comb(n, r)

        def comb(self, n, r):
            if r < 0 or r > n: return 0
            return (self.fac[n] * pow(self.fac[r], MOD-2, MOD)) % MOD * pow(self.fac[n-r], MOD-2, MOD) % MOD

        def permutation(self, n, r):
            if r == 0: return 1
            return self.fac[n] * pow(self.fac[n-r], MOD-2, MOD) % MOD

    comb = Comb(N)

    ans = 0

    for i in range(K+1):
        n = (comb(N-1, i) * M) % MOD * pow(M-1, N-1-i, MOD) % MOD
        ans += n
        ans %= MOD

    print(ans)

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

def solve(h, k):
    dp = [0]
    for i in range(1, len(h)):
        best = float("inf")
        for j in range(1, min(i, k)+1):
            best = min(best, dp[i - j] + abs(h[i - j] - h[i]))
        dp.append(best)
    return dp[-1]


if __name__ == "__main__":
    n, k = map(int, input().split())
    h = [int(x) for x in input().split()]
    print(solve(h, k))


### FIXED CODE ###

def solve(h, k):
    dp = [0]
    for i in range(1, len(h)):
        best = float("inf")
        for j in range(1, min(i, k)+1):
            best = min(best, dp[i - j] + abs(h[i - j] - h[i]))
        dp.append(best)
    return dp[-1]


if __name__ == "__main__":
    n, k = map(int, input().split())
    h = [int(x) for x in input().split()]
    print(solve(h, k))
### BUGGY CODE ###

N,K=map(int, input().split())
p = list(map(int, input().split()))

def calc(n,a,l):
  return (a+l)/2

max_e=0
for i in range(N-(K-1)):
  v=p[i:K+i]
  #print(v)
  smin=len(v)
  smax=sum(v)
  kou=smax-(smin-1)
  e=calc(kou,smin,smax)
  #e=list(map(calc, v))
  #print(e)
  #e=sum(e)

  if max_e<e:
    max_e=e

print(max_e)

### FIXED CODE ###

N,K=map(int, input().split())
p = list(map(int, input().split()))

p = [(n+1)/2 for n in p]
import numpy as np
s = np.cumsum(p)

e=s[K-1]
max_e=e
for i in range(1,N-K):
  e=s[i+K]-s[i]
  max_e = max(max_e, e)
    
print(max_e)
### BUGGY CODE ###

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

num = 1
cnt = 0
lst = []
for i in range(N):
    if (i < K):
        num *= A[i]
    else:
        lst.append(num)
        num = (num // A[cnt]) * A[i]
        cnt += 1
lst.append(num)

for i in range(len(lst) - 1):
    if (lst[i] < lst[i+1]):
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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

cnt = 0
for i in range(K, N):
    if (A[cnt] < A[i]):
        print('Yes')
    else:
        print('No')
    cnt += 1
### BUGGY CODE ###

import fractions

A,B,C,D = map(int,input().split())

gcd = fractions.gcd(C,D)
lcm = int(C*D/gcd)

comp = int(((lcm//C) + (lcm//D) - 1) * ((B-A+1)//lcm))

for i in range((B-A+1)%lcm):
    if (A+i)%C == 0 or (A+i)%D == 0:
        comp += 1

print(B-A+1-comp)


### FIXED CODE ###

import fractions

A,B,C,D = map(int,input().split())

gcd = fractions.gcd(C,D)
lcm = int(C*D/gcd)

ans_A = int((A-1) - (A-1)//C - (A-1)//D + (A-1)//lcm)
ans_B = int(B - B//C - B//D + B//lcm)
print(ans_B - ans_A)
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())

m10000 = -1
m5000 = -1
m1000 = -1
  
for a in range(N+1):
  for b in range(N+1-a):
    c = np.abs(N - a - b)
    X = 10000*a + 5000*b + 1000*c
    
    if X == M:
      m10000 = a
      m5000 = b
      m1000 = c

print(m10000, " ", m5000, " ", m1000)

### FIXED CODE ###


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

m10000 = -1
m5000 = -1
m1000 = -1
  
for a in range(N+1):
  for b in range(N+1-a):
    c = abs(N - a - b)
    X = 10000*a + 5000*b + 1000*c
    
    if X == M:
      m10000 = a
      m5000 = b
      m1000 = c

print(m10000, " ", m5000, " ", m1000)
### BUGGY CODE ###

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

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

import functools

@functools.lru_cache(maxsize=10 ** 6)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

@functools.lru_cache(maxsize=10 ** 6)
def lcm(a, b):
    return (a // gcd(a, b)) * b

a_lcm = 1
for v in a:
    a_lcm = lcm(a_lcm, v)

ans = 0
for v in a:
    ans = (ans + (a_lcm // v)) % MOD

print(ans)


### FIXED CODE ###

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

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

import collections

lcm_pf = collections.defaultdict(int)
for i, v in enumerate(a):
    j = 2
    pf = {}
    while j ** 2 <= v:
        ext = 0
        while v % j == 0:
            ext += 1
            v //= j
        if ext:
            pf[j] = ext
            lcm_pf[j] = max(lcm_pf[j], ext)
        j += 1
    if v != 1:
        pf[v] = 1
        lcm_pf[v] = max(lcm_pf[v], 1)

lcm = 1
for p in lcm_pf:
    lcm = lcm * (p ** lcm_pf[p])

ans = 0
for v in a:
    ans = ans + (lcm // v)
print(ans % MOD)
### BUGGY CODE ###


N = int(input())

ans = 0

for a in range(1, N+1):
    for b in range(1, int(N/a)+1):
        if a * b < N:
            ans +=1
print(ans)

### FIXED CODE ###

N = int(input())

ans = 0

for a in range(1, N+1):
    if N%a==0:
        b_max = int(N/a)-1
    else:
        b_max = int(N//a)
    
    ans += b_max
print(ans)
### BUGGY CODE ###

def main():
    import itertools,copy,sys
    input = sys.stdin.readline
    T = list(input())
    N = [i for i, x in enumerate(T) if x == '?']
    B = list(itertools.product(['P','D'], repeat=len(N)))
    max = 0
    maxstr = ''
    for b in B:
        TC = copy.deepcopy(T)
        for n,j in zip(N,range(len(N))):
            TC[n] = b[j]
        TC = ''.join(TC)
        sum = TC.count('PD') + TC.count('D')
        if max < sum:
            max = sum
            maxstr = TC
    print(maxstr)
main()

if __name__ == '__main__':
    main()

### FIXED CODE ###

#BBBBBBBBBBB

import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

t = rl()
li = []
for i in range(len(t)):
    if t[i] == '?':
        li.append('D')
    else:
        li.append(t[i])
print(''.join(li))
### BUGGY CODE ###

N=int(input())
S = []
A = []
from collections import Counter

for _ in range(N):
    S.append(input())
L=[]
for s in S:
  L.append(Counter(s))

x=0
for i in range(N):
  for j in range(i+1,N):
    if L[i]==L[j]:
    	x+=1
print(x)

### FIXED CODE ###

from collections import Counter
N = int(input())
S = [input() for i in range(N)]
ctr = Counter()
answer = 0
for s in S:
    a = ''.join(sorted(list(s)))
    #print(a)
    if a in ctr:
        answer += ctr[a]
    ctr[a] += 1
print(answer)
### BUGGY CODE ###

from bisect import bisect_right, bisect_left
N = int(input())
L = [int(_) for _ in input().split()]
ans = 0
L.sort()

for n in range(N - 1, -1, -1):
    for m in range(n - 1, -1, -1):
        if abs(N - 1 - bisect_left(L, L[n] + L[m])) > 0:
            #print(n, m)
            ans += bisect_left(L, L[n] + L[m]) - n - 1
            #print("ans", ans)

print(ans)

### FIXED CODE ###

from bisect import bisect_right, bisect_left
N = int(input())
L = [int(_) for _ in input().split()]
ans = 0
L.sort()

for n in range(N - 1, -1, -1):
    for m in range(n - 1, -1, -1):
        ans += bisect_left(L, L[n] + L[m]) - n - 1

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

N, Q = map(int, input().split())
S = input()

for _ in range(Q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    char = S[l:r+1]
    ans = char.count("AC")
    print(ans)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
len_S = len(S)

char = ""
ac = [0] * len_S
val = 0
for i in range(N):
    char += S[i]
    # print(char)
    # print(char[len(char)-2:len(char)+1])
    if char[len(char)-2:len(char)+1] == "AC":
        val += 1
    ac[i] = val
# print(ac)

for _ in range(Q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    ans = ac[r] - ac[l]
    print(ans)
### BUGGY CODE ###

def getMP(L,A,B,C):
    n = len(L)
    if n == 3:
        a = abs(L[0]-A) + abs(L[1]-B) + abs(L[2]-C)
        b = abs(L[0]-A) + abs(L[2]-B) + abs(L[1]-C)
        c = abs(L[1]-A) + abs(L[0]-B) + abs(L[2]-C)
        d = abs(L[1]-A) + abs(L[2]-B) + abs(L[0]-C)
        e = abs(L[2]-A) + abs(L[0]-B) + abs(L[1]-C)
        f = abs(L[2]-A) + abs(L[1]-B) + abs(L[0]-C)
        return min(a,b,c,d,e,f)
    else:
        ans = 10**7
        for i in range(n):
            M = L + []
            M.pop(i)
            ans = min(ans, getMP(M,A,B,C))
            for j in range(n-i-1):
                M = L + []
                m = M.pop(i)
                M[j+i] += m
                ans = min(ans, getMP(M,A,B,C)+10)
        return ans
    
N, A, B, C = map(int, input().split())
L = [int(input()) for _ in range(N)]

print(getMP(L,A,B,C))

### FIXED CODE ###

import itertools

N, A, B, C = map(int, input().split())
l = [int(input()) for _ in range(N)]

state = ['A', 'B', 'C', 'D']
loop = list(itertools.product(state, repeat=N))

m = 10**8

for i in range(4**N):
    takeA = 0
    takeB = 0
    takeC = 0
    syn = -3
    for j in range(N):
        if loop[i][j] == 'A':
            takeA += l[j]
            syn += 1
        elif loop[i][j] == 'B':
            takeB += l[j]
            syn += 1
        elif loop[i][j] == 'C':
            takeC += l[j]
            syn += 1
    if takeA!=0 and takeB!=0 and takeC!=0:
        m = min(m, abs(takeA-A)+abs(takeB-B)+abs(takeC-C)+10*syn)
        
print(m)
### BUGGY CODE ###

from collections import deque
n, k = map(int, input().split())
a = list(map(int, input().split()))

prev = 1
for i in range(k):
    prev *= a[i]

a_old = deque(a)
a = deque(a[k:])
for i in range(k, n):
    score = prev*a.popleft() / a_old.popleft()
    if score <= prev:
        print('No')
    else:
        print('Yes')
    prev = score


### FIXED CODE ###

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

for i in range(n-k):
    if a[i+k] <= a[i]:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

n, k = map(int, input().split())
s = set()
for i in range(k):
    l, r = map(int, input().split())
    s |= set(list(range(l, r+1)))

mod = 998244353
dp = [0] * (n+1)
dp[1] = 1
s = sorted(list(s))
for i in range(1, n):
    for add in s:
        if i+add <= n:
            dp[i+add] += dp[i]
            dp[i+add] %= mod
print(dp[n])

### FIXED CODE ###

n, k = map(int, input().split())
s = []
for i in range(k):
    l, r = map(int, input().split())
    s.append([l, r])

mod = 998244353
dp = [0] * (n+1)
cumsum = [0] * (n+1)

dp[1] = 1
s = sorted(s)
counter = 0
for i in range(1, n+1):
    counter += cumsum[i]
    dp[i] += counter
    dp[i] %= mod
    for l, r in s:
        if i+l <= n:
            cumsum[i+l] += dp[i]
        if i+r+1 <= n:
            cumsum[i+r+1] -= dp[i]
print(dp[n] % mod)
### BUGGY CODE ###

import sys

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

ans = 0
DP = [0] * (W + 1)
for i in range(N):
    dp = []
    w, v = map(int, sys.stdin.readline().split())
    for j, element in enumerate(DP):
        if j >= w:
            dp.append(max(DP[j - w] + v, element))
        else:
            dp.append(element)
    DP = dp

print(max(DP))


### FIXED CODE ###

import sys

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

ans = 0
DP = [0] * (W + 1)
for i in range(N):
    dp = []
    w, v = map(int, sys.stdin.readline().split())
    for j, element in enumerate(DP):
        if j >= w:
            dp.append(DP[j - w] + v if element < DP[j - w] + v else element)
        else:
            dp.append(element)
    DP = dp

print(max(DP))
### BUGGY CODE ###

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

rec_hen = 0
a_set = sorted(set(a), reverse=True)
for ai in a_set:
  ac = a.count(ai)
  if ac >= 4:
    if rec_hen != 0:
      print(rec_hen * ai)
      exit(0)
    print(ai * ai)
    exit(0)
  if ac >= 2:
    if rec_hen != 0:
      print(rec_hen * ai)
      exit(0)
    rec_hen = ai

print(0)

### FIXED CODE ###

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

rec_hen = 0
#a_set = sorted(set(a), reverse=True)
acc = collections.Counter(a)
ssa = sorted(acc.items(), key=lambda x: x, reverse=True)
for i, c in ssa:
  if c >= 4:
    if rec_hen != 0:
      print(rec_hen * i)
      exit(0)
    print(i * i)
    exit(0)
  if c >= 2:
    if rec_hen != 0:
      print(rec_hen * i)
      exit(0)
    rec_hen = i

print(0)
### BUGGY CODE ###

n = int(input())
MOD = n

print(0, flush=True)
in_prev = 0
s = input()
if s == 'Vacant':exit()
else: in_prev = s
    out_prev = 0
    out_now = n//2

opp=-1
step = (n-1)//2
for j in range(19):

    s = input()


    if s == 'Vacant':
        exit()

    elif in_prev == s:

        tmp = out_prev+out_now
        if tmp %2==0:
            opp = True
            if out_prev == 0:
                out_prev = n
                tmp = out_prev+out_now+1
            else:
                tmp = out_prev+out_now
            out_prev = out_now
            out_now = tmp//2
            print(out_now, flush=True)
        else:
            opp = False
            tmp = out_prev+out_now
            out_prev = out_now
            out_now = tmp//2
            print(out_now, flush=True)

    else:

        tmp = out_prev+out_now
        if tmp %2!=0:
            opp = True
            if out_prev == 0:
                out_prev = n
                tmp = out_prev+out_now+1
            else:
                tmp = out_prev+out_now
            out_prev = out_now
            out_now = tmp//2
            print(out_now, flush=True)
        else:
            opp = False
            tmp = out_prev+out_now
            out_prev = out_now
            out_now = tmp//2
            print(out_now, flush=True)



### FIXED CODE ###

n = int(input())
print(0,flush=True)

prev = input()
if prev=='Vacant': exit()
zero = prev
now=[]

def isok(ans, odd_diff):
    print(ans,flush=True)
    now = input()

    if now == 'Vacant': exit()

    if (now==zero and odd_diff)or(now!=zero and not odd_diff):
        return True
    else:
        return False

ok = n-1 #ok以前にVacantが存在
ng = 0 #ng以前にVacantは存在しない

while ok - ng > 1:
    m = (ok+ng)//2
    odd_diff = (m%2==1)
    if isok(m, odd_diff):
        ok = m
    else:
        ng = m

print(ok,flush=True)
exit()
### BUGGY CODE ###

import sys

h, w, m = map(int,input().split())
bomb = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(m)]
x = [0] * h
y = [0] * w

for h,w in bomb:
    x[h] +=1
    y[w] +=1

maxX = max(x)
maxY = max(y)

r = [h for h,x in enumerate(x) if x == maxX]
c = [w for w,y in enumerate(y) if y == maxY]

for ri in r:
    for ci in c:
        if (ri,ci) not in bomb:
            print(maxX + maxY)
            sys.exit()
print(maxX + maxY -1)

### FIXED CODE ###

import sys

def main():
    h, w, m = map(int,input().split())
    bomb = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(m)]
    x = [0] * h
    y = [0] * w

    for h,w in bomb:
        x[h] +=1
        y[w] +=1

    maxX = max(x)
    maxY = max(y)

    r = [h for h,x in enumerate(x) if x == maxX]
    c = [w for w,y in enumerate(y) if y == maxY]

    bomb = set(bomb)
    
    for ri in r:
        for ci in c:
            if (ri,ci) not in bomb:
                print(maxX + maxY)
                sys.exit()
    print(maxX + maxY -1)
    
main()
### BUGGY CODE ###

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)

for _ in range(M):
    A[0] = int(A[0]/2)
    A = sorted(A, reverse=True)

print(sum(A))

### FIXED CODE ###

from heapq import (
    heapify,  # 優先度付きキューの生成
    heappop,
    heappush,
    heappushpop,
    heapreplace
    )

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

#heapqは最小値しか取り出さないので-1倍する
A = [-i for i in map(int,input().split())]
heapify(A)

for _ in range(M):
    s = -heappop(A)
    s //= 2
    heappush(A, -s)

print(-sum(A))
### BUGGY CODE ###

def abc178d():
    s = int(input())
    dp = [[0] * (s+1) for _ in range(700)]
    for j in range(3, s+1):
        dp[0][j] = 1
    for i in range(1, 700):
        for j in range((i+1)*3, s+1):
                dp[i][j] = sum(dp[i-1][i*3:j-2])
    cnt = 0
    for i in range(0, 700):
        cnt += dp[i][s]
    print(cnt%(pow(10, 9)+7))
abc178d()

### FIXED CODE ###

def abc178d():
    s = int(input())
    dp = [[0] * (s+1) for _ in range(700)]
    for j in range(3, s+1):
        dp[0][j] = 1
    for i in range(1, 700):
        for j in range((i+1)*3, s+1):
            if j == (i+1)*3:
                dp[i][j] = sum(dp[i-1][i*3:j-2])
            else:
                dp[i][j] = dp[i][j-1] + dp[i - 1][j-3]
    cnt = 0
    for i in range(0, 700):
        cnt += dp[i][s]
    print(cnt%(pow(10, 9)+7))
abc178d()
### BUGGY CODE ###

import math

def readInt():
	return int(input())
 
def readInts():
	return list(map(int, input().split()))
 
def readChars():
	return input().split()

N,Y = readInts()
o = Y



for x in range(Y//10000+1):
	o=Y-x*10000
	#print(Y,x,o)
	for y in range(o//5000+1):
		#print(y)
		o=Y-x*10000-y*5000
		for z in range(o//1000+1):
			if x+y+z>N:
				break
			res = x*10000+y*5000+z*1000
			if res==Y and sum([x,y,z])==N:
				print(str(x)+" "+str(y)+" "+str(z))
				exit()

print("-1 -1 -1")

### FIXED CODE ###

import math

def readInt():
	return int(input())
 
def readInts():
	return list(map(int, input().split()))
 
def readChars():
	return input().split()

N,Y = readInts()
o = Y



for x in range(Y//10000,-1,-1):
	o=Y-x*10000
	#print(Y,x,o)
	for y in range(o//5000,-1,-1):
		#print(y)
		o=Y-x*10000-y*5000
		z=o//1000
		res = x*10000+y*5000+z*1000
		if x+y+z>N or res>Y:
			break
		if res==Y and x+y+z==N:
			print(str(x)+" "+str(y)+" "+str(z))
			exit()

print("-1 -1 -1")
### BUGGY CODE ###

N  = int(input())
As = list(map(int,input().split()))
array = []
for i in range(31):
    sum = 0
    for j in range(N):
        if As[j]>>i & 1 == 1:
            sum += 1
        if j == N-1 and sum % 2 == 0:
            array.append(0)
        if j == N-1 and sum % 2 == 1:
            array.append(1)
ans_array = []
for j in range(N):
    for i in range(31):
        if array[i] == 1 and As[j]>>i & 1 == 1:
            As[j] &= ~(1<<i)
        elif array[i] == 1:
            As[j] |= 1<<i

print(*As)

### FIXED CODE ###

N  = int(input())
As = list(map(int,input().split()))
array = []
B = 0
for i in range(N):
    B ^= As[i]
ans_array = []
for i in range(N):
    ans_array.append(B^As[i])
print(*ans_array)
### BUGGY CODE ###

n = int(input())

dishes_a = list()
dishes_b = list()
dishes_diff = list()
for i in range(0, n):
    a, b = input().split()
    a = int(a)
    b = int(b)
    diff = b - a
    dishes_a.append(a)
    dishes_b.append(b)
    dishes_diff.append(diff)

takahashi = 0
aoki = 0
diff_flag = True
index = 0
for i in range(0, n):
    if i % 2 == 0:
        if max(dishes_diff) != 0:
            index = dishes_diff.index(max(dishes_diff))
        else:
            index = dishes_a.index(max(dishes_a))

        takahashi = takahashi + dishes_a[index]
        dishes_a.pop(index)
        dishes_b.pop(index)
        dishes_diff.pop(index)
    else:
        index = dishes_b.index(max(dishes_b))
        aoki = aoki + dishes_b[index]
        dishes_a.pop(index)
        dishes_b.pop(index)
        dishes_diff.pop(index)

print(takahashi - aoki)


### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
import os
import re
import sys
import math


n = int(input())

dishes = list()

for i in range(0, n):
    a, b = raw_input().split()
    a = int(a)
    b = int(b)
    sum = a + b
    dishes.append([a, b, sum])

takahashi = 0
aoki = 0
dishes.sort(key=lambda x: x[2], reverse=True)

for i in range(0, n):
    if i % 2 == 0:
        j = dishes[0]
        dishes.pop(0)
        takahashi = takahashi + j[0]
    else:
        j = dishes[0]
        dishes.pop(0)
        aoki = aoki + j[1]

print takahashi - aoki
### BUGGY CODE ###

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

result = []
for i in range(len(a)):
    for j in range(len(a)):
        if i < j:
            result.append(a[i] * a[j])

print(sum(result) % (10 ** 9 + 7))


### FIXED CODE ###

n = input()
a = list(map(int, input().split()))
sum_a = sum(a)
count = 0
for i, v in enumerate(a):
    sum_a -= v
    count += v * sum_a

print(count % (10 ** 9 + 7))
### BUGGY CODE ###

import numpy as np

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

r = []

for i in range(1,N+1):
    a = li.index(i)
    r.append(a)

result = ""

for t in r:
    result = result + str(t+1) + " "

print(result)

### FIXED CODE ###

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

r = [0]*N

for index in range(N):
    l = li[index]
    r[l-1] = str(index+1)

print(" ".join(r))
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
R = []
for i in range(N-K+1):
  X = A[i]
  for j in range(K-1):
    X = X*A[i+j+1]
  R.append(X)
  if i ==0:
    continue
  else:
    if X > R[i-1]:
      print("Yes")
    else:
      print("No")


### FIXED CODE ###

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

for i in range(K-1,N-1):
  if A[i-(K-1)] < A[i+1]:

    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
    ans = ans * i

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

### FIXED CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
    ans = ans * i
    ans = ans % (10 ** 9 + 7)

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

N,K=map(int,input().split())
dp=[1000000000000000 for i in range(N)]
h=[int(x) for x in input().split()]
dp[0]=0
for i in range(N):
    for j in range(i,i+K+1 if i+K+1 < N else N):
        dp[j] = dp[j] if dp[j]<dp[i]+abs(h[j]-h[i]) else dp[i]+abs(h[j]-h[i])
print(dp[-1])

### FIXED CODE ###

N,K=map(int,input().split())
dp=[1000000000000000 for i in range(N)]
h=[int(x) for x in input().split()]
dp[0]=0
for i in range(N):
    for j in range(i,i+K+1 if i+K+1 < N else N):
        dp[j] = dp[j] if dp[j]<dp[i]+abs(h[j]-h[i]) else dp[i]+abs(h[j]-h[i])
print(dp[-1])
### BUGGY CODE ###

n,*h=map(int,open(0).read().split())
while len(h)>1:
    kh=[]
    for i in range(len(h)):
        mn=min(h)
        md=h[i]%mn
        if md!=0:
            kh.append(md)
        else:
            kh.append(mn)
    h=list(set(kh))
print(mn)

### FIXED CODE ###

def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)

n,*h=map(int,open(0).read().split())

gh=gcd(h[0],h[1])
for i in range(2,n):
    gh=gcd(h[i],gh)

print(gh)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
A_sl = list(set(A))
if len(A_sl) == 1:
    print(len(A))
elif len(A_sl) == 2:
    A_sl.sort()
    if A_sl[1] - A_sl[0] <= 2:
        print(len(A))
    else:
        count_l = A.count(A_sl[1])
        count_s = A.count(A_sl[0])
        print(max(count_l,count_s)) 
else:
    for i in range(min(A) + 1,max(A)):
        count = A.count(i-1) + A.count(i) + A.count(i+1)
        if count > ans:
            ans = count
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
l = [0]*(10**5)
for e in A:
    if e == 0:
        l[0] += 1
        l[1] += 1
    elif e == 99999:
        l[99999] += 1
        l[99998] += 1
    else:
        l[e-1] += 1
        l[e] += 1
        l[e+1] += 1
print(max(l))