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

s = input()
t = input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
word = [[""]*(len(t)+1) for _ in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
            word[i+1][j+1] += word[i][j] + s[i]
        else:
            dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])
            if dp[i+1][j]>dp[i][j+1]:
                word[i+1][j+1] = word[i+1][j]
            else:
                word[i+1][j+1] = word[i][j+1]


print(word[-1][-1])

### FIXED CODE ###

s = input()
t = input()

x = len(s)
y = len(t)
dp = [[0]*(y+1) for _ in range(x+1)]

for i in range(x):
    for j in range(y):
        if s[i]==t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])

res = ""
while x>0 and y>0:
    if dp[x][y] == dp[x-1][y]:
        x -= 1
    elif dp[x][y] == dp[x][y-1]:
        y -= 1
    else:
        res = s[x-1] + res
        x -= 1
        y -= 1
print(res)
### BUGGY CODE ###

n, a, b = map(int, input().split())
ans = 2 ** n -1
val = 1
val2 = 1
for i in range(a):
    val *= n - i
    val2 *= i + 1
ans -= (val // val2)
val = 1
val2 = 1
for i in range(b):
    val *= n - i
    val2 *= i + 1
ans -= (val // val2)
print(ans % (int(1e9) + 7))

### FIXED CODE ###

n, a, b = map(int, input().split())
m = int(1e9) + 7
ans = (pow(2, n, m) -1) % m
val = 1
val2 = 1
for i in range(a):
    val = (val * (n - i)) % m
    val2 = (val2 * (i + 1)) % m
ans -= ((val % m) * (pow(val2, m-2, m)))
#print(((val % m) * (pow(val2, m-2, m))))
ans %= m
val = 1
val2 = 1
for i in range(b):
    val = (val * (n - i)) % m
    val2 = (val2 * (i + 1)) % m
ans -= ((val % m) * (pow(val2, m-2, m)))
#print(((val % m) * (pow(val2, m-2, m))))
print(ans % (int(1e9) + 7))
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
cx, cy = map(lambda x: int(x) - 1, input().split())
dx, dy = map(lambda x: int(x) - 1, input().split())
s = [input() for _ in range(h)]
c = [[10**6] * w for _ in range(h)]


def bfs():
    d = ((1, 0), (-1, 0), (0, 1), (0, -1))
    q = deque([(cx, cy)])

    c[cx][cy] = 0

    while q:
        x, y = q.pop()
        cp = c[x][y]
        if (x, y) == (dx, dy):
            c[x][y] = cp
            break
        for i, j in d:
            nx = x + i
            ny = y + j
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                    ny] > cp:
                q.append((nx, ny))
                c[nx][ny] = cp
        cp += 1
        for i in range(-2, 3):
            for j in range(-2, 3):
                nx = x + i
                ny = y + j
                if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                        ny] > cp:
                    c[nx][ny] = cp
                    q.appendleft((nx, ny))

    return -1 * (c[dx][dy] == 10**6) or c[dx][dy]


print(bfs())


### FIXED CODE ###

#!/usr/bin/env python3
import heapq

h, w = map(int, input().split())
cx, cy = map(lambda x: int(x) - 1, input().split())
dx, dy = map(lambda x: int(x) - 1, input().split())
s = [input() for _ in range(h)]
c = [[10**6] * w for _ in range(h)]


def bfs():
    d = ((1, 0), (-1, 0), (0, 1), (0, -1))
    d2 = (
        (-2, -2),
        (-2, -1),
        (-2, 0),
        (-2, 1),
        (-2, 2),
        (-1, -2),
        (-1, -1),
        (-1, 1),
        (-1, 2),
        (0, -2),
        (0, 2),
        (1, -2),
        (1, -1),
        (1, 1),
        (1, 2),
        (2, -2),
        (2, -1),
        (2, 0),
        (2, 1),
        (2, 2),
    )
    hp = []

    heapq.heappush(hp, (0, (cx, cy)))
    c[cx][cy] = 0

    while hp:
        cp, (
            x,
            y,
        ) = heapq.heappop(hp)
        if (x, y) == (dx, dy):
            c[x][y] = cp
            break
        for i in range(4):
            nx = x + d[i][0]
            ny = y + d[i][1]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                    ny] > cp:
                heapq.heappush(hp, (cp, (nx, ny)))
                c[nx][ny] = cp
        cp += 1
        for i in range(20):
            nx = x + d2[i][0]
            ny = y + d2[i][1]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                    ny] > cp:
                c[nx][ny] = cp
                heapq.heappush(hp, (cp, (nx, ny)))

    return c[dx][dy] if c[dx][dy] < 10**6 else -1


