Harryxun/stf_run huggingface dataset:
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

if N == 1:
    print(K)
else:
    from scipy import special
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].add(b)
        else:
            d[a] = {b}
        if b in d:
            d[b].add(a)
        else:
            d[b] = {a}
    root = {1}
    ans = K
    while True:
        a = K - 2
        if 1 in root:
            a = K - 1
        children.clear()
        for i in root:
            for j in d[i]:
                d[j].remove(i)
            b = len(d[i])
            if a < b:
                print(0)
                break
            if b == 0:
                continue
            ans *= special.perm(a, b, exact=True)
            children |= d[i]
        else:
            if len(children) == 0:
                print(ans % mod)
                break
            root = children
            continue
        break

### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)
def find(parent, i):
  t = parent[i]
  if t < 0:
    return i
  t = find(parent, t)
  parent[i] = t
  return t

def unite(parent, i, j):
  i = find(parent, i)
  j = find(parent, j)
  if i == j:
    return
  parent[j] += parent[i]
  parent[i] = j

n, m = map(int, input().split())
parent = [-1] * n
inconvenience = n * (n - 1) // 2
data = [[int(c) - 1 for c in input().split()] for _ in range(m)]
data.reverse()
result = []
for a, b in data:
  result.append(inconvenience)
  if find(parent, a) != find(parent, b):
    inconvenience -= parent[find(parent, a)] * parent[find(parent, b)]
  unite(parent, a, b)
result.reverse()
for i in result:
  print(i)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5)

def find(parent, i):
  t = parent[i]
  if t < 0:
    return i
  t = find(parent, t)
  parent[i] = t
  return t

def unite(parent, i, j):
  i = find(parent, i)
  j = find(parent, j)
  if i == j:
    return
  parent[j] += parent[i]
  parent[i] = j

n, m = map(int, input().split())
parent = [-1] * n
inconvenience = n * (n - 1) // 2
data = [[int(c) - 1 for c in input().split()] for _ in range(m)]
data.reverse()
result = []
for a, b in data:
  result.append(inconvenience)
  if find(parent, a) != find(parent, b):
    inconvenience -= parent[find(parent, a)] * parent[find(parent, b)]
  unite(parent, a, b)
result.reverse()
for i in result:
  print(i)
a,b=input()
if b%a==0:
  print(a+b)
else:
  print(b-a)

### FIXED CODE ###

a,b=map(int, input().split())
if b%a==0:
  print(a+b)
else:
  print(b-a)
import bisect

characters = [chr(ord('a') + i) for i in range(26)]

def main():
    N = int(input())
    S = input()
    Q = int(input())

    indices_dict = {a: [] for a in characters}
    for i, s in enumerate(S):
        indices_dict[s].append(i + 1)

    for i in range(Q):
        a, b, c = input().split()
        if int(a) == 2:
            l, r = int(b), int(c)
            cnt = 0
            for c in characters:
                l_ind = bisect.bisect_left(indices_dict[c], l)
                r_ind = bisect.bisect_right(indices_dict[c], r)
                if l_ind != r_ind:
                    cnt += 1
            print(cnt)
        else:
            ind, to_c = int(b), c
            bisect.insort_left(indices_dict[to_c], ind)
            from_c = S[ind - 1]
            indices_dict[from_c].pop(bisect.bisect_left(indices_dict[from_c], ind))

if __name__ == "__main__":
    main()

### FIXED CODE ###

from bisect import insort_left, bisect_left
n = int(input())
s = list(input())
Q = int(input())
query = [input() for _ in range(Q)]
dic = {chr(i+ord('a')):[] for i in range(26)}
for ind, c in enumerate(s):
    dic[c].append(ind)

for q in query:
    t, a, b = q.split()
    a = int(a)-1
    if t=='1':
        if s[a]==b:
            continue
        ind = bisect_left(dic[s[a]], a)
        dic[s[a]].pop(ind)
        insort_left(dic[b], a)
        s[a] = b
    else:
        b = int(b)-1
        tmp = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                tmp += 1
        print(tmp)
