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

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

class UnionFind():
  def __init__(self,n):
    self.parent={}
    for i in range(n):
      self.parent[i]=[i]
      
  def find_parent(self,x):
    import sys
    parent=self.parent
    for key in parent.keys():
      if x in parent[key]:
        return key
        sys.exit()
        
  def union(self,x,y):
    parent=self.parent
    x_par,y_par=self.find_parent(x),self.find_parent(y)
    if x_par==y_par:
      pass
    else:
      if len(parent[x_par])<len(parent[y_par]):
        parent[y_par]+=parent[x_par]
        parent.pop(x_par)
      else:
        parent[x_par]+=parent[y_par]
        parent.pop(y_par)
    self.parent=parent
    return None
  
  def same(self,x,y):
    if self.find_parent(x)==self.find_parent(y):
      return True
    else:
      return False
  def cnt(self):
    par=self.parent
    return len(set(par))
uf=UnionFind(N)
for i in range(M):
  x,y,z=map(int,input().split())
  uf.union(x-1,y-1)
print(uf.cnt())

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


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

uf = UnionFind(n)

for x, y, _ in xyz:
    x -= 1
    y -= 1
    uf.unite(x, y)

uf.update_p()
ans = len(set(uf.p))
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
AB = []
for i in range(H):
  AB.append(list(map(int, input().split())))

for i in range(H):
  AB[i] = [abs(AB[i][j] - int(b)) for j, b in enumerate(input().split())]

K = 80*(H + W) + 1
dp = [[[False]*K for w in range(W+1)] for h in range(H+1)]
dp[0][0][0] = True
dp[0][1][0] = True
dp[1][0][0] = True

for h in range(H):
  for w in range(W):
    ab = AB[h][w]
    for i, tp in enumerate(dp[h][w+1]):
      if not tp:
        continue
        
      dp[h+1][w+1][abs(i+ab)] = True
      dp[h+1][w+1][abs(i-ab)] = True
      
    for i, tp in enumerate(dp[h+1][w]):
      if not tp:
        continue
      
      dp[h+1][w+1][abs(i+ab)] = True
      dp[h+1][w+1][abs(i-ab)] = True

for k in range(K):
  if dp[H][W][k]:
    print(k)
    break

### FIXED CODE ###

H, W = map(int, input().split())
AB = []
max_ab = 0
for i in range(H):
  AB.append(list(map(int, input().split())))
  max_ab = max(max_ab, max(AB[-1]))

for i in range(H):
  AB[i] = [abs(AB[i][j] - int(b)) for j, b in enumerate(input().split())]

base = max_ab*(H + W)
dp = [[1 << base for w in range(W)] for h in range(H)]
dp[0][0] = (1 << base + AB[0][0]) | (1 << base - AB[0][0])
for h in range(1, H):
  dp[h][0] = (dp[h-1][0] << AB[h][0]) | (dp[h-1][0] >> AB[h][0])

for w in range(1, W):
  dp[0][w] = (dp[0][w-1] << AB[0][w]) | (dp[0][w-1] >> AB[0][w])

for h in range(1, H):
  for w in range(1, W):
    dp[h][w] = (
      (dp[h-1][w] << AB[h][w]) | (dp[h-1][w] >> AB[h][w]) 
      | (dp[h][w-1] << AB[h][w]) | (dp[h][w-1] >> AB[h][w]))

positive = bin(dp[H-1][W-1] >> base)
print(positive[::-1].find('1'))
### BUGGY CODE ###

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

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

for i in range(n-k):
    new = dat[k + i]
    nukeru = dat[i]
    newval = prev // nukeru * new
    if newval > prev:
        print("Yes")
    else:
        print("No")
    prev = newval

### FIXED CODE ###

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

prev = dat[0]

for i in range(n-k):
    new = dat[k + i]
    nukeru = dat[i]
    if new > nukeru:
        print("Yes")
    else:
        print("No")
    prev = new
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
ans=0
l=sorted(l)[::-1]
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if l[i]<l[j]+l[k]:
        ans+=1
print(ans)

### FIXED CODE ###

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

from bisect import bisect_left,bisect
N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC.sort(key=lambda x: x[1],reverse = True)
for b,c in BC:
  A.sort()
  i = bisect_left(A,c)
  if c <= A[0]:
    break
  if b < i:
    A[:b] = [c]*b
  else:
    A[:i] = [c]*i
print(sum(A))

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [(A[i], 1) for i in range(N)]
for _ in range(M):
    B, C = map(int, input().split())
    BC.append((C,B))