print(bfs())
### BUGGY CODE ###

R,G,B,N = [int(i) for i in input().split()]
num = 0

box = sorted([R,G,B], key=lambda x:-x)
nums = [N//b for b in box]
for i in range(nums[0]+1):
    if (nums[0]-i)*box[0] + nums[1]*box[1] + nums[2]*box[2] < N:
        break
    for j in range(nums[1]+1):
        resj = (nums[0]-i)*box[0] + (nums[1]-j)*box[1]
        if resj + nums[2]*box[2] < N:
            break
        if resj > N:
            continue
        if (N-resj)%box[2]!=0:
            continue
        num += 1

print(num)

### FIXED CODE ###

R,G,B,N = [int(i) for i in input().split()]
num = 0
box = sorted([R,G,B], key=lambda x:-x)
nums = [N//b for b in box]
for i in range(nums[0]+1):
    if (nums[0]-i)*box[0] + nums[1]*box[1] + nums[2]*box[2] < N:
        break
    for j in range(nums[1]+1):
        resj = (nums[0]-i)*box[0] + (nums[1]-j)*box[1]
        if resj + nums[2]*box[2] < N:
            break
        if resj > N:
            continue
        if (N-resj)%box[2]!=0:
            continue
        num += 1
print(num)
### BUGGY CODE ###

N = int, input().split()
S = input()
res = 10 ** 9
for i in range(len(S)):
    tmp = S[:i].count("W") + S[i+1:].count("E")
    res = tmp if tmp < res else res
print(res)


### FIXED CODE ###

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

e = S.count("E")
w = 0
res = e
for i, s in enumerate(S):
    if s == "E":
        e -= 1
    tmp = e + w
    res = tmp if tmp < res else res
    if s == "W":
        w += 1
print(res)
### BUGGY CODE ###

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


def main():

    N, K = [int(i) for i in input().strip().split()]
    hights = [int(i) for i in input().strip().split()]
    min_costs = [float("inf")] * N
    min_costs[0] = 0

    for i in range(N):
        for j in range(1, K+1):
            if j <= i:
                min_costs[i] = min(
                    min_costs[i - j] + abs(hights[i] - hights[i - j]), min_costs[i])
    return min_costs[-1]


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

class Solver():
    def __init__(self, N, costs, K):
        self.dp = [99999999999] * N
        self.dp[0] = 0
        self.K = K
        self.costs = costs

    def solve(self):
        for i in range(0, len(self.costs)):
            for k in range(1, self.K + 1):
                if i >= k:
                    self.dp[i] = min(
                        self.dp[i - k] + abs(self.costs[i] - self.costs[i-k]), self.dp[i])
        return self.dp[-1]


def main():
    N, K = [int(i) for i in input().split()]
    costs = [int(i) for i in input().split()]
    solver = Solver(N, costs, K)
    print(solver.solve())


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

n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
for _ in range(n):
    if len(a)<2:
        break
    else:
        bi=format(a[0], 'b')
        x=2**len(bi)-a[0]
        if x==a[0] and a.count(x)>1:
            ans+=1
            a.remove(x)
            a.remove(x)
            continue
        elif x in a and x!=a[0]:
            ans+=1
            a.remove(x)
        a.pop(0)
print(ans)


### FIXED CODE ###

import collections
import bisect
n= int(input())
a=list(map(int, input().split()))
c=collections.Counter(a)
ans=0
des=sorted(a,reverse=True)
# asc=sorted(a)

for i in des:
    if c[i]>0:
        bi=format(i, 'b')
        x=2**len(bi)-i
        c[i]-=1
        if c[x]>0:
            c[x]-=1
            ans+=1
print(ans)
### BUGGY CODE ###

h, w, m = map(int, input().split())
h_l = [[] for i in range(h + 1)]
w_l = [[] for i in range(w + 1)]
max_h = 0
max_h_l = []
max_w = 0
max_w_l = []
for _ in range(m):
    h, w = map(int, input().split())
    if h_l[h] :
        h_l[h][1].append(w)
        h_l[h][0] += 1
    else:
        h_l[h] = [1, [w]]
        
    if h_l[h][0] > max_h:
        max_h_l = [h]
        max_h = h_l[h][0]
    if h_l[h][0] == max_h:
        max_h_l.append(h)
            

        
    if w_l[w]:
        w_l[w][1].append(h)
        w_l[w][0] += 1
    else:
        w_l[w] = [1, [h]]
    if w_l[w][0] > max_w:
        max_w_l = [w]
        max_w = w_l[w][0]
    if w_l[w][0] == max_w:
        max_w_l.append(w)


flag = 0
ans = 0
for i in max_h_l:
    if flag == 1:
        break
    for j in max_w_l:
        if flag == 1:
            break
        if j in h_l[i][1]:
            ans = max_h + max_w - 1
        else:
            ans = max_h + max_w
            flag = 1
print(ans)

### FIXED CODE ###

h, w, m = map(int, input().split())
h_l = [[] for i in range(h + 1)]
w_l = [[] for i in range(w + 1)]
max_h = 0
max_h_l = []
max_w = 0
max_w_l = []
inputs = {}
for _ in range(m):
    h, w = map(int, input().split())
    inputs.setdefault(h, set([w]))
    inputs[h].add(w)

    if h_l[h] :
        h_l[h][1].add(w)
        h_l[h][0] += 1
    else:
        h_l[h] = [1, set([w])]
        
    if h_l[h][0] > max_h:
        max_h_l = [h]
        max_h = h_l[h][0]
    elif h_l[h][0] == max_h:
        max_h_l.append(h)
 
        
    if w_l[w]:
        w_l[w][1].add(h)
        w_l[w][0] += 1
    else:
        w_l[w] = [1, set([h])]
    if w_l[w][0] > max_w:
        max_w_l = [w]
        max_w = w_l[w][0]
    elif w_l[w][0] == max_w:
        max_w_l.append(w)

ans = max_h + max_w -1
flag = 0
for i in max_h_l:
    if flag == 1:
        break
    for j in max_w_l:
        if j not in inputs[i]:
            ans = max_h + max_w
            flag = 1
            break
        
print(ans)
### BUGGY CODE ###

s=input()
q=int(input())

rev=1
for i in range(q):
    qu=input()
    if qu=="1":
        rev=-rev
    else:
        t,f,c=qu.split()
        if f=="1" and rev==1:
            s=c+s
#            print(s)
        elif f=="2" and rev==1:
            s=s+c
#            print(s)
        elif f=="1" and rev==-1:
            s=s+c
#            print(s)
        elif f=="2" and rev==-1:
            s=c+s
#            print(s)
if rev==-1:
    s=s[::-1]
#    print(s)
print(s)       

### FIXED CODE ###

s=input()
q=int(input())

sb=""
sa=""
rev=1
for i in range(q):
    qu=input()
    if qu=="1":
        rev=-rev
    else:
        t,f,c=qu.split()
        if f=="1" and rev==1:
#            s=c+s
            sb=c+sb
#            print(s)
        elif f=="2" and rev==1:
#            s=s+c
            sa=sa+c
#            print(s)
        elif f=="1" and rev==-1:
#            s=s+c
            sa=sa+c
#            print(s)
        elif f=="2" and rev==-1:
#            s=c+s
            sb=c+sb
#            print(s)
s=sb+s+sa
if rev==-1:
    s=s[::-1]
#    print(s)
print(s)
### BUGGY CODE ###

import itertools
n,k=map(int,input().split())
p=list(map(int,input().split()))
s=[]
for i in range(len(p)-k+1):
  t=p[i:i+k]
  s.append(t)
#print(s)
ans=0
for i in range(len(s)):
  sums=0
  for j in range(k):
    sums+=(s[i][j]+1)*s[i][j]/2/s[i][j]
  #print(sums)
  ans=max(ans,sums)
print('{:.10f}'.format(ans))

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
s=[]
for i in p:
  t=(1+i)
  s.append(t)
  
t=[0,]
for i in range(n):
  u=t[i]+s[i]
  t.append(u)

ans=0
for i in range(n-k+1):
  ans=max(ans,t[i+k]-t[i])
  

print('{:.10f}'.format(ans/2))
### BUGGY CODE ###

n=int(input())
s=input()
l=[]
for i in range(n):
  x=s[:i].count('W')+s[i+1:].count('E')
  l.append(x)
print(min(l))

### FIXED CODE ###

n=int(input())
s=input()
lw=0
re=s.count('E')
l=[]
for i in range(n):
  if s[i]=='W':
    x=lw+re
    lw+=1
  else:
    x=lw+(re-1)
    re-=1
  l.append(x)
print(min(l))
### BUGGY CODE ###

N=int(input())
A=input().split(" ")
for i in range(N):
   A[i]=int(A[i])

import fractions
from functools import reduce

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


ans=0
GCD_target=gcd_list(A)

for i in range(N):
   copied_A = A[:]
   copied_A.pop(i)
   GCD_current=gcd_list(copied_A)
   ans=max(ans,GCD_current)

print(ans)

### FIXED CODE ###

from fractions import *
n = int(input())
a = [0]+list(map(int, input().split()))+[0]
b = [0]*(n+2)
c = [0]*(n+2)
for i in range(1, n+1):
	b[i] = gcd(b[i-1], a[i])
for i in range(n, 0, -1):
	c[i] = gcd(c[i+1], a[i])

ans=1
for i in range(1, n+1):
    x1 = b[i-1]
    x2 = c[i+1]
    ans=max(ans, gcd(x1, x2))

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

n, m, s = map(int, input().split())
uvab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(n)]


import math

M = 50 * n + 1
s = min(s, M - 1)

dp = [[float('inf')] * M for _ in range(n)]

dp[0][s] = 0
c, d = cd[0][0], cd[0][1]
for jj in range(M):
    dp[0][jj] = min(dp[0][jj], dp[0][s] + max(math.ceil((jj - s) / c), 0) * d)

while True:
    flag = False

    for i in range(m):
        u1, v1, a, b = uvab[i][0] - 1, uvab[i][1] - 1, uvab[i][2], uvab[i][3]
        for u, v in [(u1, v1), (v1, u1)]:
            for j in range(M - a):
                tmp = dp[u][j + a] + b
                if tmp < dp[v][j]:
                    dp[v][j] = tmp
                    flag = True

            c, d = cd[v][0], cd[v][1]
            for jj in range(c, M):
                tmp = dp[v][jj - c] + d
                if tmp < dp[v][jj]:
                    dp[v][jj] = tmp
                    flag = True

    if flag == False:
        break

for t in range(1, n):
    print(min(dp[t]))


### FIXED CODE ###

n, m, s = map(int, input().split())
uvab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(n)]


