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

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

#output
import math

A.sort()
mod = 10**9+7

def cmb(n, r):
    if n < r: return 0
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

M = 0
m = 0
for i, a in enumerate(A):
    M += cmb(i, K-1) * a
    m += cmb(N-i-1, K-1) * a
    M %= mod
    m %= mod

print((M-m) % mod)

### FIXED CODE ###

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

#output
import math

A.sort()
mod = 10**9+7

n_ = 10**5 + 3
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod
#これだとTLE!
"""
def cmb(n, r):
    if n < r: return 0
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
"""

M = 0
m = 0
for i, a in enumerate(A):
    M += cmb(i, K-1) * a
    m += cmb(N-i-1, K-1) * a
    M %= mod
    m %= mod

print((M-m) % mod)
### BUGGY CODE ###

from collections import Counter

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

l_sum = []
s= 0
for i in range(n):
    s += a[i]
    l_sum.append(s)

ans = 0
for i in range(n):
    if l_sum[i] == 0:
        ans += 1
    for j in range(i+1, n):
        if l_sum[i] == l_sum[j]:
            ans += 1

print(ans)

### FIXED CODE ###

from collections import Counter

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

l_sum = [0]
s= 0
for i in range(n):
    s += a[i]
    l_sum.append(s)

c_sum = Counter(l_sum)

# print(c_sum)
ans = 0
for i in c_sum:
    if c_sum[i] > 1:
        ans += c_sum[i] * (c_sum[i] - 1) // 2

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

N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
BC = [[int(x) for x in input().split()]for i in range(Q)]

Sum = sum(A)
for i in range(Q):
  b = BC[i][0]
  c = BC[i][1]
  Sum += (c-b)*A.count(b)
  print(Sum)
  A = [c if i == b else i for i in A]


### FIXED CODE ###

import collections
N = int(input())
a = [int(x) for x in input().split()]
aa = collections.Counter(a)
A = list(aa.items())
Alisted = [0]*(10**5+1)
for i in range(len(A)):
  Alisted[A[i][0]] = A[i][1]
Q = int(input())
BC = [[int(x) for x in input().split()]for i in range(Q)]

Sum = sum(a)
for i in range(Q):
  b = BC[i][0]
  c = BC[i][1]
  num = Alisted[b]
  Sum += (c-b)*num
  print(Sum)
  Alisted[b]=0
  Alisted[c]+=num
### BUGGY CODE ###

import re
N = int(input())
S = input()
cnt = 0

for i in range(1000):
    str_i = '{:03}'.format(i)
    found = 0
    for s in S:
        if(s==str_i[found]):
            found += 1
            if(found == 3):
                cnt += 1
                break
print(cnt)      

### FIXED CODE ###

N = int(input())
S = input()
cnt = 0

for i in range(1000):
    str_i = '{:03}'.format(i)
    found = 0
    for s in S:
        if(s==str_i[found]):
            found += 1
            if(found == 3):
                cnt += 1
                break
print(cnt)
### BUGGY CODE ###

# Disjoint Set: Union Find Tree
[p, rank, d] = [[], [], []]
w = {}

def makeSet(x):
    global p, rank, w
    p.append(x)
    rank.append(0)

def findSet(x):
    global p
    if x != p[x]:
        p[x] = findSet(p[x])
    return p[x]