BC = sorted(BC,reverse = True)
ans = 0
a = 0
count = N
for c,b in BC:
  lamb = min(count,b)
  ans += c * lamb
  count -= lamb

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

def main():
    from collections import deque
    N,M = map(int, input().split())
    A = deque(map(int, input().split()))
    for _ in range(M):
        B,C=map(int, input().split())
        A.extend([C for _ in range(B)])
    A = list(A)
    A.sort(reverse=True)
    ans = 0
    for i in range(N):
        ans += A[i]
    print(ans)

main()

### FIXED CODE ###

n,m=map(int,input().split())
ans=list(map(int,input().split()))
arr=[list(map(int,input().split())) for _ in range(m)]
arr=sorted(arr,reverse=True,key=lambda x:x[1])
tmp=0
for cnt,val in arr:
  ans+=[val]*cnt
  tmp+=cnt
  if tmp>=n:
    break
ans=sorted(ans,reverse=True)
print(sum(ans[:n]))
### BUGGY CODE ###

n,k = (int(i) for i in input().split())
h = list(int(i) for i in input().split())
dp = list(0 for i in range(n))
num = list(range(n))
num = sorted(num, reverse=True)
for i in num:
    if i==n-1:
         dp[i]=0
    elif i==n-2:
         dp[i]=abs(h[n-1]-h[n-2])
    elif i>n-k-1:
        for j in range(i+1,n):
            if j==i+1:
                dp[i] = abs(h[j]-h[i])+dp[j]
            else:
                dp[i] = min(dp[i],abs(h[j]-h[i])+dp[j])
    else:
        for j in range(i+1,i+k+1):
            if j==i+1:
                dp[i] = abs(h[j]-h[i])+dp[j]
            else:
                dp[i] = min(dp[i],abs(h[j]-h[i])+dp[j])              
print(dp[0])

### FIXED CODE ###

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

H = [0] + H
dp = [0] * (N+1)

for i in range(2, N+1):
    dp[i] = dp[i-1] + abs(H[i]-H[i-1])
    for k in range(2, K+1):
        if i-k >= 1:
            dp[i] = min(dp[i], dp[i-k]+abs(H[i]-H[i-k]))

res = dp[N]
print(res)
### BUGGY CODE ###

import math

S=input()
T=input()


ans = 0
l=len(S)

if S ==T:
    print(0)
else:
    for a in range(l): 
          if S[a] != T[a]:
              S.replace(S[a], T[a])
              ans += 1
          
    print(ans)

### FIXED CODE ###

S=input()
T=input()

ans = 0
l=len(S)

if S ==T:
    print(0)
else:
    for a in range(l): 
          if S[a] != T[a]:
              ans += 1
          
    print(ans)
### BUGGY CODE ###

import math
import numpy as np
from fractions import gcd
import fractions
import statistics
import collections
from functools import reduce
import itertools
from collections import defaultdict

N,M=map(int, input().split())
city = defaultdict(list)
p = [0] * M
y = [0] * M

for i in range(M):
    p[i],y[i]=map(int, input().split())
    city[p[i]].append(y[i])

city_sorted = defaultdict(list)
for key,v in city.items():
    city_sorted[key] = sorted(v)

for a in range(M):
    for (i,x) in enumerate(city_sorted[p[a]]):
        if (y[a] == x):
            print(str(p[a]).zfill(6)+str(i+1).zfill(6))
            break

### FIXED CODE ###

import math
import numpy as np
from fractions import gcd
import fractions
import statistics
import collections
from functools import reduce
import itertools
from collections import defaultdict

N,M=map(int, input().split())
city = defaultdict(list)
p = [0] * M
y = [0] * M

for i in range(M):
    p[i],y[i]=map(int, input().split())
    city[p[i]].append(y[i])

year = defaultdict(list)
for key,v in city.items():
    for i,x in enumerate(sorted(v)):
        year[x] = i+1

for a in range(M):
    print(str(p[a]).zfill(6)+str(year[y[a]]).zfill(6))
### BUGGY CODE ###

import numpy as np
import heapq
import copy

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

num_vec = np.zeros(n + 1)
for ai in a:
    num_vec[ai] += 1

for k in range(1, n+1):
    vec = copy.deepcopy(num_vec)
    
    count = 0
    while True:
        ind_num_maps = list((i, num) for (i, num) in enumerate(vec) if num!=0)

        picks = list(map(lambda map: map[0], heapq.nlargest(k, ind_num_maps, key=lambda map: map[1])))
        for pick in picks:
            vec[pick] -= 1

        if len(picks) == k:
            count += 1
        else:
            break

    print(count)
            

