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

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque

INF = 1 << 50


def run():
    N, K = map(int, sysread().split())
    A = list(map(int, sysread().split()))

    l = 0
    r = 10**9
    eps = 1e-8
    while int(l) != int(r):
        test = (l + r) / 2
        sum = 0
        for a in A:
            if a / test == a //test:
                sum += a // test - 1
            else:
                sum += a // test
        if sum > K:
            l = test
        elif a < K:
            r = test
        else:# sum == K
            r = test
    if int(l) == 0:
        print(1)
        return
    if int(l) == l:
        sum = 0
        for a in A:
            sum += (a - eps) // int(l)
        if sum == K:
            print(int(l))
            return

    print(int(l)+1)

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque

INF = 1 << 50


def run():
    N, K = map(int, sysread().split())
    A = list(map(int, sysread().split()))

    l = 0
    r = 10**9
    while int(l) != int(r):
        #print(l, r)
        test = (l + r) / 2
        sum = 0
        for a in A:
            sum += math.ceil(a / test) - 1

        if sum > K:
            l = test
        elif sum < K:
            r = test
        else:# sum == K
            r = test
        if int(r) == r and r-l < 1:
            print(int(r))
            return

    if int(l) == 0:
        print(1)
        return
    if int(l) == l:
        sum = 0
        for a in A:
            sum += math.ceil(a / int(l)) - 1
        if sum == K:
            print(int(l))
            return

    print(int(l)+1)

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

from collections import Counter

s=input()[::-1]
ans=0
lst=[0]
num=0
p=1
for i in s:
    lst.append((int(i)*p+lst[-1])%2019)
    p=p*10


