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

n,k=map(int,input().split())
a=list(map(int,input().split()))
suma=sum(a)
import math
def func(x):
  chk=0
  for ai in a:
    # 長さx以下に分割するなら最小でtmp本にわかれる
    tmp=math.ceil(ai/x)
    chk+=tmp
  return chk<=n+k
l,r=0,max(a)
for _ in range(100):
  x=(l+r)/2
  if func(x):# k回ですべてx以下にできるなら、もっと小さくできそう
    l,r=l,x
  else:
    l,r=x,r
x=(l+r)/2
print(math.ceil(x))
#print(l,r,x)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
suma=sum(a)
import math
def func(x):
  chk=0
  for ai in a:
    # 長さx以下に分割するなら最小でtmp本にわかれる
    tmp=math.ceil(ai/x)
    chk+=tmp
  return chk<=n+k
l,r=0,max(a)
for _ in range(50):
  x=(l+r)/2
  if func(x):# k回ですべてx以下にできるなら、もっと小さくできそう
    l,r=l,x
  else:
    l,r=x,r
x=(l+r)/2
print(math.ceil(x))
#print(l,r,x)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
A_dis=[abs(A[0]-0)]+list(abs(A[i+1]-A[i]) for i in range(N-1))+[abs(0-A[N-1])]
for j in range(N):
    if j!=0 and j!=N-1:
        print(sum(A_dis)-abs(A[j]-A[j-1])-abs(A[j+1]-A[j])+abs(A[j+1]-A[j-1]))
    elif j==0:
        print(sum(A_dis) - abs(A[j]) - abs(A[j + 1] - A[j])+abs(A[j+1]))
    else:
        print(sum(A_dis) - abs(A[j]) - abs(A[j - 1] - A[j]) + abs(A[j - 1]))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A_dis=[abs(A[0]-0)]+list(abs(A[i+1]-A[i]) for i in range(N-1))+[abs(0-A[N-1])]
total=sum(A_dis)
for j in range(N):
    if j!=0 and j!=N-1:
        print(total-abs(A[j]-A[j-1])-abs(A[j+1]-A[j])+abs(A[j+1]-A[j-1]))
    elif j==0:
        print(total- abs(A[j]) - abs(A[j + 1] - A[j])+abs(A[j+1]))
    else:
        print(total- abs(A[j]) - abs(A[j - 1] - A[j]) + abs(A[j - 1]))
### BUGGY CODE ###

import heapq

N, M = map(int, input().split(" "))
A = [-int(_) for _ in input().split(" ")]