import math

M = 50 * n + 1
s = min(s, M - 1)

dp = [[float('inf')] * M for _ in range(n)]

dp[0][s] = 0
c, d = cd[0][0], cd[0][1]
for jj in range(M):
    dp[0][jj] = min(dp[0][jj], dp[0][s] + max(math.ceil((jj - s) / c), 0) * d)

while True:
    flag = False

    for i in range(m):
        u1, v1, a, b = uvab[i][0] - 1, uvab[i][1] - 1, uvab[i][2], uvab[i][3]
        for u, v in [(u1, v1), (v1, u1)]:
            for j in range(M - a):
                tmp = dp[u][j + a] + b
                if tmp < dp[v][j]:
                    dp[v][j] = tmp
                    flag = True

            c, d = cd[v][0], cd[v][1]
            for jj in range(c, M):
                tmp = dp[v][jj - c] + d
                if tmp < dp[v][jj]:
                    dp[v][jj] = tmp
                    flag = True

    if flag == False:
        break

for t in range(1, n):
    print(min(dp[t]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))

    A.sort()
    F.sort(reverse=True)
    r = A[-1]*F[0]
    l = -1
    while(r-l > 1):
        tmp = (l+r)//2
        k = 0
        for x, y in zip(A, F):
            if x*y > tmp:
                k += x - (tmp // y)
            #k += max(0, x - (tmp // y))
        if K >= k:
            r = tmp
        else:
            l = tmp
    print(r)
main()


### FIXED CODE ###

import sys
import bisect
import math
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse=True)