### FIXED CODE ###

import collections
import numpy as np

# リストarrからx個の同じ長さの列を取り出す時の最大の長さ
# 発想: x個取り出す時、ある文字をx個より多く取り出して列に含むことはない
#       一方ある文字をその文字がある数よりも取り出して使うこともできない
#       つまり、min(arr.count(a), x)で、x個の同じ長さの列に使えるaの数がわかる
#       さらに、sum(min(arr.count(a),x))で、x個の同じ長さの列に使える文字の数がわかる
#       よって、sum(min(arr.count(a),x))//xで、x個の同じ長さの列の長さがわかる
#       発展的に、longest(arr,x)までの計算状況からlongest(arr,x+1)が計算できる
# def longest(arr, x):    # legacy
#     return sum(min(arr.count(a), x) for a in arr) // x


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

counter = collections.Counter(a)        #O(n)
nums = list(counter.values())           #O(n)
num_counter = collections.Counter(nums) #O(n)
lastest_add = np.count_nonzero(nums)    #O(n)
building, longests = [0], [0]
for i in range(1, n+1):                 #O(n)
    appended = building[-1] + lastest_add   #O(1)
    building.append(appended)               #O(1)
    longests.append(appended // i)          #O(1)
    lastest_add -= num_counter[i]           #O(1)


lastest_longest = 0
k_most = []
for i, x in enumerate(reversed(longests)):
    while x > lastest_longest:
        lastest_longest += 1
        k_most.append(n-i)

k_most.extend([0]*(n-len(k_most)))      # zero padding

for longests_num in k_most:
    print(longests_num)

# print('----------------')
# for k in range(1, n+1):
#     maxindexes = list(i for i, x in enumerate(longests) if x >= k)
#     if maxindexes:
#         print(maxindexes[-1])
#     else:
#         print(0)
### BUGGY CODE ###

import itertools

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

tr = [[0]*n for _ in range(n)]

for i in range(m):
    l, r = map((lambda x:int(x)-1), input().split())
    tr[l][r] += 1

for i in range(n):
    tr[i] = list(itertools.accumulate(tr[i]))

for i in range(q):
    p, q = map((lambda x:int(x)-1), input().split())
    ans = 0
    for j in tr[p:q+1]:
        ans += (j[q] - j[p-1]) if p>0 else j[q]

    print(ans)



### FIXED CODE ###

import itertools

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

tr = [[0]*n for _ in range(n)]

for i in range(m):
    l, r = map((lambda x:int(x)-1), input().split())
    tr[l][r] += 1

for i in range(n):
    tr[i] = list(itertools.accumulate(tr[i]))

for i in range(q):
    p, q = map((lambda x:int(x)-1), input().split())
    ans = 0
    for j in tr[p:q+1]:
        ans += (j[q] - j[p-1]) if p>0 else j[q]

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

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))+[0]

    for i in range(k):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        
        for k in range(n):
            B[k+1]+=B[k]
        A=B

        if A==[n]*(n+1):
            break
    
    

    print(*A[:-1])    
    
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))

    for i in range(k):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        
        for k in range(n):
            B[k+1]+=B[k]
        A=B[:-1]

        if A==[n]*(n):
            break
    
    

    print(*A)    
    
resolve()
### BUGGY CODE ###


x = input().split()
n = int(x[0]) # n == 比較文字列の長さ
q = int(x[1]) # q == 検討する回数
s = input()

def ind_Multi(a,b): #a,b == 検索範囲   
    global n
    global s 
    index_L = []
    for i in range(a,b):
        if s[i] == "A":
            index_L.append(i)
    return index_L

            
        

def sc():
    global s
    global n
    global q
    global idbox
    maxx = 0
    count = 0
    com = [int(s)-1 for s in input().split()]
    idbox = ind_Multi(com[0],com[1])
    if not idbox:
        print(0)
        return None
        
    

    
    for i in range(idbox[0],idbox[-1]+1): # i == 先頭の文字
        
        if (s[i+1]) == "C":
            count += 1
            
            
    print(count)

for i in range(q):
    
    sc()


### FIXED CODE ###


x = input().split()
n = int(x[0]) # n == 比較文字列の長さ
q = int(x[1]) # q == 検討する回数
s = input()

        
t = [0] * n
if s[0] == "A":
    t[0] = 1
    
for i in range(0,n-1):
    if s[i:i+2] == "AC":
        
        if (i == 0) :
            t[i] =  + 1
        else:
            t[i] = t[i-1] + 1
    else :
        if i == 0:
            t[i] = 0
        else:
            t[i] = t[i-1]



