Animesh and Mohit are playing a game. They have $N$ balls in front of them. All the balls are numbered, not necessarily in any order. Animesh picks a set of ${K}$ balls from the lot each time, checks this set, puts it back into the lot, and repeats this process until all possible selections have been made. At each draw, Mohit picks two balls from these ${K}$ balls -- the one with the maximum number and the one with the minimum number, and notes their difference on a paper. At the end of the game, Animesh has to tell the $\textit{Sum}$ of all the numbers on Mohit's paper. As value of this number can be very huge, you have to tell the value mod $10^9+7$.  

Input Format 

The first line contains two integers $N$ and ${K}$. 

The next line will contain a list having $N$ numbers.  

Output Format 

Print the value of $\textit{Sum}$  mod $(10^9+7)$.  

Constraints 

$1\leq N\leq10^5$ 

$1\leq K\leq N$ 

$0\leq\:\text{numbers_on_ball}\:\leq10^9$  

Sample Input  

4 2
10 20 30 40

Sample Output  

100

Explanation

There are 6 possible selections. 

1. 10 20 

2. 20 30 

3. 30 40 

4. 10 30 

5. 20 40 

6. 10 40 

Summation = 10+10+10+20+20+30 = 100

Difficulty: MEDIUM
Tags: Combinatorics

Starter code:

Solutions:
P = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = sorted(map(int, input().split()))
inv = [0, 1]
for i in range(2, n + 1):
	inv.append(P - P // i * inv[P % i] % P)
comb = 1
ans = 0
for pick in range(k - 1, n):
	ans += (a[pick] - a[n - 1 - pick]) * comb % P
	ans %= P
	comb = comb * (pick + 1) % P * inv[pick + 2 - k] % P
print(ans)


import sys
MOD = 1000000007
(N, K) = list(map(int, sys.stdin.readline().split()))
X = sorted(map(int, sys.stdin.readline().split()))
choose = 1
total = 0
for i in range(N - K + 1):
	total += choose * (X[K + i - 1] - X[N - K - i]) % MOD
	choose = choose * (K + i) * pow(i + 1, MOD - 2, MOD) % MOD
print(total % MOD)


import math
sumright = []
sumleft = []
dd = []
chooseans = []
MOD = pow(10, 9) + 7
rr = input('').split(' ')
a = int(rr[0])
b = int(rr[1])
choose = b - 2
if b == 1:
	print(0)
else:
	for r in range(0, a - 1):
		if r == choose:
			chooseans.append(1)
			continue
		if choose == 0:
			chooseans.append(1)
			continue
		if choose > r:
			chooseans.append(0)
			continue
		if r == 0:
			if chose == 0:
				chooseans.append(1)
			else:
				chooseans.append(0)
		else:
			chooseans.append(int(int(chooseans[r - 1] * r) // int(r - choose)))
	dd = input('').split(' ')
	dd = [int(y) for y in dd]
	dd.sort()
	sumright.append(0)
	for g in range(1, len(dd) + 1):
		sumright.append((sumright[g - 1] + dd[g - 1]) % MOD)
	sumleft.append(0)
	for g in range(1, len(dd) + 1):
		sumleft.append(sumleft[g - 1] + dd[len(dd) - g])
	ans = 0
	for r in range(0, a - 1):
		chain = 2 + r
		posplace = a - chain + 1
		ans += (sumleft[posplace] - sumright[posplace]) % MOD * chooseans[r] % MOD
		ans %= MOD
	print(ans % MOD)


m = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = sorted(list(map(int, input().split())))
combs = [0] * n
combs[k - 1] = 1
for i in range(k, len(combs)):
	combs[i] = combs[i - 1] * i // (i - (k - 1))
s = 0
for i in range(len(a) // 2):
	timesMax = combs[i]
	timesMin = combs[len(a) - i - 1]
	s = (s + a[i] * (timesMax - timesMin)) % m
	s = (s + a[-i - 1] * (timesMin - timesMax)) % m
print(s)


mod = 1000000007
(n, k) = str(input()).split()
(n, k) = (int(n), int(k))
a = sorted(list(map(int, str(input()).split())))
l = 1
r = 1
res = 0
if k == 1:
	print(0)
	exit()
for i in range(1, k):
	r = r * (n - i) // i
for i in range(0, n):
	if i >= k - 1:
		res = res + a[i] * l
		l = l * (i + 1) // (i - k + 2)
	if i <= n - k:
		res = res - a[i] * r
		r = r * (n - i - k) // (n - i - 1)
print(int(res) % mod)


import sys
MOD = 1000000007
(N, K) = list(map(int, sys.stdin.readline().split()))
X = sorted(map(int, sys.stdin.readline().split()))
choose = 1
total = 0
for i in range(N - K + 1):
	total += choose * (X[K + i - 1] - X[N - K - i]) % MOD
	choose = choose * (K + i) * pow(i + 1, MOD - 2, MOD) % MOD
print(total % MOD)


import sys
MOD = 1000000007
(N, K) = list(map(int, sys.stdin.readline().split()))
X = sorted(map(int, sys.stdin.readline().split()))
choose = 1
total = 0
for i in range(N - K + 1):
	total += choose * (X[K + i - 1] - X[N - K - i]) % MOD
	choose = choose * (K + i) * pow(i + 1, MOD - 2, MOD) % MOD
print(total % MOD)


import sys
MOD = 1000000007
(N, K) = list(map(int, sys.stdin.readline().split()))
X = sorted(map(int, sys.stdin.readline().split()))
choose = 1
total = 0
for i in range(N - K + 1):
	total += choose * (X[K + i - 1] - X[N - K - i]) % MOD
	choose = choose * (K + i) * pow(i + 1, MOD - 2, MOD) % MOD
print(total % MOD)


p = 1000000007
max_n = 100001
factorial = [1] * max_n
inv_factorial = [1] * max_n

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	(g, y, x) = egcd(b % a, a)
	return (g, x - b // a * y, y)

def mod_inv(a, m):
	(gcd, x, y) = egcd(a, m)
	if gcd != 1:
		return None
	return x % m

def nCr(n, r):
	if n < r:
		return 0
	return factorial[n] * inv_factorial[r] * inv_factorial[n - r] % p
for i in range(1, max_n):
	factorial[i] = i * factorial[i - 1] % p
	inv_factorial[i] = mod_inv(i, p) * inv_factorial[i - 1] % p
(n, k) = map(int, input().split())
array = sorted(map(int, input().split()))
print(sum(((nCr(i, k - 1) - nCr(n - i - 1, k - 1)) * array[i] for i in range(n))) % p)


import sys
MOD = 1000000007
(N, K) = list(map(int, sys.stdin.readline().split()))
X = sorted(map(int, sys.stdin.readline().split()))
choose = 1
total = 0
for i in range(N - K + 1):
	total += choose * (X[K + i - 1] - X[N - K - i]) % MOD
	choose = choose * (K + i) * pow(i + 1, MOD - 2, MOD) % MOD
print(total % MOD)


from math import factorial

def combinations(N, R):
	return factorial(N) // (factorial(N - R) * factorial(R))
(N, K) = tuple(map(int, input().split()))
L = list(map(int, input().split()))
L.sort()
v = combinations(N - 1, K - 1)
mins = L[0] * v
maxs = L[len(L) - 1] * v
for i in range(1, N - K + 1):
	v = v * (N - K - i + 1) // (N - i)
	mins += L[i] * v
	maxs += L[len(L) - i - 1] * v
print((maxs - mins) % (10 ** 9 + 7))


from sys import stdin
from itertools import accumulate as acc, count, combinations_with_replacement as cmbrep, takewhile as tkw, repeat as rp, dropwhile as dpw, combinations as comb
from functools import reduce
from random import randint
from collections import Counter
from math import sqrt, log, factorial
from fractions import gcd
from heapq import merge
from os.path import basename, exists, expanduser, splitext, isfile
from os import getcwd
lolPath = getcwd()
randid = '\\qosdjfoiz.txt'
home = isfile(lolPath + randid)
if home:
	filou = 'D:\\ZeDaddy\\Documents\\Hack\\combinatorics\\supMktIn12.txt'
else:
	filou = None
filou = None
if home:
	from mesures import ch, prof
trace = 0
prof = 0
tst = 0
modo = 10 ** 9 + 7

def inv(N):
	return pow(N, modo - 2, modo)

def cmbInc(K):
	for N in range(K):
		yield 0
	(c, N) = (1, K + 1)
	while True:
		yield c
		(c, N) = (c * N * inv(N - K) % modo, N + 1)

def lessStup(A, K):
	return sum((c * (H - L) for (L, H, c) in zip(reversed(A), A, cmbInc(K - 1)))) % modo
rd = open(filou) if filou else stdin
(N, K) = list(map(int, rd.readline().strip().split()))
A = list(sorted(map(int, rd.readline().strip().split())))
if home:
	cr = ch()
print(lessStup(A, K))
if home:
	print(cr.lap())


import sys
MOD = 1000000007
(N, K) = list(map(int, sys.stdin.readline().split()))
X = sorted(map(int, sys.stdin.readline().split()))
choose = 1
total = 0
for i in range(N - K + 1):
	total += choose * (X[K + i - 1] - X[N - K - i]) % MOD
	choose = choose * (K + i) * pow(i + 1, MOD - 2, MOD) % MOD
print(total % MOD)


magicmod = 10 ** 9 + 7
(N, K) = map(int, input().split())
B = [int(s) for s in input().split()]
B.sort()
combs = 1 if K > 1 else 0
for i in range(1, min(K, N - K + 1)):
	combs = (N - i) * combs // i
N -= 1
K -= 1
i = 0
total = 0
while combs:
	total = (total + combs * (B[-1 - i] - B[i])) % magicmod
	combs = (N - K) * combs // N
	N -= 1
	i += 1
print(total)


import sys
from time import time
cache = {}

def c(n, m, modulo):
	t = (n, m, modulo)
	if t in cache:
		return cache[t]
	rval = 1
	for i in range(1, m + 1):
		rval *= n - i + 1
		rval %= modulo
		rval *= pow(i, modulo - 2, modulo)
		rval %= modulo
	cache[t] = rval
	return rval

def factorial(n, modulo):
	f = 1
	for i in range(1, n + 1):
		f *= i
		f %= modulo
	return f

def get_ccache(n, k, modulo):
	cache = [None] * n
	for i in range(k + 1, n):
		cache[i] = cache[i - 1] * i * pow(i - k, modulo - 2, modulo) % modulo
	return cache

def solve_bf(aa, k, modulo):
	if k == 1:
		return 0
	aa.sort()
	sm = 0
	for i in range(len(aa)):
		u = aa[i]
		for j in range(i + k - 1, len(aa)):
			v = aa[j]
			sm += (v - u) * c(j - i - 1, k - 2, modulo)
			sm %= modulo
	return sm

def get_ccache(n, k, modulo):
	cache = [1] * n
	for i in range(k + 1, n):
		cache[i] = cache[i - 1] * i * pow(i - k, modulo - 2, modulo) % modulo
	return cache

def solve_bf2(aa, k, modulo):
	if k == 1:
		return 0
	cache = get_ccache(len(aa) + 1, k - 2, modulo)
	print('cache generated', file=sys.stderr)
	aa.sort()
	sm = 0
	for i in range(len(aa)):
		print('i=%d' % i, file=sys.stderr)
		u = aa[i]
		for j in range(i + k - 1, len(aa)):
			v = aa[j]
			delta = (v - u) * cache[j - i - 1]
			sm += delta
			sm %= modulo
	return sm

def solve(aa, k, modulo):
	if k == 1:
		return 0
	aa.sort()
	ccache = get_ccache(len(aa) + 1, k - 2, modulo)
	print('ccache generated: %d' % len(ccache), file=sys.stderr)
	(scache, sm) = ([0], 0)
	for a in aa:
		sm += a
		sm %= modulo
		scache.append(sm)
	print('scache generated', file=sys.stderr)
	sm = 0
	for l in range(k, len(aa) + 1):
		c = ccache[l - 2]
		u = scache[len(aa)] - scache[l - 1]
		v = scache[len(aa) - l + 1]
		w = (u - v) % modulo
		delta = c * (u - v) % modulo
		sm += delta
		sm %= modulo
	return sm
tm = time()
modulo = pow(10, 9) + 7
(_, k) = map(int, input().split())
aa = list(map(int, input().split()))
print(solve(aa, k, modulo))
print('time elapsed: %s' % (time() - tm), file=sys.stderr)


(n, k) = [int(x) for x in input().split()]
balls = [int(x) for x in input().split()]
balls.sort()
if k == 1:
	print('0')
elif k == n:
	print((balls[-1] - balls[0]) % (10 ** 9 + 7))
else:
	s = 0
	S = 0
	for i in range(0, k - 1):
		s += balls[i]
	for i in range(n - k + 1, n):
		S += balls[i]
	last = 1
	returnV = S - s
	for i in range(1, n - k + 1):
		S += balls[n - k + 1 - i]
		s += balls[k - 2 + i]
		last = last * (k - 2 + i) // i
		returnV += (S - s) * last
	print(returnV % (10 ** 9 + 7))


import math
m = 10 ** 9 + 7
fact = []
fact.append(1)
for i in range(100000):
	fact.append(fact[i] * (i + 1) % m)

def ncr(n, r):
	if n < r:
		return 0
	return fact[n] * pow(fact[r] * fact[n - r] % m, m - 2, m) % m % m
L = list(map(int, input().split()))
n = L[0]
k = L[1]
L = list(map(int, input().split()))
L.sort()
s = 0
for i in range(len(L)):
	s = (s + L[i] * (ncr(i, k - 1) - ncr(n - i - 1, k - 1))) % m
print(s)


def getC(K, N):
	C = {K: 1}
	mod = 10 ** 9 + 7
	fK = 1
	for k in range(2, K + 1):
		fK *= k
	mod0 = mod * fK
	fD = 1
	for n in range(K + 1, N - 1):
		fD = fD * n
		fD //= n - K
		C[n] = fD % mod
	return C

def solve(A, K):
	N = len(A)
	A.sort()
	K0 = K - 2
	C = getC(K0, N)
	mod = 10 ** 9 + 7
	s = 0
	r = 0
	for i in range(K - 1, N):
		r += A[i]
		r -= A[N - 1 - i]
	s = (s + C[K - 2] * r) % mod
	for i in range(K - 1, N - 1):
		r -= A[i]
		r += A[N - 1 - i]
		s = (s + C[i] * r) % mod
	return s
(N, K) = (int(a) for a in input().split())
A = [int(a) for a in input().split()]
print(solve(A, K))


import sys
MOD = 1000000007
(N, K) = list(map(int, sys.stdin.readline().split()))
X = sorted(map(int, sys.stdin.readline().split()))
number_ways = 1
total_sum = 0
for i in range(N - K + 1):
	total_sum += number_ways * (X[K + i - 1] - X[N - K - i]) % MOD
	number_ways = number_ways * (K + i) * pow(i + 1, MOD - 2, MOD) % MOD
print(total_sum % MOD)


import sys
MOD = 1000000007
(N, K) = list(map(int, sys.stdin.readline().split()))
X = sorted(map(int, sys.stdin.readline().split()))
choose = 1
total = 0
for i in range(N - K + 1):
	total += choose * (X[K + i - 1] - X[N - K - i]) % MOD
	choose = choose * (K + i) * pow(i + 1, MOD - 2, MOD) % MOD
print(total % MOD)


modulo = 10 ** 9 + 7
nck_dict = {}

def nck(n, k):
	if k > n:
		return 0
	if k == n or k == 0:
		return 1
	if n == 0:
		return 0
	return nck_dict[n, k]
(N, K) = [int(x) for x in input().split()]
arr = [int(x) % modulo for x in input().split()]
arr.sort()
if K == 1:
	print(0)
else:
	S = 0
	tmp = 1
	for cnt in range(K, N):
		tmp *= cnt
		tmp //= cnt - K + 1
		nck_dict[cnt, K - 1] = tmp % modulo
	for cnt in range(N):
		S += arr[cnt] * nck(cnt, K - 1) % modulo
		S -= arr[cnt] * nck(N - 1 - cnt, K - 1) % modulo
		S %= modulo
	print(S)


from functools import lru_cache
(N, K) = map(int, input().split())
x = sorted(map(int, input().split()))
(k, M) = (K - 1, 10 ** 9 + 7)

@lru_cache(maxsize=None)
def C(n):
	if n < k:
		return 0
	elif n == k:
		return 1
	else:
		return n * C(n - 1) // (n - k)
for n in range(N):
	_ = C(n)
dxsum = sum(((C(i) - C(N - i - 1)) * x[i] for i in range(N))) % M
print(dxsum)


import sys
MOD = 1000000007
(N, K) = list(map(int, sys.stdin.readline().split()))
X = sorted(map(int, sys.stdin.readline().split()))
choose = 1
total = 0
for i in range(N - K + 1):
	total += choose * (X[K + i - 1] - X[N - K - i]) % MOD
	choose = choose * (K + i) * pow(i + 1, MOD - 2, MOD) % MOD
print(total % MOD)


MOD = 10 ** 9 + 7
(n, k) = [int(i) for i in input().split()]
ball = sorted([int(i) for i in input().split()])
f = 1
s = 0
for r in range(k, n + 1):
	s = (s + f * ball[r - 1]) % MOD
	f = f * r // (r - k + 1)
f = 1
for r in range(n - k + 1, 0, -1):
	s = (s - f * ball[r - 1]) % MOD
	f = f * (n - r + 1) // (n - r - k + 2)
print(s)


def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L.append(0)
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total % m

def insertion_sort(a):
	for i in range(0, len(a) - 1):
		j = i
		while a[j] > a[j + 1] and j >= 0:
			temp = a[j]
			a[j] = a[j + 1]
			a[j + 1] = temp
			j -= 1
	return a

def merge_lists(a, b):
	final_list = []
	pos_a = 0
	pos_b = 0
	while pos_a + pos_b < len(a) + len(b):
		if pos_a < len(a) and pos_b < len(b) and (a[pos_a] <= b[pos_b]):
			final_list.append(a[pos_a])
			pos_a += 1
		elif pos_a < len(a) and pos_b < len(b) and (a[pos_a] > b[pos_b]):
			final_list.append(b[pos_b])
			pos_b += 1
		elif pos_a == len(a) and pos_b < len(b):
			final_list.append(b[pos_b])
			pos_b += 1
		elif pos_a < len(a) and pos_b == len(b):
			final_list.append(a[pos_a])
			pos_a += 1
		else:
			print('error')
	return final_list

def merge_sort(a):
	if len(a) < 10:
		return insertion_sort(a)
	else:
		return merge_lists(merge_sort(a[0:len(a) // 2]), merge_sort(a[len(a) // 2:len(a)]))

def nchoosek(n, k):
	a = 1
	if n < 0 or k < 0 or n < k:
		return 0
	for i in range(0, k):
		a *= n - i
	for j in range(1, k + 1):
		a //= j
	return a

def choose_and_calculate_second(N, K, A, modulus):
	total = 0
	max_sum = 0
	min_sum = 0
	min_choose = 1
	max_choose = 1
	for i in range(0, N):
		if i >= K - 1:
			min_sum += max_choose * A[N - 1 - i]
			min_sum %= modulus
			max_sum += max_choose * A[i]
			max_sum %= modulus
			max_choose *= i + 1
			max_choose *= pow_mod(i - K + 2, modulus - 2, modulus)
			max_choose %= modulus
	return (max_sum - min_sum) % modulus
(N, K) = [int(a) for a in input().split()]
A = [int(a) for a in input().split()]
A = merge_sort(A)
print(choose_and_calculate_second(N, K, A, pow(10, 9) + 7))


(n, k) = map(int, input().split())
factorials = [1] * (n + 1)
mod = 1000000007

def init_factorial():
	for i in range(1, len(factorials)):
		factorials[i] = i % mod * factorials[i - 1] % mod % mod

def mod_pow(a, p, mod):
	if p == 0:
		return 1
	if p % 2 == 1:
		return mod_pow(a % mod * a % mod % mod, p // 2, mod) % mod * a % mod % mod
	return mod_pow(a % mod * a % mod % mod, p // 2, mod) % mod

def inverse_mod(a, mod):
	if a % mod == 1:
		return a
	return mod_pow(a, mod - 2, mod)

def binomial(n, k):
	return factorials[n] % mod * inverse_mod(factorials[k] * factorials[n - k], mod) % mod

def solve(a):
	init_factorial()
	a = sorted(a)
	i = 0
	n1 = n - 1
	total = 0
	while i < n:
		if n1 < k - 1:
			break
		nck = binomial(n1, k - 1)
		total += nck * ((a[n - i - 1] - a[i]) % mod) % mod
		i += 1
		n1 -= 1
	return total % mod
a = list(map(int, input().split()))
print(solve(a))


import sys
MOD = 1000000007
(N, K) = list(map(int, sys.stdin.readline().split()))
X = sorted(map(int, sys.stdin.readline().split()))
choose = 1
total = 0
for i in range(N - K + 1):
	total += choose * (X[K + i - 1] - X[N - K - i]) % MOD
	choose = choose * (K + i) * pow(i + 1, MOD - 2, MOD) % MOD
print(total % MOD)


(n, k) = (int(x) for x in input().split())
a = sorted([int(x) for x in input().split()])
m = [0] * n
for i in range(k - 1):
	m[i] = 0
m[k - 1] = 1
for i in range(k, n):
	m[i] = m[i - 1] * i // (i - k + 1)
mod = 1000000007
total = 0
for i in range(n):
	total = (total + m[i] * a[i]) % mod
	total = (total - m[n - i - 1] * a[i]) % mod
print(total)


P = 10 ** 9 + 7

def inv(n):
	return pow(n, P - 2, P)
F = [1, 1]

def precomp_fact(N):
	for n in range(2, N + 1):
		F.append(n * F[-1] % P)

def binom(n, p):
	if not 0 <= p <= n:
		return 0
	return F[n] * inv(F[p]) * inv(F[n - p]) % P

def main():
	(N, K) = map(int, input().split())
	B = sorted(map(int, input().split()))
	precomp_fact(N)
	S = 0
	for i in range(N):
		S = (S + B[i] * (binom(i, K - 1) - binom(N - i - 1, K - 1))) % P
	print(S)
main()


MOD = 1000000007
(N, K) = list(map(int, input().split()))
X = sorted(map(int, input().split()))
choose = 1
total = 0
for i in range(N - K + 1):
	total += choose * (X[K + i - 1] - X[N - K - i]) % MOD
	choose = choose * (K + i) * pow(i + 1, MOD - 2, MOD) % MOD
print(total % MOD)


m = int(1000000000.0 + 7)
fac = [1] * int(200000.0 + 1)
for i in range(1, int(200000.0 + 1)):
	fac[i] = fac[i - 1] * i % m

def modpow(n, x):
	if n == 1 or x == 0:
		return 1
	if x == 1:
		return n
	res = 1
	n %= m
	while x > 0:
		if x % 2 == 1:
			res = res * n % m
		x //= 2
		n = n * n % m
	return res

def inverse(n):
	return modpow(n, m - 2)

def comb(n, r):
	if n == r or n == 0:
		return 1
	num = fac[n]
	denom = fac[r] * fac[n - r] % m
	return num * inverse(denom) % m
(n, k) = [int(x) for x in input().split()]
balls = sorted([int(x) for x in input().split()])
ans = 0
for i in range(n - k + 1):
	c = comb(n - i - 1, k - 1)
	ans = (ans - balls[i] * c % m + balls[n - i - 1] * c % m) % m
print(ans)


mod = 10 ** 9 + 7
(N, K) = map(int, input().split())
a = sorted(map(int, input().split()))
inv = [0, 1]
for i in range(2, N + 1):
	inv.append(mod - mod // i * inv[mod % i] % mod)
comb = 1
res = 0
for pick in range(K - 1, N):
	res += (a[pick] - a[N - 1 - pick]) * comb % mod
	res %= mod
	comb = comb * (pick + 1) % mod * inv[pick + 2 - K] % mod
print(res)


P = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = sorted(map(int, input().split()))
inv = [0, 1]
for i in range(2, n + 1):
	inv.append(P - P // i * inv[P % i] % P)
comb = 1
ans = 0
for pick in range(k - 1, n):
	ans += (a[pick] - a[n - 1 - pick]) * comb % P
	ans %= P
	comb = comb * (pick + 1) % P * inv[pick + 2 - k] % P
print(ans)


P = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = sorted(map(int, input().split()))
inv = [0, 1]
for i in range(2, n + 1):
	inv.append(P - P // i * inv[P % i] % P)
comb = 1
ans = 0
for pick in range(k - 1, n):
	ans += (a[pick] - a[n - 1 - pick]) * comb % P
	ans %= P
	comb = comb * (pick + 1) % P * inv[pick + 2 - k] % P
print(ans)


P = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = sorted(map(int, input().split()))
inv = [0, 1]
for i in range(2, n + 1):
	inv.append(P - P // i * inv[P % i] % P)
comb = 1
ans = 0
for pick in range(k - 1, n):
	ans += (a[pick] - a[n - 1 - pick]) * comb % P
	ans %= P
	comb = comb * (pick + 1) % P * inv[pick + 2 - k] % P
print(ans)


P = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = sorted(map(int, input().split()))
inv = [0, 1]
for i in range(2, n + 1):
	inv.append(P - P // i * inv[P % i] % P)
comb = 1
ans = 0
for pick in range(k - 1, n):
	ans += (a[pick] - a[n - 1 - pick]) * comb % P
	ans %= P
	comb = comb * (pick + 1) % P * inv[pick + 2 - k] % P
print(ans)


P = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = sorted(map(int, input().split()))
inv = [0, 1]
for i in range(2, n + 1):
	inv.append(P - P // i * inv[P % i] % P)
comb = 1
ans = 0
for pick in range(k - 1, n):
	ans += (a[pick] - a[n - 1 - pick]) * comb % P
	ans %= P
	comb = comb * (pick + 1) % P * inv[pick + 2 - k] % P
print(ans)