for i in range(M):
    heapq.heapify(A)
    heapq.heappush(A, -(-heapq.heappop(A)// 2))

print(-sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split(" "))
A = [-int(_) for _ in input().split(" ")]

heapq.heapify(A)

for i in range(M):
    heapq.heappush(A, -(-heapq.heappop(A)// 2))
    
print(-sum(A))
### BUGGY CODE ###

s=input()
t=input()

dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
ans=[[[-1,0,0] for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i,c in enumerate(s):
    for j,d in enumerate(t):
        if c==d:
            dp[i+1][j+1]=dp[i][j]+1
            ans[i+1][j+1]=[i,i,j]
        else:
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
            ans[i+1][j+1]=ans[i][j+1] if dp[i+1][j+1]==dp[i][j+1] else ans[i+1][j]

i=len(s)
j=len(t)
ss=[]
while i>0 and j>0:
    x,i,j=ans[i][j]
    if x>-1:
        ss.append(s[x])

print(''.join(ss[::-1]))


### FIXED CODE ###

s=input()
t=input()

dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
ans=[[(-1,-1) for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i,c in enumerate(s):
    for j,d in enumerate(t):
        if c==d:
            dp[i+1][j+1]=dp[i][j]+1
            ans[i+1][j+1]=(i,j)
        else:
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
            ans[i+1][j+1]=ans[i][j+1] if dp[i+1][j+1]==dp[i][j+1] else ans[i+1][j]

i=len(s)
j=len(t)
ss=['']*dp[i][j]
l=dp[i][j]-1
while i>0 and j>0:
    i,j=ans[i][j]
    if i>-1:
        ss[l]=s[i]
        l-=1

print(''.join(ss))
### BUGGY CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


#隣接リスト 1-index
def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def main():
    N, M = NMI()
    F = {}
    for _ in range(M):
        a, b = NMI()
        F[(a, b)] = 1
    tree = make_adjlist_nond(N, list(F.keys()))

    ans = 0
    for start in range(1, N+1):
        que = deque()
        que.append(start)
        seen = [0] * (N+1)
        seen[start] = 1
        fri_cnt = 1
        while que:
            now = que.popleft()

            for goto in tree[now]:
                if seen[goto]:
                    continue
                seen[goto] = 1
                fri_cnt += 1
                que.append(goto)
        ans = max(fri_cnt, ans)
    print(ans)





if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


class UnionFind:
    def __init__(self, n):
        #親要素のノード番号を格納　xが根のとき-(サイズ)を格納
        self.par = [-1 for i in range(n)]
        self.n = n

    def find(self, x):
        #根ならその番号を返す
        if self.par[x] < 0:
            return x
        else:
            #親の親は親
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def is_same(self, x, y):
        #根が同じならTrue
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y: return

        #木のサイズを比較し、小さいほうから大きいほうへつなぐ
        if self.par[x] > self.par[y]:
            x, y = y, x

        self.par[x] += self.par[y]
        self.par[y] = x

    def size(self, x):
        return -self.par[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.par) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, M = NMI()
    F = [NLI() for _ in range(M)]
    uf = UnionFind(N)
    for a, b in F:
        a, b = a-1, b-1
        uf.unite(a, b)
    S = [uf.size(x) for x in range(N)]
    print(max(S))


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

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x


N, K, L = map(int, input().split())
uf = UnionFind(2 * N)
for _ in range(K):
    p, q = map(int, input().split())
    uf.union(p - 1, q - 1)

for _ in range(L):
    r, s = map(int, input().split())
    uf.union(r - 1 + N, s - 1 + N)

ans = [0] * N
for i in range(N):
    cnt = 0
    for j in range(N):
        if uf.find(i) == uf.find(j) and uf.find(i + N) == uf.find(j + N):
            cnt += 1
    ans[i] = cnt

for i in range(N - 1):
    print(ans[i], end=' ')
print(ans[N - 1])


### FIXED CODE ###

from collections import Counter


class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x


N, K, L = map(int, input().split())
uf1 = UnionFind(N)
uf2 = UnionFind(N)
for _ in range(K):
    p, q = map(int, input().split())
    uf1.union(p - 1, q - 1)

for _ in range(L):
    r, s = map(int, input().split())
    uf2.union(r - 1, s - 1)

path = [None] * N
for i in range(N):
    path[i] = (uf1.find(i), uf2.find(i))

cnt = Counter(path)
for i in range(N - 1):
    print(cnt[path[i]], end=' ')
print(cnt[path[N - 1]])
### BUGGY CODE ###

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

at = [0]
for i in range(len(A)):
    at.append(A[i])
    if i > 0:
        at[-1] += at[i]

bt = [0]
for i in range(len(B)):
    bt.append(B[i])
    if i > 0:
        bt[-1] += bt[i]


n = 0
time = 0

for i, a in enumerate(at):
    if a > K:
        break
    for j, b in enumerate(bt):
        if b > K:
            break
        if a+b <= K and a+b >= time:
            time = a+b
            n = i + j

print(n)


### FIXED CODE ###

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

at = [0]
for i in range(len(A)):
    at.append(A[i])
    if i > 0:
        at[-1] += at[i]

bt = [0]
for i in range(len(B)):
    bt.append(B[i])
    if i > 0:
        bt[-1] += bt[i]


n = 0
time = 0


for i, a in enumerate(at):
    if a > K:
        break
    l = 0
    r = len(bt)-1
    while r - l > 1:
        m = (l+r)//2
        if bt[m] < K-a:
            l = m
        else:
            r = m
    if bt[r] <= K -a:
        b = bt[r]
    else:
        r -= 1
        b = bt[r]
    if i + r >= n:
        n = i + r

print(n)
### BUGGY CODE ###

K, S = map(int, input().split())
ans = 0
for x in range(K + 1):
    for y in range(K + 1):
        for z in range(K + 1):
            if x + y + z == S:
                ans += 1
print(ans)

### FIXED CODE ###

K, S = map(int, input().split())
ans = 0
for x in range(K + 1):
    for y in range(K + 1):
        if (S - (x + y) <= K) and (0 <= S - (x + y)):
            ans += 1
print(ans)
### BUGGY CODE ###

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

if N > 24:
    print(0)
else:
    ans = 0
    for i in range(2 ** N):
        bit = bin(i)[2:].zfill(N)
        D_mod24 = [0] * N
        for j in range(N):
            if bit[j] == '0':
                D_mod24[j] = D[j]
            else:
                D_mod24[j] = 24 - D[j]
        D_mod24.sort()
        ans_temp = min(min(D_mod24), 24 - max(D_mod24))
        for j in range(N-1):
            ans_temp = min(ans_temp, D_mod24[j+1] - D_mod24[j])
        ans = max(ans, ans_temp)
    print(ans)


### FIXED CODE ###

from collections import Counter

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

if N > 23:
    print(0)
elif N > 11:
    D.append(0)
    D_count = Counter(D)
    if D_count.most_common()[0][1] > 2:
        print(0)
    else:
        print(1)
else:
    ans = 0
    for i in range(2 ** (N - 1)):
        bit = '0' + bin(i)[2:].zfill(N - 1)
        D_mod24 = [0] * N
        for j in range(N):
            if bit[j] == '0':
                D_mod24[j] = D[j]
            else:
                D_mod24[j] = 24 - D[j]
        D_mod24.sort()
        ans_temp = min(min(D_mod24), 24 - max(D_mod24))
        for j in range(N-1):
            ans_temp = min(ans_temp, D_mod24[j+1] - D_mod24[j])
        ans = max(ans, ans_temp)
    print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
flush = sys.stdout.flush
def query(x):
    print("%d\n" % x)
    flush()
    # ジャッジから返される値を取得
    return readline().strip()


n = int(input())

right = n
left = -1

print(0, flush = True)
lefti = input()
if lefti == "Vacant":
    exit(0)
print(n-1, flush = True)
righti = input()
if righti == "Vacant":
    exit(0)

while True:
    mid = left + (right-left)//2
    midi = query(mid)
    if midi == "Vacant":
        exit(0)
    if (lefti == midi and (mid - left) % 2 == 1) or ((lefti != midi) and (mid - left) % 2 == 0):
        righti = midi
        right = mid
    else:
        lefti = midi
        left = mid


### FIXED CODE ###

import sys
readline = sys.stdin.readline
flush = sys.stdout.flush
def query(x):
    print("%d\n" % x)
    flush()
    # ジャッジから返される値を取得
    return readline().strip()


n = int(input())

right = n-1
left = 0

print(0, flush = True)
lefti = input()
if lefti == "Vacant":
    exit(0)
print(n-1, flush = True)
righti = input()
if righti == "Vacant":
    exit(0)

while True:
    mid = left + (right-left)//2
    midi = query(mid)
    if midi == "Vacant":
        exit(0)
    if (lefti == midi and (mid - left) % 2 == 1) or ((lefti != midi) and (mid - left) % 2 == 0):
        righti = midi
        right = mid
    else:
        lefti = midi
        left = mid
### BUGGY CODE ###

N = int(input())
power = 1
for x in range(1, N+1):
    power *= x
print(power%(10**9+7))

### FIXED CODE ###

N = int(input())
power = 1
for x in range(1, N+1):
    power = (power * x) % (10**9+7)
print(power)
### BUGGY CODE ###

import math
X = int(input())
time = X
for i in range(X+1):
    j = X - i
    if j > time: continue
    n = - 1 + math.sqrt(1+8*(X-j))
    if n < 2*j and math.floor(n) == n:
        time = min(time, j)
print(time)

### FIXED CODE ###

import math
X = int(input())
n =  math.ceil((math.sqrt(1+8*X) - 1)/2)
ans = n
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
N, C = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [[0] * (C + 1) for _ in range(N)]
mod = 10 ** 9 + 7
for i in range(N):
  for j in range(C + 1):
    for k in range(a[i], b[i] + 1):
      c[i][j] += (k ** j) % mod
      c[i][j] %= mod
dp = [[0] * (C + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
  for j in range(C + 1):
    for k in range(j, C + 1):
      dp[i + 1][k] += dp[i][j] * c[i][k - j]
      dp[i + 1][k] %= mod
print(dp[-1][-1] % mod)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
N, C = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [0] * (N * (C + 1))
mod = 10 ** 9 + 7
for i in range(N):
  c[i * (C + 1)] = b[i] - a[i] + 1
for i in range(N):
  for k in range(a[i], b[i] + 1):
    t = 1
    for j in range(C):
      t *= k
      t %= mod 
      c[i * (C + 1) + j + 1] += t
      c[i * (C + 1) + j + 1] %= mod
dpx = [0] * (C + 1)
dpy = [0] * (C + 1)
dpx[0] = 1
for i in range(N):
  if i % 2:
    dpx = [0] * (C + 1)
  else:
    dpy = [0] * (C + 1)
  for j in range(C + 1):
    for k in range(j, C + 1):
      if i % 2:
        dpx[k] += dpy[j] * c[i * (C + 1) + k - j]
        dpx[k] %= mod
      else:
        dpy[k] += dpx[j] * c[i * (C + 1) + k - j]
        dpy[k] %= mod
if N % 2:
  print(dpy[-1] % mod)
else:
  print(dpx[-1] % mod)
### BUGGY CODE ###

N = int(input())

ans = 0

while N > 0:
    ans += N % 10
    # ans = ans % 9
    N = N // 10
ans = ans % 9
if ans == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N = input()

ans = 0

for i in range(len(N)):
    ans += int(N[i])

ans = ans % 9
if ans == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

import heapq
import numpy as np
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for i in range(M):
  b, c = map(int, input().split())
  A.extend([c]*b)
A.sort()
print(int(sum(A[len(A)-N:])))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
a = []

for i in range(M):
  b = list(map(int, input().split()))
  a.append(b)
  
from operator import itemgetter
A.sort()
a.sort(key = itemgetter(1))
count = 0
for i in range(N):
  if A[i] < a[-1-count][1]:
    A[i] =  a[-1-count][1]
    a[-1-count][0] -= 1
    if a[-1-count][0] == 0:
      count += 1
    if count == M:
      break
print(sum(A))
### BUGGY CODE ###

import math

def resolve():
  N = int(input())

  for n in range(1, N+1):
    count = 0
    max_range = int(math.sqrt(n)) + 1
    for x in range(1, max_range):
      for y in range(1, max_range):
        for z in range(1, max_range):
          if x**2 + y**2 + z**2 + x*y + y*z + z*x == n:
            count += 1
    print(count)

if __name__ == "__main__":
  resolve()


### FIXED CODE ###

import math

def resolve():
  N = int(input())

  result = [0] * (N + 1)
  max_range = int(math.sqrt(N)) + 1
  for x in range(1, max_range):
    for y in range(1, max_range):
      for z in range(1, max_range):
        index = x**2 + y**2 + z**2 + x*y + y*z + z*x
        if index <= N:
          # if index == 8:
          #   print("x: {0}, y: {1},z: {2},".format(x, y, z))
          result[index] += 1

  for i in result[1:]:
    print(i)

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

import sys
# sys.setrecursionlimit(100000)
import heapq


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    from collections import Counter
    n, m = input_int_list()
    hq = list(Counter(input_int_list()).items())

    heapq.heapify(hq)

    for _ in range(m):
        b, c = input_int_list()
        while b > 0:
            k, v = heapq.heappop(hq)
            if k >= c:
                heapq.heappush(hq, (k, v))
                break
            else:
                if v == b:
                    heapq.heappush(hq, (c, b))
                    b = 0
                elif v > b:
                    heapq.heappush(hq, (c, b))
                    heapq.heappush(hq, (k, v - b))
                    b = 0
                elif b > v:
                    heapq.heappush(hq, (c, v))
                    b -= v
    ans = 0
    for k, v in hq:
        ans += k * v

    print(ans)

    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
# sys.setrecursionlimit(100000)
import heapq


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    from collections import Counter
    # 計算量 O(n*log_n + m*log_m)

    # 入力
    n, m = input_int_list()
    hq = list(Counter(input_int_list()).items())  # O(n)
    # 最小値管理にPriorityQueueを使う

    heapq.heapify(hq)  # O(n*log_n)

    queries = []
    for _ in range(m):
        queries.append(input_int_list())

    queries.sort(key=lambda x: x[1], reverse=True)  # O(m * log_m)

    # cが大きい数字から処理したほうが効率的になる
    for b, c in queries:
        while b > 0:
            k, v = heapq.heappop(hq)
            if k >= c:
                heapq.heappush(hq, (k, v))
                break
            else:
                if v == b:
                    heapq.heappush(hq, (c, b))
                    b = 0
                elif v > b:
                    heapq.heappush(hq, (c, b))
                    heapq.heappush(hq, (k, v - b))
                    b = 0
                elif b > v:
                    heapq.heappush(hq, (c, v))
                    b -= v
    ans = 0
    for k, v in hq:
        ans += k * v

    print(ans)

    return


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

N, S = map(int, input().split())
mod = 998244353
A = list(map(int, input().split()))
D = {0: [[-1, -1]], S: []}
for i in range(N):
    L = [[j, D[j]] for j in D]
    L.sort(reverse=True)
    for jn, j in enumerate(L):
        if j[0]+A[i] <= S:
            for kn, k in enumerate(j[1]):
                if j[0]+A[i] in D:
                    D[j[0]+A[i]].append([(j[0]>0)*k[0]+(j[0]==0)*i, i])
                else:
                    D[j[0]+A[i]] = [[(j[0]>0)*k[0]+(j[0]==0)*i, i]]
p = 0
for i in D[S]:
    p += (i[0] + 1) * (N - i[1]) % mod
    p %= mod
print(p)

### FIXED CODE ###

N, S = map(int, input().split())
mod = 998244353
A = list(map(int, input().split()))
L = [0 for _ in range(S+1)]
p = 0
F = {0}
for i in range(N):
    L[0] += 1
    X = [[j, L[j]] for j in F]
    for j in X:
        if j[0] + A[i] <= S:
            L[j[0]+A[i]] += j[1]
            L[j[0]+A[i]] %= mod
            F.add(j[0]+A[i])
    p += L[S]
    p %= mod

print(p)
### BUGGY CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
l = [list(map(int, input().split())) for _ in range(M)]

ans = 0
for i in range(1, N+1):
  # ノードi(=1,...,N)と結合しているノードを全て求め、connectに格納
  connect = []
  for j in range(M):
    if i in l[j]:
      if i == l[j][0]: connect.append(l[j][1])
      else: connect.append(l[j][0])
  
  # ノードiの標高が、結合している任意のノードの標高より高いなら ans += 1
  n = 0
  for c in connect:
    if H[i-1] > H[c-1]: n += 1
  if n == len(connect): ans += 1

print(ans)

### FIXED CODE ###

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

# N,M=O(10^5)なので、O(N+M)で解く
# 各ノードについて、隣接する展望台の高さの最大値を更新する
neighbor_max = [0] * N
for _ in range(M):
  A, B = map(int, input().split())
  neighbor_max[A - 1] = max(neighbor_max[A - 1], H[B - 1])
  neighbor_max[B - 1] = max(neighbor_max[B - 1], H[A - 1])

# 各ノードについて、自身の高さと、隣接する展望台の高さの最大値を比較する
# 接続を一つも持たないノードについても、計算は正しい
ans = 0
for i in range(N):
  if H[i] > neighbor_max[i]: ans += 1
    
print(ans)
### BUGGY CODE ###

n = int(input())
ans = 0

def gcd(a,b):
    if a>b:
        p = a
        q = b
    else:
        p = b
        q = a
    d = q
    while p % q != 0:
        d = p % q
        p = q
        q = d
    return d


for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            if i==1 or j==1 or k==1:
                ans += 1
            else:
                ans += gcd(gcd(i,j),k)

print(ans)


### FIXED CODE ###

n = int(input())
ans = 0
 
def max(a,b):
    if a>b:
        return a
    else:
        return b
 
def min(a,b):
    if a<b:
        return a
    else:
        return b
 
def gcd(a,b):
    p = max(a,b)
    q = min(a,b)
    d = q
    while p % q != 0:
        d = p % q
        p = q
        q = d
    return d
 
 
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans += gcd(gcd(i,j),k)
 
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
(n, ), *r = [[*map(int, i.split())] for i in open(0)]
s = sorted([[x + l, x - l] for x, l in r])
c = 0
p = 0
while s:
    c += 1
    p = s[0][0]
    s = [i for i in s if i[1] >= p]
print(c)


### FIXED CODE ###

#!/usr/bin/env python3
(n, ), *r = [[*map(int, i.split())] for i in open(0)]
s = sorted([[x + l, x - l] for x, l in r])
c = 1
p = s[0][0]
for i in s[1:]:
    if i[1] >= p:
        c += 1
        p = i[0]
print(c)
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline

    MOD = pow(10, 9) + 7

    n, k = map(int, input().split())
    A = sorted(map(int, input().split()))
    B = A[::-1]
    fact = [1]
    for i in range(1, n+1):
        fact.append((fact[i-1]*i)%MOD)

    ans = 0
    for i, a in enumerate(A):
        now = k-2
        while now <= n-2-i:
            tmp = ((fact[now] % MOD * pow(fact[now-(k-2)], MOD-2, MOD)) % MOD * pow(fact[k-2], MOD-2, MOD)) % MOD
            ans = (ans - a*tmp)%MOD
            now += 1
        now = k-2

    for i, b in enumerate(B):
        now = k-2
        while now <= n-2-i:
            tmp = ((fact[now] % MOD * pow(fact[now-(k-2)], MOD-2, MOD)) % MOD * pow(fact[k-2], MOD-2, MOD)) % MOD
            ans = (ans + b*tmp)%MOD
            now += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline

    MOD = pow(10, 9) + 7

    n, k = map(int, input().split())
    A = sorted(map(int, input().split()))
    B = A[::-1]
    fact = [1]
    for i in range(1, n+1):
        fact.append((fact[i-1]*i)%MOD)
    now = k-2
    S = []
    while now <= n-2:
        tmp = ((fact[now] % MOD * pow(fact[now-(k-2)], MOD-2, MOD)) % MOD * pow(fact[k-2], MOD-2, MOD)) % MOD
        S.append(tmp)
        now += 1
    cumsum = [0, ]
    for i, s in enumerate(S):
        cumsum.append((cumsum[i]+s) % MOD)
    ans = 0
    for i, a in enumerate(A):
        ans = (ans - a*cumsum[-(i+1)])%MOD
        if cumsum[-(i+1)] == 0:
            break
    for i, b in enumerate(B):
        ans = (ans + b*cumsum[-(i+1)])%MOD
        if cumsum[-(i+1)] == 0:
            break
    print(ans)


if __name__ == '__main__':
    main()