def sc():
    global t
    global s
    global n
    global q
    global idbox
    maxx = 0
    count = 0
    com = [int(s)-1 for s in input().split()]
    
    
    print(t[com[1]-1] - t[com[0]-1])
        
    

    

for i in range(q):
    
    sc()
### BUGGY CODE ###

n=int(input())
a=map(int,input().split())
m=0
from itertools import*
for i,j in combinations(a,2):
    k=i*j
    m+=k
print(m%1000000007)

### FIXED CODE ###

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

cumsum = [A[0]]
for i in range(1, N):
    cumsum.append(A[i] + cumsum[i - 1])

ans = 0
for i in range(N):
    ans += (A[i] * (cumsum[-1] - cumsum[i])) % MOD
    ans %= MOD

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

N, M = map(int, input().split())
kukan = sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x: x[1])
ans = 0

while kukan:
    cut = kukan[0][1] - 1
    kukan = list(filter(lambda x: not x[0] <= cut < x[1], kukan))
    ans += 1

print(ans)

### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    kukan_list = sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x: x[1])
    ans = 0
    cut = 0
    
    for kukan in kukan_list:
        if cut >= kukan[0]:
            continue
        ans += 1
        cut = kukan[1] - 1
    
    print(ans)

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

N = int(raw_input())
S = [list(raw_input()) for t in range(N)]
ans = 0
for n in range(N):
  isSym = True
  for i in range(N):
    for j in range(i,N):
      if S[i][j] != S[j][i]:
        isSym = False
  ans += 1 if isSym else 0
  s = S.pop()
  S.insert(0, s)
print ans*N


### FIXED CODE ###

N = int(raw_input())
S = [list(raw_input()) for t in range(N)]
ans = 0
for n in range(N):
  t = S[n:]+S[:n]
  t_t = list(map(list, zip(*t)))
  if t == t_t:
    ans += 1
#for n in range(N):
#  isSym = True
#  for i in range(N):
#    for j in range(i,N):
#      if S[i][j] != S[j][i]:
#        isSym = False
#        break
#    if not isSym:
#      break
#  ans += 1 if isSym else 0
#  s = S.pop()
#  S.insert(0, s)
print ans*N
### BUGGY CODE ###

n,*a= map(int,open(0).read().split())
b=[0]*n

for i in range(1,n+1):
    b[i-1]=a.index(i)+1
print(*b)

### FIXED CODE ###

n,*a= map(int,open(0).read().split())
"""
b=[]

for i in range(1,n+1):
    b.append(a.index(i)+1)
"""
b=[[a[i],i+1] for i in range(n)]
b.sort(key=lambda x: x[0])
for bb in b:
    print(bb[1],end =" ")
print("")
### BUGGY CODE ###

#from operator import itemgetter
#from collections import Counter
#import heapq
N = int(input())
S = input()
#N, M = map(int, input().split())
#A = list(map(lambda x: int(x)*(-1), input().split()))
#A = [int(input()) for i in range(N)]
#C = [list(map(int, input().split())) for i in range()]
R  =[]
G  =[]
B  =[]
for i, s in enumerate(S):
    if s == 'R':
        R.append(i)
    elif s == 'G':
        G.append(i)
    else:
        B.append(i)
answer = len(R)*len(G)*len(B)
hiku = 0
for r in R:
    for g in G:
        for b in B:
            if abs(r-g) == abs(g-b) or abs(r-b) == abs(b-g) or abs(b-r) == abs(r-g):
                hiku += 1
answer -= hiku
print(answer)


### FIXED CODE ###

N = int(input())
S = input()
#N, M = map(int, input().split())
#A = list(map(lambda x: int(x)*(-1), input().split()))
#A = [int(input()) for i in range(N)]
#C = [list(map(int, input().split())) for i in range()]
R  =[]
G  =[]
B  =[]
for i, s in enumerate(S):
    if s == 'R':
        R.append(i)
    elif s == 'G':
        G.append(i)
    else:
        B.append(i)
answer = len(R)*len(G)*len(B)
hiku = 0