B = [(A[i]*F[i], F[i]) for i in range(N)]
B.sort(reverse=True)
L = 0
R = B[0][0]
if sum(A) <= K:
    print(0)
    exit(0)
while(1):
    ans = (L+R) // 2
    flag = True
    tmp = 0
    for i in range(N):
        tmp += math.ceil(max(B[i][0] - ans, 0) / B[i][1])
        if tmp > K:
            flag = False
            break
    if flag:
        R = ans
    else:
        L = ans
    if L == R or L+1 == R:
        print(R)
        break
### BUGGY CODE ###

#!/usr/bin/env python3

import math
import numpy as np

n = int(input().split()[0])
a_list = list(map(int, input().split()))


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


a_list = sorted(a_list)
max_comb = -float("inf")

for i, ai in enumerate(a_list):
    # aiを固定する
    # aiが偶数の場合は、ai/2、
    # aiが奇数の場合は、(ai-1)/2または(ai+1)/2に
    # 一番近い値が答えになる
    if ai % 2 == 0:
        idx = np.abs(np.asarray(a_list) - ai // 2).argmin()
        aj = a_list[idx]
    else:
        target_1 = (ai - 1) // 2
        idx_1 = np.abs(np.asarray(a_list) - target_1).argmin()
        aj = a_list[idx_1]
        target_2 = (ai + 1) // 2
        idx_2 = np.abs(np.asarray(a_list) - target_2).argmin()

        if abs(a_list[idx_1] - target_1) > abs(a_list[idx_2] - target_2):
            aj = a_list[idx_2]

    comb = C(ai, aj)
    if max_comb < comb:
        max_comb = comb
        comb_set = (ai, aj)

ans = "{} {}".format(ai, aj)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

import math
import bisect
import numpy as np

n = int(input().split()[0])
a_list = list(map(int, input().split()))


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


a_list = sorted(a_list)
max_comb = -float("inf")
a_list = sorted(a_list, reverse=True)
ai = a_list[0]
w_list = a_list[1:]
w_list = sorted(w_list)

# 真ん中に一番近い値を取得する
if ai % 2 == 0:
    idx = np.abs(np.asarray(w_list) - ai // 2).argmin()
    aj = w_list[idx]
else:
    t_1 = (ai - 1) // 2
    idx_1 = np.abs(np.asarray(w_list) - t_1).argmin()
    aj_1 = w_list[idx_1]

    t_2 = (ai + 1) // 2
    idx_2 = np.abs(np.asarray(w_list) - t_2).argmin()
    aj_2 = w_list[idx_2]

    if abs(t_1 - aj_1) < abs(t_2 - aj_2):
        aj = aj_1
    else:
        aj = aj_2

ans = "{} {}".format(ai, aj)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)


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


n = int(input())
aa = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

dp = [10 ** 18] * (n + 10)
dp[0] = 0
ans1 = [0] * n
ans2 = [0] * n


def dfs(i=0, r=-1):
    global dp, ans1, ans2
    mi = 0
    ma = n
    while mi != ma:
        mm = (mi + ma) // 2
        if dp[mm] >= aa[i]:
            ma = mm
        else:
            mi = mm + 1

    be = dp[mi]
    dp[mi] = min(dp[mi], aa[i])
    ans1[i] = mi
    ans2[i] = max(ans1[i], ans2[r])

    for j in e[i]:
        if j == r:
            continue
        dfs(j, i)

    dp[mi] = be


dfs()
for i in ans2:
    print(i)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)


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