N, M = map(int, input().split())
zahyou = list(map(int,input().split()))
zahyou.sort()
difference = []
ans = 0

if M == 1:
    ans = 0
else:
    for i in range (M-1):
        difference.append(zahyou[i+1] - zahyou[i])
    difference.append(0)
    difference.sort()
    difference.reverse()
    length = zahyou[-1] - zahyou[0]
    ans = int(length)
    for i in range (N-1):
        ans -= difference[i]

print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
zahyou = list(map(int,input().split()))
zahyou.sort()
difference = []
ans = 0

if N >= M:
    ans = 0
else:
    for i in range (M-1):
        difference.append(zahyou[i+1] - zahyou[i])
    difference.sort()
    ans = sum(difference[:M-N])

print(ans)
a=input().split()
num=a[0]
del a[0]
for i in range(0,num//2+1):
    a[i]=int(a[i])
b=0
c=0
answer=sum(a)
for i in range(0,len(a)):
    b=b+a[i]
    c=sum(a)-b
    if (b-c>=0 and answer>b-c):
        answer=b-c
    elif (c-b>0 and answer>c-b):
        answer=c-b
print(answer)


### FIXED CODE ###

b=input()
a=input().split()
for i in range(0,len(a)):
    a[i]=int(a[i])
b=0
c=0
answer=sum(a)
for i in range(0,len(a)):
    b=b+a[i]
    c=sum(a)-b
    if (b-c>=0 and answer>b-c):
        answer=b-c
    elif (c-b>0 and answer>c-b):
        answer=c-b
print(answer)
a,b,c = map(int, input().split())
print((x-z)//(y+z))

### FIXED CODE ###

x,y,z = map(int, input().split())
print((x-z)//(y+z))
def kaijo(n):
  res = 1
  for i in range(n):
    res *= i+1
  return res

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

print(kaijo(N))

### FIXED CODE ###

n = int(input())

print(int(0.5 * n * (n+1)))
while True:
 x,y=sorted [int(x) for X in input().split()]
 if (x,y)==(0,0):
  break
 print(x,y)

### FIXED CODE ###

while True:
 x,y=sorted ([int(x) for x in input().split()])
 if (x,y)==(0,0):
  break
 print(x,y)
n,m=map(int,input().split())
d={}
for i in range(n):
  a,b=map(int,input().split())
  d[b]=a
D=sorted(d.items())
val=0
cnt=0
j=0
while cnt<=m:
  cnt+=D[j][0]
  val+=D[j][1]
  j+=1
val-=D[j][1]*(cnt-m)
print(val)


### FIXED CODE ###

n,m=map(int,input().split())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
a.sort()
totl=0
x=0
for j,k in a:
  if x+k<m:
    totl+=j*k
    x+=k
  else:
    totl+=j*(m-x)
    break
print(totl)
n, m = [int(i) for i in input().split(" ")]
a = [int(i) for i in input().split(" ")]
a = sorted(a)
q = []

for j in range(0, m):
    q.append([int(i) for i in input().split(" ")])

q = sorted(q, key=lambda k: k[1], reverse=True)

p = 0

for t in q:
    b, c = t
    pi = 0
    for i in range(b):
        if a[p + i] < c:
            a[p + i] = c
            pi += 1
        else:
            break
    p += pi

print(sum(a))

### FIXED CODE ###

n, m = [int(i) for i in input().split(" ")]
a = [int(i) for i in input().split(" ")]
a = sorted(a)
q = []

for j in range(0, m):
    q.append([int(i) for i in input().split(" ")])

q = sorted(q, key=lambda k: k[1], reverse=True)

p = 0

for t in q:
    b, c = t
    pi = 0
    for i in range(b):
        if p + i < n and a[p + i] < c:
            a[p + i] = c
            pi += 1
        else:
            break
    p += pi

print(sum(a))
n ,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort().reverse()
total = 0
for i in a:
  total += i
ok = 0
for i in range(m):
  if a[i] >= total / (4 * m):
    ok += 1
 
if ok != m:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

n ,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
total = 0
for i in a:
  total += i
ok = 0
for i in range(1, m + 1):
  if a[-i] >= total / (4 * m):
    ok += 1

if ok != m:
  print("No")
else:
  print("Yes")
While True:
    array = input().split(" ")
    a = int(array[0])
    op = array[1]
    b = int(input())

    if op == "?":
        break
    print(a, op, b)
    

### FIXED CODE ###

while True:
    a, op, b = input().split(" ")
    if op == "?":
        break
    elif op == "+":
        print( int(a) + int(b) )
    elif op == "-":
        print( int(a) - int(b) )
    elif op == "*":
        print( int(a) * int(b) )
    elif op == "/":
        print( int(a) // int(b) )
max_v = 1000000000
min_v = -1000000000

with open('in1.txt', 'r') as f:
    raw_data = f.readline()
    n = raw_data

    for r in f:
        max_v = max(max_v, r - min_v)
        min_v = min(min_v, r)
    
print(max_v)

### FIXED CODE ###

n = int(input())
data = [int(input()) for i in range(n)]

min_value = data.pop(0)
earn_value = -1000000000000
for d in data:
    earn_value = max(d - min_value, earn_value)
    min_value = min(d, min_value) 
print(earn_value)
if __name == '__main__':
    A, B, C, D = map(int, input().split())

    if B =< C or D =< A:
        print(0)
    else:
        if A < C:
            print(B-C)
        else:
            print(D - A)

### FIXED CODE ###

if __name__ == '__main__':
    A, B, C, D = map(int, input().split())

    if B <= C or D <= A:
        print(0)
    else:
        if A < C:
            if B < D:
                print(B-C)
            else:
                print(D-C)
        elif A > C:
            if B < D:
                print(B-A)
            else:
                print(D-A)
        else:
            if B < D:
                print(B-A)
            else:
                print(D-A)
def warshall_floyd(distance_table, point_size):
    for k in range(point_size):
        for i in range(point_size):
            for j in range(point_size):
                if distance_table[i][j] > distance_table[i][k] + distance_table[k][j]:
                    distance_table[i][j] = distance_table[i][k] + distance_table[k][j]

class bit:
    def __createtable():
        table = [None] * 64
        mask64 = (1 << 64) - 1
        hash = 0x03F566ED27179461
        for i in range(64):
            table[hash >> 58] = i
            hash = (hash << 1) & mask64
        return table
    
    __table = __createtable()

    def number_of_trailing_zeros(x):
        if x == 0:return 64
        mask64 = (1 << 64) - 1
        return bit.__table[((bit.lowest_one(x) * 0x03F566ED27179461) & mask64) >> 58]

    def lowest_one(i):
        return i & -i

def ccp(distance_table, point_size, v):
    if v:
        i = bit.number_of_trailing_zeros(v)
        v ^= (1 << i)
        return min(ccp(distance_table, point_size, v ^ (1 << j)) + distance_table[i][j] for j in range(point_size) if v & 1 << j)
    else:
        return 0


point_size, e = map(int, readline().split())
distance_table = [[float('inf')] * point_size for _ in range(point_size)]
cost = 0
v = 0
for _ in range(e):
    s, t, d = map(int, readline().split())
    distance_table[s][t] = min(distance_table[s][t], d)
    distance_table[t][s] = min(distance_table[t][s], d)
    v ^= 1 << s ^ 1 << t
    cost += d

warshall_floyd(distance_table, point_size)
print(cost + ccp(distance_table, point_size, v))

### FIXED CODE ###

def warshall_floyd(distance_table, point_size):
    for k in range(point_size):
        for i in range(point_size):
            for j in range(point_size):
                if distance_table[i][j] > distance_table[i][k] + distance_table[k][j]:
                    distance_table[i][j] = distance_table[i][k] + distance_table[k][j]

class bit:
    def __createtable():
        table = [None] * 64
        mask64 = (1 << 64) - 1
        hash = 0x03F566ED27179461
        for i in range(64):
            table[hash >> 58] = i
            hash = (hash << 1) & mask64
        return table
    
    __table = __createtable()

    def number_of_trailing_zeros(x):
        if x == 0:return 64
        mask64 = (1 << 64) - 1
        return bit.__table[((bit.lowest_one(x) * 0x03F566ED27179461) & mask64) >> 58]

    def lowest_one(i):
        return i & -i

def ccp(distance_table, point_size, v):
    if v:
        i = bit.number_of_trailing_zeros(v)
        v ^= (1 << i)
        return min(ccp(distance_table, point_size, v ^ (1 << j)) + distance_table[i][j] for j in range(point_size) if v & 1 << j)
    else:
        return 0


import sys
readline = sys.stdin.readline

point_size, e = map(int, readline().split())
distance_table = [[float('inf')] * point_size for _ in range(point_size)]
cost = 0
v = 0
for _ in range(e):
    s, t, d = map(int, readline().split())
    distance_table[s][t] = min(distance_table[s][t], d)
    distance_table[t][s] = min(distance_table[t][s], d)
    v ^= 1 << s ^ 1 << t
    cost += d

warshall_floyd(distance_table, point_size)
print(cost + ccp(distance_table, point_size, v))
a,b,c,d=map(int,input().split());print(max(0,min(c,d)-max(a,b))

### FIXED CODE ###

a,b,c,d=map(int,input().split());print(max(0,min(b,d)-max(a,c)))
import sys
input = sys.stdin.readline

n = int(input())
x = [list(input().split()) for _ in range(n)]

for i in range(n):
    x[i][1] = int(x[i][1])

X = []
for i in range(len(x)):
    X.append(int(x[i][1]))
xx = sorted(x)

temp = xx[0][0]
l = []
ans = []
l.append(xx[0][1])
for i in range(1, n):
    if temp == xx[i][0]:
        l.append(xx[i][1])
        flag = True
    else:
        flag = False
        l.sort(reverse=True)
        for j in l:
            ans.append(j)

        l = []
        temp = xx[i][0]
        l.append(xx[i][1])



if flag:
    l.sort(reverse=True)
    for j in l:
        ans.append(j)
    
ans = [int(a) for a in ans]

for i in range(n):
    print(X.index(ans[i]) + 1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
x = [list(input().split()) for _ in range(n)]

for i in range(n):
    x[i][1] = int(x[i][1])

X = []
for i in range(len(x)):
    X.append(int(x[i][1]))
    
xx = sorted(x)
flag = True
temp = xx[0][0]
l = []
ans = []
l.append(xx[0][1])
for i in range(1, n):
    if temp == xx[i][0]:
        l.append(xx[i][1])
        flag = True
    else:
        flag = False
        l.sort(reverse=True)
        for j in l:
            ans.append(j)

        l = []
        temp = xx[i][0]
        l.append(xx[i][1])

if flag:
    l.sort(reverse=True)
    for j in l:
        ans.append(j)
    
ans = [int(a) for a in ans]

if len(ans) != len(X):
    ans.append(xx[i][1])
for j in range(n):
    print(X.index(ans[j]) + 1)
def lcs_size():
  X = input()
  Y = input()
  
  a = len(X)
  b = len(Y)
  
  c[0][0] = 0
  for i in range(a):
    for j in range(b):
      if X[i] == Y[j]:
        c[i+1][j+1] = c[i][j] + 1
      else:
        c[i+1][j+1] = max(c[i][j+1], c[i+1][j])
      maxl = max(maxl, c[i+1][j+1])
  
  return maxl

q = input()

for i in range(q):
  print lcs_siz()

### FIXED CODE ###

def lcs_size():
  X = raw_input()
  Y = raw_input()
  a = len(X)
  b = len(Y)
  z2 = [0 for i in range(b+1)]

  for i in range(a):
    ch = X[i]
    z1 = z2 + []
    for j in range(b):
      if ch == Y[j]:
        z2[j+1] = z1[j] + 1
      elif z2[j+1] < z2[j]:
        z2[j+1] = z2[j]

  return z2[-1]

q = input()
for k in range(q):
  print lcs_size()
n=int(input())
l=[[0,0,0] for _ in range(n)]
for i in range(n):
    l[i][0],l[i][1],l[i][2]=map(int,input().split())
p=[]
for i in range(n):
    for cx in range(101):
        for cy in range(101):
            if l[i][2]>0:
                H=l[i][2]+abs(l[i][0]-cx)+abs(l[i][1]-cy)
                p.append([cx,cy,H])

p.sort()
ans=0
for i in range(101*101*n-1):
    if p[i]==p[i+1]:
        ans+=1
        if ans==n-1:
            print(' '.join(map(str,p[i])))
            break
    else:
        ans=0


### FIXED CODE ###

n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
for i in range(101):
    for j in range(101):
        H=[]
        for k in range(n):
            if l[k][2]>0:
                H.append(l[k][2]+abs(l[k][0]-i)+abs(l[k][1]-j))
            else:
                continue
        if len(set(H))==1:
            for k in range(n):
                if l[k][2]==0:
                    if H[0]-abs(l[k][0]-i)-abs(l[k][1]-j)>0:
                        break
            else:
                print(i,j,H[0])
def putty(n):
    if (n == 0):
        return [1]
    return [0]+putty(n-1)+[1]+putty(n-1)+[0]

n, x = map(int, input().split())
a = putty(n)
a = a[:x]
print(sum(a))

### FIXED CODE ###

d = int(input())

if (d ==25):
    print("Christmas")
elif (d==24):
    print("Christmas Eve")
elif (d==23):
    print("Christmas Eve Eve")
else:
    print("Christmas Eve Eve Eve")
N,M=map(int,input().split())
S=[]
C=[]
for i in range(M):
  s,c=map(int,input().split())
  S+=[s]
  C+=[c]
tf=1
ans=[]
for i in range(N):
  ans+=[-1]
for i in range(M):
  if ans[S[i]-1] ==-1:
    ans[S[i]-1]=C[i]
  else:
    if ans[S[i]-1]!=C[i]:
      tf=0
      break
    else:
      continue
for i in range(M):
  if ans[i]==-1:
    if i!=0:
      ans[i]=0
    else:
      ans[i]=1
if ans[0]==0:
  print('-1')
else:
  ansnum=''
  for i in range(M):
    ansnum+=str(ans[i])
  print(ansnum)

### FIXED CODE ###

N,M=map(int,input().split())
S=[]
C=[]
for i in range(M):
  s,c=map(int,input().split())
  S+=[s]
  C+=[c]
tf=1
ans=[]
for i in range(N):
  ans+=[-1]
for i in range(M):
  if ans[S[i]-1] ==-1:
    ans[S[i]-1]=C[i]
  else:
    if ans[S[i]-1]!=C[i]:
      tf=0
      break
    else:
      continue
for i in range(N):
  if ans[i]==-1:
    if i!=0 or (i==0 and N==1):
      ans[i]=0
    else:
      ans[i]=1
  elif ans[i]==0 and i==0 and N!=1:
    tf=0
    break
if tf==0:
  print('-1')
else:
  ansnum=''
  for i in range(N):
    ansnum+=str(ans[i])
  print(ansnum)
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_)
    a=((a+c//A_)*c_/c)%w
    #a=(a*c_//c+c_//A_)%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))
def Judge(n):
  n=int(input())
  for i in range(1,10):
    if n % i == 0 and n // i < 10:
      return "Yes"
  return "No"

n=int(input())
print(Judge(n))

### FIXED CODE ###

def Judge(n):
  for i in range(1,10):
    if n % i == 0 and n // i < 10:
      return "Yes"
  return "No"
 
n=int(input())
print(Judge(n))
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N, K = (int(_) for _ in input().split())
    x = list(int(_) for _ in input().split())
    ans = INF
    for i in range(N-K+1):
        l = i
        r = i + K-1
        ans = min(abs(x[l]) + abs(x[l]-x[r]),ans)
        
    for i in range(N-K+1):
        l = N-K+1-i
        r = N-1-i
        ans = min(abs(x[r]) + abs(x[l]-x[r]),ans)
    print(ans)
    
if __name__ == '__main__':
    main()


### FIXED CODE ###

from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N, K = (int(_) for _ in input().split())
    x = list(int(_) for _ in input().split())
    ans = INF
    for i in range(N-K+1):
        l = i
        r = i + K-1
        ans_l = abs(x[l]) + abs(x[l]-x[r])
        ans_r = abs(x[r]) + abs(x[l]-x[r])
        ans = min(ans_l,ans_r,ans)
        
    print(ans)
    
if __name__ == '__main__':
    main()
n,m = map(int,input().split())
numList = list(map(int,input().split()))

for i in numList:
	sum += i

if sum > 1/(4*m):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

n,m = map(int,input().split())
Ai = list(map(int,input().split()))

sum = 0

for i in Ai:
	sum += i

S = sorted(Ai,reverse=True)

if S[m-1] >= sum/(4*m):
  print("Yes")
else:
  print("No")
a,b=map(int,input().split())
if (a+b)%==0:
  print((a+b)//2)
else:
  print('IMPOSSIBLE')

### FIXED CODE ###

a,b=map(int,input().split())
if (a+b)%2==0:
  print((a+b)//2)
else:
  print('IMPOSSIBLE')
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

N, K = LI()
A = LI()

A.sort()
B = copy.deepcopy(A)
B.reverse()
ans = 0

def ncr(n,r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

counts = collections.Counter(B)
# max
maxs = 0
tmp_n = N
for k, v in sorted(counts.items(), key=lambda x: -x[0]):
    tmp_n -= v
    for c in range(1,min(v, K) + 1):
        tmp_k = K - c
        if tmp_k <= 0 or tmp_n <= 0:
            pass
        else:
            ans += k * ncr(v, c) * ncr(tmp_n, tmp_k)
            ans = ans % mod

print(ans, "max")
# min
tmp_n = N
for k, v in sorted(counts.items()):
    tmp_n -= v
    for c in range(1,min(v, K) + 1):
        tmp_k = K - c
        if tmp_k <= 0 or tmp_n <= 0:
            pass
        else:
            ans -= k * ncr(v, c) * ncr(tmp_n, tmp_k)
            ans = ans % mod

print(ans % mod)


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000
def LI(): return list(map(int, sys.stdin.readline().split()))

P = 10**9 + 7
N = 10000

n_ = 10**5 + 3

fun = [1 for i in range(n_+1)]
for i in range(1, n_ + 1):
    fun[i] = fun[i-1] * i % mod

rev = [1 for i in range(n_+1)]
rev[n_] = pow(fun[n_], mod-2, mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1) % mod

def nCr(n,r):
    if n <= 0 or r < 0 or r> n:return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

N, K = LI()
A = LI()

A.sort()
B = copy.deepcopy(A)
B.reverse()
ans = 0

# max
tmp_n = N
tmp_k = K - 1
for b in B:
    tmp_n -= 1
    if tmp_n < tmp_k:
        break
    ans = (ans + b * nCr(tmp_n, tmp_k))%mod

# print(ans, "max")
# min
tmp_n = N
tmp_k = K - 1
for a in A:
    tmp_n -= 1
    if tmp_n < tmp_k:
        break
    ans = (ans - a * nCr(tmp_n, tmp_k))%mod

print(ans)