def link(x, y):
    global p, rank
    if rank[x] > rank[y]:
        p[y] = x
    else:
        p[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1

def relate(x, y, z):
    global w
    w[(x, y)] = z
    union(x, y)

def cost(x, y, n, total):
    global w, d
    for i in range(n):
        if ((x, i) in w.keys()) == True and d[i] == 0:
            d[i] = 1
            if i == y:
                total += w[(x, i)]
                return total
            result = cost(i, y, n, total)
            if result != None:
                total = result + w[(x, i)]
                return total     

        if ((i, x) in w.keys()) == True and d[i] == 0:
            d[i] = 1
            if i == y:
                total -= w[(i, x)]
                return total
            result = cost(i, y, n, total)
            if result != None:
                total = result - w[(i, x)]
                return total

def diff(x, y, n):
    if same(x, y) == 1:
        global d
        total = 0
        d = [0 for i in range(n)]
        d[x] = 1
        return cost(x, y, n, total)
    else:
        return "?"     

def union(x, y):
    link(findSet(x), findSet(y))    

def same(x, y):
    if findSet(x) == findSet(y):
        return 1
    else:
        return 0   

[n, q] = list(map(int, input().split()))
for i in range(n):
    makeSet(i)
'''
print(p)
print(rank)
print(w)
print("\n")
'''

for i in range(q):
    data = list(map(int, input().split()))
    if data[0] == 0:
        relate(data[1], data[2], data[3])
    else:
        print(diff(data[1], data[2], n))
    '''
    print("\n")
    print(p)
    print(rank)
    print(w)
    print("\n")
    '''


### FIXED CODE ###

# Disjoint Set: Union Find Trees
[p, rank] = [[], []]
[n, q] = list(map(int, input().split()))
w = [0 for i in range(n)]

def makeSet(x):
    global p, rank
    p.append(x)
    rank.append(0)

def findSet(x):
    global p
    if x != p[x]:
        pre_parent = p[x]
        p[x] = findSet(p[x])
        w[x] += w[pre_parent]
    return p[x]

def link(x, y, z):
    global p, rank, w
    if rank[x] > rank[y]:
        p[y] = x
        w[y] = z
    else:
        p[x] = y
        w[x] = -z
        if rank[x] == rank[y]:
            rank[y] += 1

def same(x, y):
    if findSet(x) == findSet(y):
        return 1
    else:
        return 0   

def relate(x, y, z):
    global w
    root_x = findSet(x)
    root_y = findSet(y)
    z += w[x]
    z -= w[y]
    link(root_x, root_y, z)
   
def diff(x, y):
    if same(x, y) == 1:
        global w
        return w[y] - w[x]
    else:
        return "?"     

for i in range(n):
    makeSet(i)

for i in range(q):
    data = list(map(int, input().split()))
    if data[0] == 0:
        relate(data[1], data[2], data[3])
    else:
        print(diff(data[1], data[2]))
### BUGGY CODE ###

if __name__ == '__main__':
    N = int(input())
    L = list(map(int, input().split()))
    res = 0
    for i, li in enumerate(L[:-2]):
        for j, lj in enumerate(L[i+1:-1]):
            sub = abs(li-lj)
            res += sum(sub < lk < li+lj for lk in L[i+j+2:])
    print(res)



### FIXED CODE ###

import bisect


if __name__ == '__main__':
    N = int(input())
    L = sorted(list(map(int, input().split())))
    ans = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            ans += bisect.bisect_left(L, L[i]+L[j])-j-1
    print(ans)
### BUGGY CODE ###

# seishin.py
N = int(input())
MOD = 10**9 + 7

fact = [1]*(N+1)

for i in range(1, N+1):
    fact[i] = r = i*fact[i-1] % MOD

ans = cnt = 0
for K in range((N+1)//2, N):
    res = fact[K]*fact[K-1]*pow(fact[2*K-N], MOD-2, MOD) % MOD
    ans += (res - cnt) * K % MOD
    cnt = res
    ans %= MOD
print(ans)


### FIXED CODE ###

# seishin.py
N = int(input())
MOD = 10**9 + 7

fact = [1]*(N+1)
rfact = [1]*(N+1)

for i in range(1, N+1):
    fact[i] = r = i*fact[i-1] % MOD
    rfact[i] = pow(r, MOD-2, MOD)

ans = cnt = 0
for K in range((N+1)//2, N):
    res = fact[K]*fact[K-1]*rfact[2*K-N] % MOD
    ans += (res - cnt) * K % MOD
    cnt = res
    ans %= MOD
print(ans)
### BUGGY CODE ###

T = input()
result = ""

for number, letter in zip(range(len(T)) ,T):
  if letter == "?":
    """
    # 最初の文字が?の時.
    if number == 0:
      result += "P"
    elif number == len(T) - 1:
      result += "D"
    # 一つ前の文字が"D"の時.
    elif result[number - 1] == "D":
      result += "P"
    # 一つ前の文字が"P"の時.
    elif result[number - 1] == "P":
      result += "D"
    """
    result += "D"
  else:
    result += letter

print(result)

### FIXED CODE ###

T = input()
print(T.replace("?", "D"))
### BUGGY CODE ###

N = int(input())

intSum = 0
for i in range(N):
    intSum = intSum + i

print(intSum)

### FIXED CODE ###

N = int(input())
count = int( (N-1) / 2 )

if (N-1) % 2 == 0:
    intSum = N*count
else:
    intSum = N*count + count + 1

print(intSum)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
S = [[]for i in range(N)]
for i in range(M):
    u,v = map(int,input().split())
    S[u-1].append(v-1)
St,T = map(int,input().split())

D = [[float('inf')]*3 for i in range(N)]
D[St-1][0] = 0
queue = [St-1]
hoge = [0]*N
i = 0
while queue != []:
    i += 1
    l = 0
    for q in queue:
        for s in S[q]:
            if D[s][i%3] > i:
                D[s][i%3] = i
                if not s in hoge[:l]:
                    hoge[l] = s
                    l += 1
    queue = hoge[:l]
    if D[T-1][0] != float('inf'):
        break
if D[T-1][0] == float('inf'):
    print(-1)
else:
    print(D[T-1][0]//3)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
S = [[]for i in range(N)]
for i in range(M):
    u,v = map(int,input().split())
    S[u-1].append(v-1)
St,T = map(int,input().split())

D = [[float('inf')]*3 for i in range(N)]
D[St-1][0] = 0
queue = [St-1]
i = 0
while queue != []:
    i += 1
    hoge = []
    for q in queue:
        for s in S[q]:
            if D[s][i%3] > i:
                D[s][i%3] = i
                if not s in hoge:
                    hoge.append(s)
    queue = hoge[:]
    if D[T-1][0] != float('inf'):
        break
if D[T-1][0] == float('inf'):
    print(-1)
else:
    print(D[T-1][0]//3)
### BUGGY CODE ###

N = int(input())
Alist = [int(input()) for _ in range(N)]

for i in range(N):
    print(max(Alist[:i] + Alist[i+1:]))


### FIXED CODE ###

N = int(input())
Alist = [int(input()) for _ in range(N)]
Alist_sorted = sorted(Alist)

m = max(Alist)
for i in range(N):
    if Alist[i]==m:
        print(Alist_sorted[-2])
    else:
        print(m)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
E = []
for i in range(M):
    a, b = map(int, input().split())
    E.append((a-1, b-1))

tree = {n: n for n in range(N)}
child = {n: 1 for n in range(N)}

max_connection = N*(N-1)//2


def find_head(i):
    if tree[i] != i:
        return find_head(tree[i])
    else:
        return i


connection = 0
out_list = [max_connection]
for e in E[:0:-1]:
    head_e0 = find_head(e[0])
    head_e1 = find_head(e[1])

    if head_e0 == head_e1:
        out_list.append(max_connection-connection)
    else:
        tree[head_e1] = head_e0
        connection = connection + child[head_e0]*child[head_e1]
        child[head_e0] += child[head_e1]
        out_list.append(max_connection - connection)
    if max_connection == connection:
        break

if len(out_list) != M:
    out_list += [0]*(M-len(out_list))

for o in out_list[::-1]:
    print(o)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
E = []
for i in range(M):
    a, b = map(int, input().split())
    E.append((a-1, b-1))

tree = {n: n for n in range(N)}
child = {n: 1 for n in range(N)}

max_connection = N*(N-1)//2


def find_head(i):
    if tree[i] != i:
        tree[i] = find_head(tree[i])
        return tree[i]
    else:
        return i


connection = 0
out_list = [max_connection]
for e in E[:0:-1]:
    head_e0 = find_head(e[0])
    head_e1 = find_head(e[1])

    if head_e0 == head_e1:
        out_list.append(max_connection-connection)
    else:
        tree[head_e1] = head_e0
        connection = connection + child[head_e0]*child[head_e1]
        child[head_e0] += child[head_e1]
        out_list.append(max_connection - connection)
    if max_connection == connection:
        break

if len(out_list) != M:
    out_list += [0]*(M-len(out_list))

for o in out_list[::-1]:
    print(o)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
import numpy as np
from operator import itemgetter

def main():
    N,M = map(int,input().split())
    root = [list(map(int,input().split())) for _ in range(M)]
    
    root.sort(key=itemgetter(0))
    d = [10**18 for _ in range(N)]
    d[0] = 0
    d = np.array(d)
    for l,r,c in root:
        if d[l-1] == 10**18:
            print(-1)
            exit()
        else:
            d[l:r] = np.minimum(d[l:r],d[l-1]+c)
            
    print(d[-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
import heapq

def main():
    N,M = map(int,input().split())
    INF = 10**15
    root = [[] for _ in range(N)]
    for i in range(N-1):
        root[i+1].append((0,i))
    for _ in range(M):
        l,r,c = map(int,input().split())
        root[l-1].append((c,r-1))
    
    dist = [INF for _ in range(N)]
    q = [(0,0)]
    dist[0] = 0
    while q:
        d,now = heapq.heappop(q)
        if dist[now] < d:
            continue
        for cost,fol in root[now]:
            _d = d+cost
            if dist[fol] > _d:
                dist[fol] = _d
                heapq.heappush(q,(_d,fol))

    if dist[-1] == INF:
        print(-1)
    else:
        print(dist[-1])

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

def main():
    import sys
    input = sys.stdin.readline
    from fractions import gcd
    a = int(input())
    l = list(map(int,input().split()))



    def lcm(a,b):
        return a*b//gcd(a,b)

    MOD = 10**9+7
    ans = 0
    t = 1
    for i in l:
        t = lcm(t,i)

    for i in l:
        ans +=t//i
        ans %=MOD
    print(ans)
main()

### FIXED CODE ###

def main():
    from fractions import gcd
    a = int(input())
    l = list(map(int,input().split()))



    def lcm(a,b):
        return a*b//gcd(a,b)
    A= 1
    MOD = 10**9+7
    ans = 0
    t = 1
    for i in l:
        t = t* i //gcd(t,i)
    for i in l:
        ans +=t//i
    ans %=MOD
    print(ans)
main()
### BUGGY CODE ###

import math
N, K = map(int, input().split())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return int(r <= K)

if __name__ == '__main__':
    min_i, max_i = 0, max(Cs)+1
    index = (max_i + min_i)//2
    while True:
        if not func(index):
            if func(index+1):
                print(index+1)
                break
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1


### FIXED CODE ###

import math
N, K = map(int, input().split())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return r <= K

if __name__ == '__main__':
    min_i, max_i, index = 0, max(Cs)+1, 1
    while True:
        if func(index):
            index, max_i = (index-1 + min_i)//2, index-1
        else:
            index, min_i = (index+1 + max_i)//2, index+1
        if min_i > max_i:
            print(min_i)
            break
### BUGGY CODE ###

N = int(input())
*a,= map(int, input().split())
def without(a,k):
  return a[0:k]+a[k+1:]

def sames(x):
  x=sorted(x)
  count=0
  for i in range(len(x)):
    ch=x[i]
    for j in range(i+1,len(x)):
      if x[j]!=ch:
        break
      else:
        count+=1
  return count

for k in range(N):
  print(sames(without(a,k)))

### FIXED CODE ###

N = int(input())
*a,= map(int, input().split())
count,result={},{}

for i in range(N):
  count[a[i]]=0
  result[a[i]]=0
  
def ncn(n):
  return n*(n-1)//2

for i in range(N):
  count[a[i]]+=1

total=0
for key in count.keys():
  kc = count[key]
  result[key]=ncn(kc)
  total += result[key]
  
def without(k):
  return total-count[a[k]] + 1

for k in range(N):
  print(without(k))
### BUGGY CODE ###

#B
n = int(input())
a = list(map(int,input().split()))
flg = True
MAX = 10 ** 18
cnt = 1
for i in range(n):
    cnt = cnt*a[i]
if cnt > MAX:
    flg = False
        

if flg:
    print(cnt)
else:
    print(-1)

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input(). split ()))
    if 0 in A:
        print(0)
        return
    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return
    print(prod)
    
main()
### BUGGY CODE ###

import numpy

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

acc_a = [0]
for i in range(N):
    acc_a.append(acc_a[i] + A[i])

acc_b = [0]
for i in range(M):
    acc_b.append(acc_b[i] + B[i])

acc_a = numpy.array(acc_a)
acc_b = numpy.array(acc_b)

currentMax = 0
for j in range(M + 1):
    tB = acc_b[j]
    remain = K - tB
    # print('-----------')
    # print('Bを{0}冊読んだら，かかる時間は{1}分, 残り時間は{2}分'.format(j, tB, K - tB))
    if remain < 0:
        # print('時間切れで読める本なし')
        break

    # print(numpy.where(acc_a < remain)[0])
    if len(numpy.where(acc_a < remain)[0]) != 0:
        readable = numpy.where(acc_a <= remain)[0][-1]

        # print('残り時間{0}分で読めるAの本は{1}冊'.format(remain, readable))
        # print('トータル{0}冊読める'.format(j + readable))
        currentMax = max(currentMax, j + readable)

print(currentMax)

### FIXED CODE ###

import numpy

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

acc_a = [0]
for i in range(N):
    acc_a.append(acc_a[i] + A[i])

acc_b = [0]
for i in range(M):
    acc_b.append(acc_b[i] + B[i])

acc_a = numpy.array(acc_a)
acc_b = numpy.array(acc_b)

currentMax = 0
bnum = M
for anum in range(N + 1):
    if acc_a[anum] > K:
        break

    while True:
        if acc_b[bnum] > K - acc_a[anum]:
            bnum = bnum - 1 
        else:
            break

    currentMax = max(currentMax, anum + bnum)


print(currentMax)
### BUGGY CODE ###

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

plus = []
minus = []

for i in a:
    minus.append(i-1)
    plus.append(i+1)

all_l = a + minus + plus
set_all = list(set(all_l))

ans = 0
for i in set_all:
    if all_l.count(i) > ans:
        ans = all_l.count(i)

print(ans)

### FIXED CODE ###

import collections

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

plus = []
minus = []

for i in a:
    minus.append(i-1)
    plus.append(i+1)

all_l = a + minus + plus
ans = collections.Counter(all_l)
print(ans.most_common(1)[0][1])
### BUGGY CODE ###

N = int(input())
A = []
B = []
for i  in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)

now_time = 0
flag = True
for i in range(N):
  min_b = min(B)
  min_b_idx = B.index(min_b)
  now_time += A[min_b_idx]
  del B[min_b_idx]
  del A[min_b_idx]
  if now_time > min_b:
    flag = False
if flag:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

import sys
from operator import itemgetter
sysinput = sys.stdin.readline

N = int(sysinput())
A = []

# O(N)
for i  in range(N):
  A.append(list(map(int, sysinput().split())))

A.sort(key=itemgetter(1))

now_time = 0
flag = True
for i in range(N):
  min_b = A[i][1]
  now_time += A[i][0]
  if now_time > min_b:
    flag = False
if flag:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

mod=10**9+7
def axora(a,b):
  x=(a^b)%mod
  return x

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    ans=(ans+axora(a[i],a[j]))%mod
print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
a=list(map(int,input().split()))
ma=len(bin(max(a)))-2
b=np.array(a)
mod=10**9+7
ans=0
for i in range(ma):
  one=np.count_nonzero((b&1)==1)
  zero=n-one
  ans+=(one*zero*(2**i))%mod
  b=b//2
print(ans%mod)
### BUGGY CODE ###

def num(s,n,k):
  d,m,dm,dmc = 0,0,0,0
  for i in range(n,n*2):
    x,y = s[i],s[i-k]
    if y == 68:
      d -= 1
      dm -= m
    elif y == 77:
      m -= 1
    if x == 68:
      d += 1
    elif x == 77:
      m += 1
      dm += d
    elif x == 67:
      dmc += dm
  return dmc

def main():
  n = int(input())
  s = [0]*n + list(map(ord, list(input())))
  _ = input()
  l = list(map(int, input().split()))
  for k in l:
    print(num(s,n,k))

main()

### FIXED CODE ###

def num(s,n,k):
  d,m,dm,dmc = 0,0,0,0
  for i in range(n,n*2):
    x,y = s[i],s[i-k]
    if y == 68:
      d -= 1
      dm -= m
    elif y == 77:
      m -= 1
    if x == 68:
      d += 1
    elif x == 77:
      m += 1
      dm += d
    elif x == 67:
      dmc += dm
  return dmc

def main():
  n = int(input())
  s = [0]*n + list(map(ord, list(input())))
  _ = input()
  l = list(map(int, input().split()))
  for k in l:
    print(num(s,n,k))

main()
### BUGGY CODE ###

import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a=ii()
l=list(mi())
l=sorted(l)
s=list(combinations(l,3))
ans=0
for i,j,k in s:
  if i+j>k:
    ans+=1
print(ans)

### FIXED CODE ###

import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a=ii()
l=list(mi())
l=sorted(l)
ans=0
for i in range(a-2):
  for j in range(i+1,a-1):
    s=bisect.bisect_left(l,l[i]+l[j])
    ans+=s-j-1
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
num=list()
while N>=0:
    N=N-K
if abs(N)<abs(N+K):
    print(abs(N))
else:
    print(abs(N+K))

### FIXED CODE ###

N,K=map(int,input().split())
if abs(N-(N//K)*K)<abs((N-(N//K)*K)-K):
    print(N-(N//K)*K)
else:
    print(abs((N-(N//K)*K)-K))
### BUGGY CODE ###

import collections
import sys

N = int(input())
s = [collections.Counter(sys.stdin.readline().rstrip()) for _ in range(N)]

counted = []
count = 0
for s_count in s:
    if s_count not in counted:
        n = s.count(s_count)
        counted.append(s_count)
        count += n * (n - 1) // 2
            
print(count)

### FIXED CODE ###

import collections
import sys

N = int(input())
s = [sorted(collections.Counter(sys.stdin.readline().rstrip()).items()) for _ in range(N)]

counted = {}
for s_count in s:
    if str(s_count) not in counted:
        counted[str(s_count)] = 1
    else:
        counted[str(s_count)] += 1


count = 0        
for n in counted.values():
    count += n * (n - 1) // 2
            
print(count)
### BUGGY CODE ###

from fractions import gcd

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

    t = 0
    for i in range(1, n+1):
        for j in range(1, n+1):
            for k in range(1, n+1):
                ans = gcd(i, gcd(j, k))
                t += ans

    print(t)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from math import gcd

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

    t = 0
    for i in range(1, n+1):
        for j in range(1, n+1):
            for k in range(1, n+1):
                ans = gcd(i, gcd(j, k))
                t += ans

    print(t)

if __name__ == "__main__":
    main()