n = int(input())
aa = {}
for j,i in enumerate(map(int,input().split())):
    if i in aa:
        aa[i].append(j)
    else:
        aa[i] = [j]
a = [0] * n
for k,i in enumerate(sorted(list(aa))):
    for j in aa[i]:
        a[j] = k+1


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r):
        l += self.n
        r += self.n
        s = self.one
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.b[r - 1])
            if l & 1:
                s = self.func(s, self.b[r - 1])
                l += 1
            l >>= 1
            r >>= 1
        return s


e = [[] for _ in range(n)]
for _ in range(n - 1):
    aa, bb = [int(i) - 1 for i in input().split()]
    e[aa].append(bb)
    e[bb].append(aa)
seg = SegmentTree([0] * (max(a)+2), max, 0)
ans1 = [0] * n
ans1[0] = 1
ans2 = [0] * n
ans2[0] = 1


def dfs(i=0, r=-1):

    y = seg.get_segment(0, a[i])
    ans1[i] = y + 1
    ans2[i] = max(ans2[r], ans1[i])

    be = seg.get_item(a[i])
    seg.update_func(a[i], ans1[i])
    for j in e[i]:
        if j == r:
            continue
        dfs(j, i)
    seg.update(a[i], be)


dfs()
print("\n".join(map(str,(ans2))))
### BUGGY CODE ###