ans=sum(x*(x-1)//2 for x in Counter(lst).values())
print(ans)

### FIXED CODE ###

from collections import Counter

s=input()[::-1]
ans=0
lst=[0]
num=0
p=1
for i in s:
    lst.append((int(i)*p+lst[-1])%2019)
    p=p*10%2019

ans=sum(x*(x-1)//2 for x in Counter(lst).values())
print(ans)
### BUGGY CODE ###

from scipy.sparse.csgraph import csgraph_from_dense, dijkstra


def inpl():
    return list(map(int, input().split()))


N, X, Y = inpl()

edge = [[-1 for n in range(N)] for i in range(N)]

for i in range(N - 1):
    edge[i][i + 1] = 1
    edge[i + 1][i] = 1
edge[X - 1][Y - 1] = 1
edge[Y - 1][X - 1] = 1

G = csgraph_from_dense(edge, null_value=-1)
ans_dict = {}
for g in dijkstra(G):
    for i in g:
        ans_dict[i] = ans_dict.get(i, 0) + 1

for i in range(1, N):
    print(ans_dict.get(i, 0) // 2)


### FIXED CODE ###

def inpl():
    return list(map(int, input().split()))


N, X, Y = inpl()
X -= 1
Y -= 1
ans = {i: 0 for i in range(N)}
for i in range(N):
    for j in range(i + 1, N):
        c = min(j - i, abs(i - X) + 1 + abs(j - Y), abs(i - Y) + 1 + abs(j - X))
        ans[c] += 1

for i in range(1, N):
    print(ans[i])
### BUGGY CODE ###

a, b, k = map(int, input().split())

if (b - a)  < k * 2:
    for i in range(a, b+1):
        print(i)
    exit()


ans = []
for i in range(a,b+1):
    ans.append(i)

for j in range(len(ans)):
    if k <= j < (len(ans) - k):
        pass
    else:
        print(ans[j])


### FIXED CODE ###

a, b, k = map(int, input().split())

if (b - a)  < k * 2:
    for i in range(a, b+1):
        print(i)
    exit()
else:
    for i in range(a,a+k):
        print(i)
    for i in range(b-k+1,b+1):
        print(i)
### BUGGY CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
  print(Counter(a)[i])


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
dp=[0]*(n+1)
for i in range(n-1):
  dp[a[i]]+=1
for i in range(n):
  print(dp[i+1])
### BUGGY CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict
from bisect import bisect_right

s = ns()
t = ns()

ok = True

sset = set(list(s))
for ti in t:
    if ti not in sset:
        ok = False
        break

if not ok:
    print(-1)

else:
    n = len(s)

    charidx = defaultdict(list)

    for i, si in enumerate(s):
        charidx[si].append(i)
    for i, si in enumerate(s):
        charidx[si].append(n+i)

    move = [{ki: -1 for ki in charidx.keys()} for _ in range(n)]

    for i, si in enumerate(s):
        for ki in charidx.keys():
            nexidx = bisect_right(charidx[ki], i)
            move[i][ki] = (charidx[ki][nexidx] - i) % (n+1)

    cur = s.index(t[:1])
    ans = cur
    for ti in t[1:]:
        nex = move[cur][ti]
        ans += nex
        cur = (cur + nex) % n

    print(ans+1)



### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict
from bisect import bisect_right

s = ns()
t = ns()

ok = True

sset = set(list(s))
for ti in t:
    if ti not in sset:
        ok = False
        break

if not ok:
    print(-1)

else:
    n = len(s)

    charidx = defaultdict(list)

    for i, si in enumerate(s):
        charidx[si].append(i)
    for i, si in enumerate(s):
        charidx[si].append(n+i)

    ks = charidx.keys()

    move = [{ki: -1 for ki in ks} for _ in range(n)]

    for i, si in enumerate(s):
        for ki in ks:
            idxlist = charidx[ki]
            nexidx = bisect_right(idxlist, i)
            move[i][ki] = (idxlist[nexidx] - i) % (n+1)

    cur = s.index(t[:1])
    ans = cur
    for ti in t[1:]:
        nex = move[cur][ti]
        ans += nex
        cur = (cur + nex) % n

    print(ans+1)
### BUGGY CODE ###

import collections
import math

def comb(n, r):
    if n < 2:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N = int(input())
L = input().split(" ")

c = collections.Counter(L)

d = {}
tmp_total = 0 

memo1 = {}
for i in c:
    if c[i] not in memo1.keys():
        tmp = comb(c[i], 2)
        memo1[i] = tmp
        tmp_total += tmp
    else:
        tmp_total += memo1[c[i]]
        
total = tmp_total
memo = {}
for i in L:
    if i not in memo.keys():
        ans = total - memo1[i] + comb(c[i]-1, 2)
        memo[i] = ans
        print(ans)
    else:
        print(memo[i])
    

### FIXED CODE ###

import collections
import math

def comb(n, r):
    if n < 2:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N = int(input())
L = input().split(" ")

c = collections.Counter(L)

d = {}
tmp_total = 0 

memo1 = {}
L2 = {}

for i in c:
    if c[i] not in memo1.keys():
        tmp = comb(c[i], 2)
        memo1[c[i]] = tmp
        tmp_total += tmp
    else:
        tmp_total += memo1[c[i]]
        
total = tmp_total

for i in L:
    ans = total - memo1[c[i]] + memo1[c[i]]*(c[i]-2)//c[i]
    print(ans)
### BUGGY CODE ###

n = int(input())
count = 0

for i in range(n):
    data = int(input())
    data = abs(data)
    if data == 2:
        count += 1
    for j in range(2,data):
        if data % j == 0:
            break
        elif j == data - 1:
            count += 1

print(count)

### FIXED CODE ###

n = int(input())
count = 0

for i in range(n):
    data = int(input())
    data = abs(data)
    if data == 2:
        count += 1
    elif pow(2,data-1,data) == 1:
            count += 1

print(count)
### BUGGY CODE ###

p=[1 for i in range(1001)]
p[0]=0
p[1]=0
for i in range(2,1001):
    if p[i]==1:
        for j in range(2,1001):
            if i*j<=1000:
                p[i*j]=0
#print(p[:25])
Prime=[]
for i in range(1001):
    if p[i]==1:
        Prime.append(i)
#print(Prime)
#print(len(Prime))
N=int(input())
L=list(map(int,input().split()))

def gcd(a,b):
    if b>a:
        a,b=b,a
    while a%b!=0:
        a,b=b,a%b
    return b
    
X=L[0]
for i in range(1,N):
    X=gcd(X,L[i])
    if X==1:
        break
if X>1:
    print("not coprime")
    exit()
        
D={}

for I in L:
    for j in Prime:
        if I%j==0:
            if j not in D:
                D[j]=1
            else:
                print("setwise coprime")
                exit()
            while I%j==0:
                I//=j
    if I!=1:
        if I not in D:
            D[I]=1
        else:
            print("setwise coprime")
            exit()
#print(D)

print("pairwise coprime")

### FIXED CODE ###

import time
A=time.time()
p=[1 for i in range(1001)]
p[0]=0
p[1]=0
for i in range(2,1001):
    if p[i]==1:
        for j in range(2,1001):
            if i*j<=1000:
                p[i*j]=0
#print(p[:25])
Prime=[]
for i in range(1001):
    if p[i]==1:
        Prime.append(i)

#print(Prime)
#print(len(Prime))
N=int(input())
L=list(map(int,input().split()))

def gcd(a,b):
    if b>a:
        a,b=b,a
    while a%b!=0:
        a,b=b,a%b
    return b
    
X=L[0]
for i in range(1,N):
    X=gcd(X,L[i])
    if X==1:
        break
if X>1:
    print("not coprime")
    exit()
        
D={}

for I in L:
    B=time.time()
    if B-A>1.9:
        print("pairwise coprime")
        exit()
    for j in Prime:
        if I%j==0:
            if j not in D:
                D[j]=1
            else:
                print("setwise coprime")
                exit()
            while I%j==0:
                I//=j
    if I!=1:
        if I not in D:
            D[I]=1
        else:
            print("setwise coprime")
            exit()
#print(D)

print("pairwise coprime")
### BUGGY CODE ###

import heapq
N = int(input())
edges = [[] for _ in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    edges[a-1].append([b-1, c])
    edges[b-1].append([a-1, c])
Q, K = map(int, input().split())
K -= 1


ans_list = []
def dijkstra(edges, num_v, start):
    dist = [float('inf')] * num_v
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])

    while len(q) > 0:
        _, u = heapq.heappop(q)
        for edge in edges[u]:
            if dist[edge[0]] > dist[u] + edge[1]:
                dist[edge[0]] = dist[u] + edge[1]
                heapq.heappush(q, [dist[u] + edge[1], edge[0]])
    return dist
for i in range(Q):
    x, y = map(lambda n: int(n) - 1, input().split())
    x_K = dijkstra(edges, N, x)[K]
    K_y = dijkstra(edges, N, K)[y]
    ans_list.append(x_K + K_y)

for i in ans_list:
    print(i)

### FIXED CODE ###

import heapq
N = int(input())
edges = [[] for _ in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    edges[a-1].append([b-1, c])
    edges[b-1].append([a-1, c])
Q, K = map(int, input().split())
K -= 1


ans_list = []
def dijkstra(edges, num_v, start):
    dist = [float('inf')] * num_v
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])

    while len(q) > 0:
        _, u = heapq.heappop(q)
        for edge in edges[u]:
            if dist[edge[0]] > dist[u] + edge[1]:
                dist[edge[0]] = dist[u] + edge[1]
                heapq.heappush(q, [dist[u] + edge[1], edge[0]])
    return dist
base = dijkstra(edges,  N, K)
for i in range(Q):
    x, y = map(lambda n: int(n) - 1, input().split())
    x_K = base[x]
    K_y = base[y]
    ans_list.append(x_K + K_y)

for i in ans_list:
    print(i)
### BUGGY CODE ###

import sys
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

x,y= (int(_) for _ in input().split()) 
if (x+y)%3!=0:
    print(0)
    sys.exit()
else:
    n=(x+y)/3
    n=int(n)
    if x<n or y<n:
         print(0)
         sys.exit()
    else:
        x=x-n
        y=y-n
        xy=[x,y]
        ans=int(combinations_count(x+y, min(xy)))
        print(ans%1000000007)

### FIXED CODE ###

import sys
import math
from operator import mul
from functools import reduce
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 
N = 10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

x,y= (int(_) for _ in input().split()) 
if (x+y)%3!=0:
    print(0)
    sys.exit()
else:
    n=(x+y)/3
    n=int(n)
    if x<n or y<n:
         print(0)
         sys.exit()
    else:
        x=x-n
        y=y-n
        ans=int(cmb(x+y, x,mod))
        print(ans%1000000007)
### BUGGY CODE ###

n, m, q = map(int, input().split())
l = [[int(i) for i in input().split()] for _ in range(q)]
m -= 1
As = []


def gen_A(x, y, A, c):
  global As
  if x == n and y == m:
    As.append(A)
    return
  if x < n:
    nA = A+str(c)
    gen_A(x+1, y, nA, c)
  if y < m:
    nc = c+1
    gen_A(x, y+1, A, nc)


gen_A(0, 0, "", 0)
mx = 0
for A in As:
  pts = 0
  for i in l:
    if int(A[i[1]-1])-int(A[i[0]-1]) == i[2]:
      pts += i[3]
  mx = max(mx, pts)
print(mx)

### FIXED CODE ###

n, m, q = map(int, input().split())
l = [[int(i) for i in input().split()] for _ in range(q)]
m -= 1
mx = 0


def gen_A(x, y, A, c):
  global mx
  if x == n and y == m:
    pts = 0
    for i in l:
      if int(A[i[1]-1])-int(A[i[0]-1]) == i[2]:
        pts += i[3]
    mx = max(mx, pts)
    return
  if x < n:
    nA = A+str(c)
    gen_A(x+1, y, nA, c)
  if y < m:
    nc = c+1
    gen_A(x, y+1, A, nc)


gen_A(0, 0, "", 0)
print(mx)
### BUGGY CODE ###

from collections import deque
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
path=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  path[a-1].append(b-1)
  path[b-1].append(a-1)
l=deque()
l.append(0)
while True:
  for i in path[l[0]]:
    if not i in l:
      l.appendleft(i)
      break
  else:break
while True:
  for i in path[l[-1]]:
    if not i in l:
      l.append(i)
      break
  else:break
print(len(l))
l=list(map(lambda x:x+1,l))
print(*l)

### FIXED CODE ###

from collections import deque
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
path=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  path[a-1].append(b-1)
  path[b-1].append(a-1)
l=deque()
s=set()
l.append(0)
s.add(0)
while True:
  for i in path[l[0]]:
    if not i in s:
      l.appendleft(i)
      s.add(i)
      break
  else:break
while True:
  for i in path[l[-1]]:
    if not i in s:
      l.append(i)
      s.add(i)
      break
  else:break
print(len(l))
l=list(map(lambda x:x+1,l))
print(*l)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    adj = []
    for i in range(N):
        adj.append(S())

    def bfs(v):
        group = [-1] * N
        q = deque([(v, 0)])
        valid = True

        while q:
            cur_v, gid = q.popleft()
            group[cur_v] = gid
            for next_v in range(N):
                if adj[cur_v][next_v] == '0':
                    continue
                if group[next_v] != -1:
                    if abs(group[cur_v] - group[next_v]) > 1:
                        valid = False
                        break
                    else:
                        continue
                q.append((next_v, gid+1))
        if not valid:
            return -1
        # print('v: ', v)
        # print('group: ', group)
        # print()
        return max(group) + 1

    ans = -1
    for i in range(N):
        ans = max(ans, bfs(i))

    print(ans)

main()



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    adj = []
    for i in range(N):
        adj.append(S())

    def bfs(v):
        group = [-1] * N
        q = deque([(v, 0)])
        group[v] = 0
        while q:
            cur_v, gid = q.popleft()
            for next_v in range(N):
                if adj[cur_v][next_v] == '0':
                    continue
                if group[next_v] != -1:
                    if abs(group[cur_v] - group[next_v]) > 1:
                        return -1
                    if group[cur_v] == group[next_v]:
                        return -1
                    else:
                        continue
                group[next_v] = gid + 1
                q.append((next_v, gid+1))
        return max(group) + 1

    ans = -1
    for i in range(N):
        ans = max(ans, bfs(i))

    print(ans)

main()
### BUGGY CODE ###

N,M=map(int,input().split())
high_list=list(map(int,input().split()))
pathlist=[]
for i in range(M):
    pathlist.extend(list(map(int,input().split())))
ans=N
for n in range(1,N+1):
    for m in range(0,M*2,2):
        if(pathlist[m]==n):#自身じゃない方の灯台
            if(high_list[n-1]<=high_list[pathlist[m+1]-1]):#経路先が自身よりも高い
                ans=ans-1#回答に含まない
                break
        elif(pathlist[m+1]==n):
            if(high_list[n-1]<=high_list[pathlist[m]-1]):#経路先が自身よりも高い
                ans=ans-1
                break

print(ans)




### FIXED CODE ###

N,M=map(int,input().split())
high_list=list(map(int,input().split()))
highest=[True]*N
for i in range(M):
    a,b=map(int,input().split())
    if(high_list[a-1]>=high_list[b-1]):
        highest[b-1]=False
    if(high_list[a-1]<=high_list[b-1]):
        highest[a-1]=False
print(sum(highest))
### BUGGY CODE ###

N,W = map(int, input().split())
w = [0]*(N+1); v = [0]*(N+1);
for i in range(1, N+1):
    w[i], v[i] = map(int, input().split())

dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(1, N+1):
    dp_i = dp[i]
    dp_i_1 = dp[i-1]
    w_i = w[i]
    v_i = v[i]
    for sum_w in range(1, W+1):
        if sum_w - w_i >= 0:
            dp_i[sum_w] = max(dp_i_1[sum_w - w_i] + v_i, dp_i_1[sum_w])
        else:
            dp_i[sum_w] = dp_i_1[sum_w]
print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
v = [0]*(N+1); w = [0]*(N+1)
for i in range(1, N+1):
    a, b = map(int, input().split())
    w[i], v[i] = a, b

dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(1, N+1):
    row = dp[i]; row_before = dp[i-1]
    v_i = v[i]; w_i = w[i]
    for sum_w in range(1, W+1):
        if sum_w - w_i >= 0:
            row[sum_w] = max(row_before[sum_w - w_i] + v_i, row_before[sum_w])
        else:
            row[sum_w] = row_before[sum_w]
print(dp[N][W])
### BUGGY CODE ###

n,m,q=map(int,input().split())

a=[]
for i in range(n):
    a.append([0]*(n))

import numpy as np
a=np.array(a)

#print(a)
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    a[(r-1):n,0:l]+=1

#print(a)

for i in range(q):
    P,Q=map(int,input().split())
    print(a[(Q-1),(P-1)])

### FIXED CODE ###

from itertools import accumulate
from operator import add, mul
n,m,q=map(int,input().split())

a=[]
b=[]
for i in range(n):
    a.append([0]*(n))
    b.append([0]*(n))

#import numpy as np
#b=np.array(b)
#print(a)
'''
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    #a[(r-1):n,0:l]+=1
    for j in range(r-1,n):
        for k in range(l):
            a[j][k]+=1
'''
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    a[l-1][r-1]+=1

#print(a)

for i in range(n):
    a[i]=list(accumulate(a[i]))

#print(a)

for i in range(n):
    for j in range(n-i-1):
        a[n-i-j-2][n-i-1]+=a[n-i-j-1][n-i-1]
        #print(a)

#print(a)

'''
for l in range(n):
    for r in range(l,n):
        temp=a[r][l]
        for i in range(r,n):
            for j in range(0,l+1):
                b[i][j]+=temp
        #b[r:n,0:l+1]+=temp
'''
#print(a)
#print(b)

for i in range(q):
    P,Q=map(int,input().split())
    print(a[(P-1)][(Q-1)])
'''
for i in range(que):
    p,q=MI()
    if p==1:
        ans=lis[q-1][q-1]
    else:
        ans=lis[q-1][q-1]-lis[p-2][q-1]
    print(ans)
'''
### BUGGY CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
# n = int(input())
mod = 10 ** 9 + 7
a.sort(reverse = True)
# print(a)
ans = 0

def C(n, k, mod):
    x,y = 1,1
    while k > 0:
        x *= n ; y *= k
        n, k = n-1, k-1
        x %= mod ; y %= mod
    return x * pow(y, mod-2, mod)

for i in range(0,n-k+1):
    ans += a[i] * C(n-i-1, k-1, mod)
    ans %= mod

a.reverse()
for i in range(0, n - k + 1):
    ans -= a[i] * C(n - i - 1, k - 1, mod)
    ans %= mod

ans %= mod

print(ans)


### FIXED CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
# n = int(input())
mod = 10 ** 9 + 7
p = mod
a.sort(reverse = True)
# print(a)
ans = 0

#
# def C(n, k):
#     if k == 0:
#         return 1
#     elif n < k or k < 0:
#         return 0
#     else:
#         x,y = 1,1
#         while k > 0:
#             x *= n
#             y *= k
#             n, k = n-1, k-1
#
#         return x * pow(y, mod-2, mod) % mod
#

fac = [0] * (n + 1)
fac[0] = 1
for i in range(n):
    fac[i + 1] = fac[i] * (i + 1) % mod


def C(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], p - 2, p) * pow(fac[k], p - 2, p) % p


for i in range(0,n-k+1):
    ans += a[i] * C(n-i-1, k-1)
    ans %= mod

a.reverse()
for i in range(0,n-k+1):
    ans -= a[i] * C(n-i-1, k-1)
    ans %= mod



print(ans)