Harryxun/stf_run huggingface dataset:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)
        
        self.par = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        tmpx,tmpy=x,y
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
            self.par[tmpy]  =tmpx

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.par[tmpx]  = tmpy
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def cur(n):
    if memo[n]==-1: memo[n]=(cur(tree.par[n])+state[n])%2
    return memo[n]

N=int(input())
tree=UnionFind(N)

state=[-1]*(N+1)
for i in range(N-1):
    u,v,w=map(int,input().split())
    tree.Unite(u,v)
    if tree.par[u]==v: state[u]=w%2
    if tree.par[v]==u: state[v]=w%2

memo=[-1]*(N+1)
memo[tree.Find_Root(0)]=0
for i in range(1,N+1):
    if cur(i)%2==0: print(0)
    else: print(1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

def cur(current,e,dist,color):
    for it in e[current]:
        if color[it]!=-1: continue
        color[it]=(color[current]+dist[(it,current)])%2
        cur(it,e,dist,color)

N=int(input())
e=[[] for i in range(N+1)]
dist={}
for i in range(N-1):
    u,v,w=map(int,input().split())
    e[u].append(v)
    e[v].append(u)
    dist[(u,v)],dist[(v,u)]=w,w
memo=[-1]*N




color=[-1]*(N+1)
color[1]=0
cur(1,e,dist,color)

for i in range(1,N+1):
    print(color[i])
n=int(input())
a=list(map(int,input().split()))
answer=1
for i in range(n):
    answer*=a[i]
    if answer>10**18:
        answer=-1
        break
if a.cout(0)>0:
    answer=0
print(answer)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
answer=1
for i in range(n):
    answer*=a[i]
    if answer>10**18:
        answer=-1
        break
if a.count(0)>0:
    answer=0
print(answer)
t=int(input())
h=t//3600
m=t//60%60
s=t%60
print(h+":"+m+":"+s)


### FIXED CODE ###

S = int(input())
h = S // 3600
m = S % 3600 // 60
s = S % 60
print(str(h)+":"+str(m)+":"+str(s))
N=int(input())
p=list(map(int,input().split()))
q=['x' for _ in range(N)]
ans=0
for i in range(N):
    if p[i]!=i+1:
        q[i]='o'
for i in range(N-1):
    if q[i]=='x':
        if i<n-1:
            p[i], p[i+1]=p[i+1], p[i]
        else:
            p[i], p[i-a1]=p[i-1], p[i]
        q[i]='o'
        q[i+1]='o'
        ans+=1

print(ans)


### FIXED CODE ###

from collections import Counter
N=int(input())
a=list(map(int, input().split()))
b=[]
for i in range(N):
    b.append(a[i])
    b.append(a[i]+1)
    b.append(a[i]-1)
Ctb=Counter(b)
print(max(Ctb.values()))
a,b,k =map(int,input().split())

if k<=a
  print(a-k,b)
elif a<k<=a+b:
  print(k-a,b-(k-a))
else:
  print(0,0)

### FIXED CODE ###

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

if a > k:
  print(a-k,b)
elif a == k:
  print(0,b)
else:
  if (a+b) > k:
    print(0,a+b-k)
  else:
    print(0,0)
N, C = map(int, input().split())
r = [[0] * C for _ in range(10 * 5)]
for _ in range(N):
    s, t, c = map(int, input().split())
    for i in range(s - 1, t):
        r[i][c - 1] = 1
ans = 0
for t in r:
    sum_t = sum(t)
    if sum_t > ans:
        ans = sum_t

print(ans)

### FIXED CODE ###

N, A, B = map(int, input().split())
print(min(A * N, B))
N = int(input())
S = []
for _ in range(N):
    s = [0]*26
    for i in map(lambda: ord(c)-97, input()):
        s[i] += 1

res = 0
for i in range(N):
    for j in range(i+1, N):
        if S[i] == S[j]:
            res += 1

print(res)

### FIXED CODE ###

N = int(input())
d = dict()

for _ in range(N):
    s = "".join(sorted(input()))
    if s in d:
        d[s] += 1
    else:
        d[s] = 0

print(int(sum(map(lambda x: (x+1)*x/2, d.values()))))
from heapq import heappush, heappop
from collections import deque

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

ans = 0

for i in range(K+1):
    sup = min(i,K)
    for l in range(sup+1):
        for r in range(sup+1-l):
            j = min(i-r-l,r+l)
            hq = []
            dq = deque(V)
            for _ in range(l):
                item = dq.popleft()
                heappush(hq, item)
            for _ in range(r):
                item = dq.pop()
                heappush(hq, item)
            for _ in range(j):
                heappop(hq)
            res = sum(hq)
            ans = max(ans,res)

print(ans)

### FIXED CODE ###

from heapq import heappush, heappop
from collections import deque

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

ans = 0

for i in range(K+1):
    sup = min(i,N)
    for l in range(sup+1):
        for r in range(sup+1-l):
            j = min(i-r-l,r+l)
            hq = []
            dq = deque(V)
            for _ in range(l):
                item = dq.popleft()
                heappush(hq, item)
            for _ in range(r):
                item = dq.pop()
                heappush(hq, item)
            for _ in range(j):
                heappop(hq)
            res = sum(hq)
            ans = max(ans,res)

print(ans)
N=int(input())
D=int(input())

print((N+D*2)//(D*2+1))

### FIXED CODE ###

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

print((N+2*D) // (2*D+1))
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
h = list(map(int, input().split()))
h_cond = [True]*n
count = 0

for i in range(m):
    tmp_a, tmp_b = map(int, input().split())
    if h[tmp_a-1] < h[tmp_b-1]:
        h_cond[tmp_a-1] = False
    elif h[tmp_a-1] > h[tmp_b-1]:
        h_cond[tmp_b-1] = False
    else:
        h_cond[tmp_a - 1] = False
        h_cond[tmp_b - 1] = False

# print(h_cond)
# print(route)
for idx, hi in enumerate(route):
    if h_cond[idx]:
        count += 1

print(count)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n, m = map(int, input().split())
h = list(map(int, input().split()))
h_cond = [True]*n
count = 0

for i in range(m):
    tmp_a, tmp_b = map(int, input().split())
    if h[tmp_a-1] < h[tmp_b-1]:
        h_cond[tmp_a-1] = False
    elif h[tmp_a-1] > h[tmp_b-1]:
        h_cond[tmp_b-1] = False
    else:
        h_cond[tmp_a - 1] = False
        h_cond[tmp_b - 1] = False

# print(h_cond)
# print(route)
for idx, hi in enumerate(h_cond):
    if h_cond[idx]:
        count += 1

print(count)
S_str=str(input())
S=int(S_str[-1])
N=len(S_str)

mod=[0]*2018
mod[0]=1
now=S%2019
mod[now]+=1

for i in range(N-1)[::-1]:
    #print(i+1,S,S%2019)
    next=pow(10,N-1-i,2019)
    next=(next*int(S_str[i]))%2019
    now=(now+next)%2019
    mod[now]+=1

    

def culc(x):
    return x*(x-1)//2


ans=0
for j in range(len(mod)):
    ans+=culc(mod[j])

print(ans)




### FIXED CODE ###

S_str=str(input())
S=int(S_str[-1])
N=len(S_str)

mod=[0]*2019
mod[0]=1
now=S%2019
mod[now]+=1

for i in range(N-1)[::-1]:
    #print(i+1,S,S%2019)
    next=pow(10,N-1-i,2019)
    next=(next*int(S_str[i]))%2019
    now=(now+next)%2019
    mod[now]+=1

    

def culc(x):
    return x*(x-1)//2


ans=0
for j in range(len(mod)):
    ans+=culc(mod[j])

print(ans)
# coding: -*- utf-8 -*-

in_str = input()
a, b = in_str.split(" ")
if a*b % 2 == 0:
    print("Even")
else:
    print("Odd")

### FIXED CODE ###

# coding: utf-8
in_str = input()
a, b = in_str.split(" ")
a = int(a)
b = int(b)

if a*b % 2 == 0:
    print("Even")
else:
    print("Odd")
from collections import Counter

n = int(input())
v = list(map(int,input().split()))
even1 = v[0::2]
odd1 = v[1::2]
even2 = Counter(v1)
odd2 = Counter(v2)
a = even2.most_common()[0][0]
b = odd2.most_common()[0][0]
c = even2.most_common()[0][1]
d = odd2.most_common()[0][1]
if a != b:
 print(len(even1)-c+len(odd1)-d)
else:
 if len(list(set(even1))) == 1 and len(list(set(odd1))) == 1:
  print(len(even1))

 else:
  if c <= d:
   print(len(even1)*2-d-even2.most_common()[1][1])
  else:
   print(len(even1)*2-c-odd2.most_common()[1][1])


### FIXED CODE ###

from collections import Counter

n = int(input())
v = list(map(int,input().split()))
even1 = v[0::2]
odd1 = v[1::2]
even2 = Counter(even1)
odd2 = Counter(odd1)
a = even2.most_common()[0][0]
b = odd2.most_common()[0][0]
c = even2.most_common()[0][1]
d = odd2.most_common()[0][1]
if a != b:
 print(len(even1)-c+len(odd1)-d)
else:
 if len(list(set(even1))) == 1 and len(list(set(odd1))) == 1:
  print(len(even1))
 elif len(list(set(even1))) == 1:
  print(len(odd1)-odd2.most_common()[1][1])
 elif len(list(set(odd1))) == 1:
  print(len(even1)-even2.most_common()[1][1])
 else:
  e = even2.most_common()[1][1]
  f = odd2.most_common()[1][1]
  if c-e >= d-f:
   print(len(even1)*2-c-f)
  else:
   print(len(even1)*2-d-e)
n=int(input())
a=list(map(int,input().split()))
count=1
if 0 in a:
  print(0)
  exit(0)
for i in range(n):
    count=count*a[i]
	if count>10**18:
    	print(-1)
        exit(0)
else:
    print(count)


### FIXED CODE ###

n = int(input())
lis = list(map(int,input().split()))
ans = 1
if 0 in lis:
  print(0)
  exit()
for num in lis:
  ans *= num
  if ans > 10 ** 18:
    print(-1)
    exit()
print(ans)
N = int(input())
A = list(map(int,input().split()))

def f(A):
    for a in A:
        if a == 0:
            print(0)
            return
    v = 1
    for a in A:
        v *= a
        if v > int(1e+18):
            print(-1)
            return
    print(v)
    return

f(A)

### FIXED CODE ###

A,B = list(map(int,input().split()))
print(A*B)
ls = [int(input()) for i in range(5)]
ans = []
num = 0
minNum = 10
    
for j in ls:
    x = j % 10
    if x < minNum and x != 0:
        num = j
        minNum = x
ans.append(num)
ls.pop(ls.index(num))

for i in ls:
    y = ((i + 9) // 10) * 10
    ans.append(y)


print(sum(ans))

### FIXED CODE ###

n =  [int(input()) for x in range(5)]
minNum = 10
array = 0
for i in range(len(n)):
    num = n[i] % 10
    if((num <= minNum) and (num != 0)):
        minNum = num
        array = i
        
numList = []
a = n[array]
n[array] = 0

for x in n:
    k = ((x + 9) // 10) * 10
    numList.append(k)  
print(sum(numList) + a)
n,y = map(int,input().split())
for a in range(n+1):
    for b in range(n-b+1):
        c=n-a-b
        if 10000*a+5000*b+1000*c==y:
            print(a, b, c)
            exit()
print("-1 -1 -1")

### FIXED CODE ###

n,y = map(int,input().split())
import sys
for a in range(n+1):
    for b in range(n-a+1):
        c=n-a-b
        if 10000*a+5000*b+1000*c==y:
            print(a, b, c)
            sys.exit()
print("-1 -1 -1")
import collections
n = int(input())
v = list(map(int,input().split()))
ve = [v[2*i] for i in range(n//2)]
vo = [v[2*i + 1] for i in range(n//2)]
Cve = collections.Counter(ve)
Cvo = collections.Counter(vo)
Cve1 = Cve.most_common()[0]
Cvo1 = Cvo.most_common()[0]
if len(Cve) == 1 and len(Cvo) == 1:
    if Cve1[0] == Cvo1[0]: ans = n//2 - Cvo1[1]
    else: ans = 0
elif len(Cve) == 1 and len(Cvo) != 1:
    Cvo2 = Cvo.most_common()[1]
    if Cve1[0] == Cvo1[0]: ans = n//2 - Cvo2[1]
    else: ans = n//2 - Cvo1[1]
elif len(Cve) != 1 and len(Cvo) == 1:
    Cve2 = Cve.most_common()[1]
    if Cve1[0] == Cvo1[0]: ans = n//2 - Cve2[1]
    else: ans = n//2 - Cve1[2]
else:
    Cve2 = Cve.most_common()[1]
    Cvo2 = Cvo.most_common()[1]
    if Cve1[0] != Cvo1[0]: ans = n - Cve1[1] - Cvo1[1] 
    if Cve1[0] == Cvo1[0]:
        if Cve1[1] > Cvo1[1]: ans = n - Cve1[1] - Cvo2[1]
        else: ans = n - Cve2[1] - Cvo1[1]
print(ans)

### FIXED CODE ###

import collections
n = int(input())
v = list(map(int,input().split()))
ve = [v[2*i] for i in range(n//2)]
vo = [v[2*i + 1] for i in range(n//2)]
Cve = collections.Counter(ve)
Cvo = collections.Counter(vo)
Cve1 = Cve.most_common()[0]
Cvo1 = Cvo.most_common()[0]
if len(Cve) == 1 and len(Cvo) == 1: #eo両方1種類
    if Cve1[0] == Cvo1[0]: ans = n//2 #eo top同じ
    else: ans = 0 #eo異なる
elif len(Cve) == 1 and len(Cvo) > 1: #eのみ1種類
    Cvo2 = Cvo.most_common()[1]
    if Cve1[0] == Cvo1[0]: ans = n//2 - Cvo2[1] #eo top同じ
    else: ans = n//2 - Cvo1[1] #eo top異なる
elif len(Cve) > 1 and len(Cvo) == 1: #oのみ1種類
    Cve2 = Cve.most_common()[1]
    if Cve1[0] == Cvo1[0]: ans = n//2 - Cve2[1] #eo top同じ
    else: ans = n//2 - Cve1[1] #eo top異なる
else:
    Cve2 = Cve.most_common()[1]
    Cvo2 = Cvo.most_common()[1]
    if Cve1[0] != Cvo1[0]: ans = n - Cve1[1] - Cvo1[1] #top異なる
    if Cve1[0] == Cvo1[0]:
        if Cve1[1] < Cvo1[1]: ans = n - Cve2[1] - Cvo1[1]
        elif Cve2[1] > Cvo2[1] : ans = n - Cve2[1] - Cvo1[1]
        else: ans = n - Cve1[1] - Cvo2[1]
print(ans)
import math

def myfact(n):
  return math.factorial(n) % 1000000007

def combinations_count(n, r):
    return myfactorial(n) // ((myfactorial(n - r) * myfactorial(r))

n, k = map(int, input().split())
for i in range(1, k+1):
  print(combinations_count(k-1, i-1) * combinations_count(i+1+(n-k)-(i-1)-1, (n-k)-(i-1)) % 1000000007) 

### FIXED CODE ###

import math

def myfactorial(n):
  return math.factorial(n)

def combinations_count(n, r):
  return (myfactorial(n) // (myfactorial(n - r) * myfactorial(r))) % 1000000007

n, k = map(int, input().split())
for i in range(1, k+1):
  if n-k+1 < i:
    print(0)
  else:
    print(combinations_count(k-1, i-1) * combinations_count(n-k+1, i) % 1000000007)
import sys


sys.setrecursionlimit(2000)
n = int(input())
info = [list(map(int, input().split())) for i in range(n)]

v = 100000
graph = [[] for i in range(v*2)]
for i in range(n):
    x = info[i][0] - 1
    y = (info[i][1] - 1) + v
    graph[x].append(y)
    graph[y].append(x)

def dfs(pos):
    if visited[pos]:
        return
    visited[pos] = True
    if 0 <= pos < v:
        cnt[0] += 1
    else:
        cnt[1] += 1
    for i in graph[pos]:
        dfs(i)
    return

visited = [False] * (v*2)
cnt = [0]*2
ans = 0
for i in range(v*2):
    cnt[0] = 0
    cnt[1] = 0
    dfs(i)
    ans += cnt[0]*cnt[1]
print(ans - n)

### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(200010)
n = int(input())
info = [list(map(int, input().split())) for i in range(n)]

v = 100000
graph = [[] for i in range(v*2)]
for i in range(n):
    x = info[i][0] - 1
    y = (info[i][1] - 1) + v
    graph[x].append(y)
    graph[y].append(x)

def dfs(pos):
    if visited[pos]:
        return
    visited[pos] = True
    cnt[pos//v] += 1
    for i in graph[pos]:
        dfs(i)
    return

visited = [False] * (v*2)
cnt = [0]*2
ans = 0
for i in range(v*2):
    cnt[0] = 0
    cnt[1] = 0
    dfs(i)
    ans += cnt[0]*cnt[1]
print(ans - n)
n, m, k = map(int, input().split())
arA = list(map(int, input().split()))
arB = list(map(int, input().split()))

idxA = idxB = 0
readTime :int = 0
readBooks :int = 0
while readTime < k:
    #if arA[idxA] <= arA[idxB] and idxA < n:
    if idxA < n and arA[idxA] <= arA[idxB]:
        if k < readTime + arA[idxA]:
            break
        readTime += arA[idxA]
        idxA += 1
    else:
        if k < readTime + arB[idxB]:
            break
        readTime += arB[idxB]
        idxB += 1
    readBooks += 1
    if idxA >= n and idxB >= m:
        break

print(readBooks)


### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
#!/usr/bin/env python3
import sys

MOD = 2019  # type: int

def solve(L: int, R: int):
    if R - L >= 2019 - 1:
        print(0)
    if R % 2019 <= L % 2019:
        print(0)
    else:
        L = L % 2019
        R = R % 2019
        
        smallest = 10000000
        for i in range(L, R):
            for j in range(i+1, R+1):
                calc = (i*j)%2019
                if calc < smallest:
                    smallest = calc
    print(smallest)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    L = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    solve(L, R)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 2019  # type: int

def solve(L: int, R: int):
    if R - L >= 2019 - 1:
        print(0)
        return
    if R % 2019 <= L % 2019:
        print(0)
        return
    else:
        L = L % 2019
        R = R % 2019
        
        smallest = 10000000
        for i in range(L, R):
            for j in range(i+1, R+1):
                calc = (i*j)%2019
                if calc < smallest:
                    smallest = calc
    print(smallest)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    L = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    solve(L, R)

if __name__ == '__main__':
    main()
from math import sqrt
t = int(input())
for i in range(t):
     s = input()
     t = input()
     if(t[:-1] == s):
         print("YES")
     else:
         print("NO")



















### FIXED CODE ###

from math import sqrt


s = input()
t = input()
if(t[:-1] == s):
    print('Yes')
else:
    print('No')
a,b = int(input().split(" "))
c=a*b
if c % 2 == 0:
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

a, b = map(int, input().split())
c = a * b
if c % 2 == 0:
  print("Even")
else:
  print("Odd")
n = int(input())

from collections import defaultdict

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

d = defaultdict(int)

for el in a:
    d[el] += 1

count = 0

d = sorted(d.items(), reverse=True)

m = max(d, key=lambda x: x[0])

while len(d):
    a, c = d.pop()
    if c == 1:
        count += 1
    if a == 1:
        break
    if a * a <= m:
        d = [elm for elm in d if elm[0] % a]

print(count)

### FIXED CODE ###

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

c = [0]*(10**6+1)

for a in aa:
    c[a] += 1

d = [False]*(10**6+1)

count = 0

for i in range(1, 10**6+1):
    if not c[i]:
        continue
    if d[i]:
        continue
    if c[i] == 1:
        count += 1
    for j in range(i, 10**6+1, i):
        d[j] = True

print(count)
MOD = 1e9 + 7

facs = [0 for _ in range(50009)]
facs[1] = 1
for i in range(2, 50009):
	facs[i] = (facs[i-1] * i) % MOD


def choose(n, k):
	if k==1:
		return n
	if n==0:
		return 0
	if n==k:
		return 1
	try:
		return int((facs[n]/facs[k]/facs[n-k]) % MOD)
	except ZeroDivisionError:
		print(n, k)

def main():
	N, K = map(int, input().split())
	numbers = sorted(map(int, input().split()))
	if K==1:
		return 0
	if K==N:
		return numbers[0] - numbers[-1]

	score = 0
	for i, x in enumerate(numbers):
		score = (score + (choose(i, K-1) - choose(N-1-i, K-1)) * x) % MOD

	return int(round(score))
	
	
print(main())


### FIXED CODE ###

import time
MOD =  1000000007
MOD2 = 1000000005
MAX = 100001

facs = [1 for _ in range(MAX)]
inv = [1 for _ in range(MAX)]


for i in range(1, MAX):
	facs[i] = (facs[i-1] * i) % MOD

for i in range(1, MAX):
	inv[i] = pow(facs[i], MOD2, MOD)


def get_facs(x):
	return facs[x]


def get_inv(x):
	return inv[x]

def choose(n, k):

	if k==0 or n==k:
		return 1
	if n==0:
		return 0
	if k>n:
		return 0
	r = (get_facs(n)*get_inv(k)) % MOD
	r = (r*get_inv(n-k)) % MOD
	return r



def main():
	N, K = map(int, input().split())
	numbers = sorted(map(int, input().split()))
	if K==1:
		return 0
	if K==N:
		return abs(numbers[0] - numbers[-1])

	score = 0
	for i, x in enumerate(numbers):
		score += ((choose(i, K-1) - choose(N-1-i, K-1)) * x)

	return score%MOD
	
	
print(main())
#!/usr/bin/env python3
import sys
from itertools import product

MOD = 1000000007  # type: int

def solve(N: int, K: int):
    if K % 2 == 1:
        print(0)
        return
    dp = [[[0 for k in range(K+1)]
            for j in range(N+1)]
            for i in range(N+1)]
    dp[0][0][0] = 1
    for i, j, k in product(range(1, N+1), range(N+1), range(K+1)):
        prev_k = k - 2 * j
        if prev_k < 0:
            continue
        dp[i][j][k] += dp[i-1][j][prev_k]
        dp[i][j][k] += 2 * j * dp[i-1][j][prev_k]
        dp[i][j][k] += (j+1) * (j+1) * dp[i-1][j+1][prev_k]
        dp[i][j][k] += dp[i-1][j-1][prev_k]
        dp[i][j][k] %= MOD
    print(dp[N][0][K])

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    k = int(next(tokens))  # type: int
    solve(n, k)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from itertools import product

MOD = 1000000007  # type: int

def solve(N: int, K: int):
    if K % 2 == 1:
        print(0)
        return
    dp = [[[0 for k in range(K+1)]
            for j in range(N+2)]
            for i in range(N+1)]
    dp[0][0][0] = 1
    for i, j, k in product(range(1, N+1), range(N+1), range(K+1)):
        prev_k = k - 2 * j
        if prev_k < 0:
            continue
        dp[i][j][k] += dp[i-1][j][prev_k]
        dp[i][j][k] += 2 * j * dp[i-1][j][prev_k]
        dp[i][j][k] += (j+1) * (j+1) * dp[i-1][j+1][prev_k]
        if j > 0: dp[i][j][k] += dp[i-1][j-1][prev_k]
        dp[i][j][k] %= MOD
    print(dp[N][0][K])

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    k = int(next(tokens))  # type: int
    solve(n, k)

if __name__ == '__main__':
    main()
n = int(input())

ans = 0
for i in range(1, int(n ** 0.5) + 1):
    m = n // i - 1
    if n % i == 0 and n // m == n % m:
        ans += m
print(ans)


### FIXED CODE ###

n = int(input())

ans = 0
for i in range(1, int(n ** 0.5) + 1):
    m = n // i - 1
    if m > 0 and n % i == 0 and n // m == n % m:
        ans += m
print(ans)
n=int(input())
if n<=9:
  print(n)
else:
  n=str(n)
  x=n[0]
  x=int(x)-1
  if n[1:].count('9')==len(n-1):
    print(x+1(len(n)-1)*9)
  else:
    print(x+(len(n)-1)*9)


### FIXED CODE ###

n=int(input())
if n<=9:
  print(n)
else:
  n=str(n)
  x=n[0]
  x=int(x)-1
  if n[1:].count('9')==len(n)-1:
    print(x+1+(len(n)-1)*9)
  else:
    print(x+(len(n)-1)*9)
if a * b //2 == 1:
  print('odd')
else:
  print('even')
  

### FIXED CODE ###

a,b=map(int,input().split())
if (a*b)%2 == 1:
  print('Odd')
else:
  print('Even')
N = int(input())
DX = list(int(i) for i in input().split())
A = []
for i in range(N):
     A.append(input())


ai =[]
ans = N + DX[1]
for i in range(N):
    for n in range(DX[0]):
        if n*A[i]+1 <= DX[0]:
            ai.append(n)
    ans += max(ai)
    ai = []
print(ans)


### FIXED CODE ###

N = int(input())
DX = list(int(i) for i in input().split())
A = []
for i in range(N):
     A.append(int(input())) 
ai =[]
ans = N + DX[1]
for i in range(N):
    for n in range(DX[0]):
        if n*A[i]+1 <= DX[0]:
            ai.append(n)
    ans += max(ai)
    ai = []
print(ans)