for i in range((N-1)//2):
    for j in range(N-i-i-2):
        if S[j] != S[j+i+1] and S[j+i+1] != S[j+i+i+2] and S[j] != S[j+i+i+2]:
            hiku += 1


answer -= hiku
print(answer)
### BUGGY CODE ###

def main():
    k, s = map(int, input().split())
    if s > 3*k:
        pass
    elif s == 3*k:
        ans = 1
    else:
        ans = 0
        for i in range(k+1):
            for j in range(k+1):
                for l in range(k+1):
                    if i + j + l == s:
                        ans += 1
    print(ans)
main()


### FIXED CODE ###

def main():
    k, s = map(int, input().split())
    if s > 3*k:
        pass
    elif s == 3*k:
        ans = 1
    else:
        ans = 0
        for i in range(k+1):
            for j in range(k+1):
                    if 0<=s - (i + j)<=k:
                        ans += 1
    print(ans)
main()
### BUGGY CODE ###

import fractions
N=int(input())
A=list(map(int,input().split()))
c=1
a=0
w=10**9+7
for i in range(N):
    c_=c*A[i]//fractions.gcd(c,A[i])
    a=(a*c_//c+c_//A[i])%w
    c=c_
print(int(a))

### FIXED CODE ###

import fractions
N=int(input())
A=list(map(int,input().split()))
c=1
a=0
w=10**9+7
for A_ in A:
    c=c*A_//fractions.gcd(c,A_)
for A_ in A:
    a+=c//A_
print(int(a%w))
### BUGGY CODE ###

A = input()
N = input().split()
N = [int(s) for s in N]

ans = 1
max = 1000000000000000000
for i in range(len(N)):
  ans = ans * N[i]

if ans > max:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

ans = 1
max = 10**18
if 0 in N:
  print(0)
else:
  for i in range(len(N)):
    ans = ans * N[i]
    if ans > max:
      ans = -1
      break
  print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
dp=[10**10]*n
h=list(map(int,input().split()))
dp[0]=0
for i in range(1,n):
    dp[i]=min(dp[i-j]+abs(h[i-j]-h[i]) for j in range(1,1+min(k,i)))

print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
dp=[10**10]*n
h=list(map(int,input().split()))
dp[0]=0
for i in range(1,n):
    dp[i]=min(dp[i-j]+abs(h[i-j]-h[i]) for j in range(1,1+min(k,i)))

print(dp[-1])
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
ans=[]
for i in range(q):
  l,r=map(int,input().split())
  ans.append(str(s[l-1:r].count("AC")))
print("\n".join(ans))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
t=[0]*(n+1)
for i in range(n):
  t[i+1]=t[i]+(1 if s[i:i+2] == "AC" else 0)
for i in range(q):
  l,r=map(int,input().split())
  print(t[r-1]-t[l-1])
### BUGGY CODE ###

n,k=map(int,input().split())
dp=[float("INF")]*n
h=list(map(int,input().split()))
dp[0]=0
for i in range(1,n):
    dp[i]=min(dp[i-j]+abs(h[i-j]-h[i]) for j in range(1,1+min(k,i)))

print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
dp=[10**10]*n
h=list(map(int,input().split()))
dp[0]=0
for i in range(1,n):
    dp[i]=min(dp[i-j]+abs(h[i-j]-h[i]) for j in range(1,1+min(k,i)))

print(dp[-1])
### BUGGY CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    mod = 10 ** 9 + 7
    
    N, K = map(int, f_i.readline().split())
    A = sorted(map(int, f_i.readline().split()))
    
    comb = 1
    ans = A[K-1] - A[N-K]
    for i, j in zip(range(K, N), range(1, N)):
        comb = comb * i // j
        ans += (A[i] - A[N-i-1]) * comb
    
    print(ans % mod)

solve()

### FIXED CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    mod = 10 ** 9 + 7
    
    N, K = map(int, f_i.readline().split())
    A = sorted(map(int, f_i.readline().split()))
    
    comb = 1
    ans = A[K-1] - A[N-K]
    for i, j in zip(range(K, N), range(1, N)):
        comb = comb * i * pow(j, mod - 2, mod) % mod
        ans += (A[i] - A[N-i-1]) * comb
        ans %= mod
    
    print(ans)

solve()
### BUGGY CODE ###

def main():
    N = int(input())
    ans = 0
    for m in range(1, N+1):
        if N % (m + 1) != 0:
            continue
        elif N // (m + 1) < m:
            ans += m
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from math import floor, sqrt


def main():
    N = int(input())
    divs = divisor(N)
    ans = 0
    for i in divs:
        m = i - 1
        if m == 0:
            continue
        if N // m == N % m:
            ans += m
    print(ans)


def divisor(N):
    divs = []
    sup = floor(sqrt(N))
    for i in range(1, sup+1):
        if N % i == 0:
            divs.append(i)
            divs.append(N // i)
    return sorted(divs)


if __name__ == '__main__':
    main()