k = int(input())
import math
ans = 0
for i in range(1,k+1):
  for j in range(1,k+1):
    for x in range(1,k+1):
      ans += math.gcd(i,math.gcd(j,x))
print(ans)

### FIXED CODE ###

import math
 
k = int(input()) + 1
ans = 0
 
for a in range(1, k):
    for b in range(1, k):
        d = math.gcd(a, b)
        for c in range(1, k):
            ans += math.gcd(d, c)
 
print(ans)
### BUGGY CODE ###

a,b = map(int, input().split())
s = max(a, b)

for i in range(s, a*b+1):
    if i % a  == 0 and  i % b == 0:
        break

print(i)

### FIXED CODE ###

a,b = map(int, input().split())
s = max(a, b)

for i in range(s, a*b+1, s):
    if i % a  == 0 and  i % b == 0:
        break

print(i)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    h,w = map(int,input().split())
    l = [list(input()) for i in range(h)]

    c = [[[-1]*2 for i in range(w)] for i in range(h)]

    def count(x,y):

        if c[x][y][0] == -1:
            n = 0
            while x+n < h and l[x+n][y] == ".":
                c[x+n][y][0] = 1
                n += 1
            c[x][y][0] = n
        elif c[x][y][0] == 1:
            c[x][y][0] = c[x-1][y][0]
            
        if c[x][y][1] == -1:
            n = 0
            while y+n < w and l[x][y+n] == ".":
                c[x][y+n][1] = 1
                n += 1
            c[x][y][1] = n
        elif c[x][y][1] == 1:
            c[x][y][1] = c[x][y-1][1]


        return c[x][y][0]+c[x][y][1]-1
    ans = 0
    for i in range(h):
        for j in range(w):
            if l[i][j] == ".":
                ans = max(ans,count(i,j))
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###


h,w = map(int,input().split())
l = [list(input()) for i in range(h)]

c1 = [[-1 for i in range(w)] for i in range(h)]
c2 = [[-1 for i in range(w)] for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if c1[i][j] == -1:
            n = 0
            while i+n < h:
                if l[i+n][j] == ".":
                    n += 1
                else:
                    break
            for k in range(n):
                c1[i+k][j] = n
            
        if c2[i][j] == -1:
            n = 0
            while j+n < w:
                if l[i][j+n] == ".":
                    n += 1
                else:
                    break
            for k in range(n):
                c2[i][j+k] = n


        ans = max(ans,c1[i][j]+c2[i][j])
print(ans-1)
### BUGGY CODE ###

def main():
    n,k = map(int,input().split())
    while 1:
        check = abs(n-k)
        if n < check:
            break
        else:
            n = check
    print(n)
if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n,k = map(int,input().split())
    div = n//k
    A = abs(n-k*div)
    B = abs(n-k*(div+1))
    if A < B:
        x = A
    else:
        x = B
    print(x)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
mod=10**9+7
s=sum(A)
ans=0
for a in A:
    ans += a*(s-a)
print((ans//2)%mod)