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

import itertools
n, m, q = list(map(int,input().split()))
sets = [list(map(int,input().split())) for i in range(q)]
#print(sets)
mx = 0
nums = list(range(1,m+1))
for h in itertools.combinations_with_replacement(nums,n):
    mxtemp = 0
    for j in range(q):
        a = sets[j][0]
        b = sets[j][1]
        if list(h)[b-1] - list(h)[a-1] == sets[j][2]:
            mxtemp += sets[j][3]
    if mxtemp > mx:
        mx = mxtemp
print(mx)

### FIXED CODE ###

import itertools
n, m, q = list(map(int,input().split()))
sets = [list(map(int,input().split())) for i in range(q)]
#print(sets)
mx = 0
nums = list(range(1,m+1))
for h in itertools.combinations_with_replacement(nums,n):
    mxtemp = 0
    for j in range(q):
        a = sets[j][0]
        b = sets[j][1]
        if list(h)[b-1] - list(h)[a-1] == sets[j][2]:
            mxtemp += sets[j][3]
    if mxtemp > mx:
        mx = mxtemp
print(mx)
### BUGGY CODE ###

from collections import defaultdict,deque
import bisect

N = int(input())
A = list(map(int,input().split()))
graph = defaultdict(deque)
for _ in range(0,N-1):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

arrive = [False] * (N+1)
dp_dict = dict()
dp_dict[1] = [A[0]]

ans = [None] *(N+1)
def dfs(s):
    stack = deque([s])
    while stack:
        v = stack[-1]
        arrive[v] = True
        if graph[v]:
            w = graph[v].popleft()
            if arrive[w] == False:
                tar = A[w-1]
                dp_dict[w] = dp_dict[v].copy()
                if tar > dp_dict[w][-1]:
                    dp_dict[w].append(tar)
                else:
                    dp_dict[w][bisect.bisect_left(dp_dict[w], tar)] = tar
                ans[w] = len(dp_dict[w])
                stack.append(w)

        else:
            stack.pop()


dfs(1)
ans[1] = 1

for i in ans[1::]:
    print(i)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
 
N = int(input())
A = tuple(map(int, input().split()))
graph = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
 
ans = [-1] * (N + 1)
inf = 10**18
LIS = [inf] * (N + 1)
 
def DFS(s, parent=0):
    a = A[s - 1]
    i = bisect.bisect_left(LIS, a)
    v = LIS[i]
    LIS[i] = a
    ans[s] = bisect.bisect_left(LIS, inf)
    for t in graph[s]:
        if t == parent:
            continue
        DFS(t, s)
    LIS[i] = v
    return
 
DFS(1)
print(*ans[1:], sep="\n")
### BUGGY CODE ###

import queue
def cal():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    q = queue.Queue()
    INF = float('inf')
    counts = [[INF]*w for _ in range(h)]
    
    for i in range(w):
        for j in range(h):
            if a[j][i] == '#':
                q.put([i, j])
                counts[j][i] = 0

    while not q.empty():
        x, y = q.get()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x0 = x+j
            y0 = y+i
            if 0 <= x0 < w and 0 <= y0 < h:
                if counts[y][x]+1 < counts[y0][x0]:
                    a[y0][x0] = '#'
                    counts[y0][x0] = counts[y][x]+1
                    q.put([x0, y0])
    ans = 0
    for i in counts:
        ans = max(ans, max(i))
    print(ans)

cal()


### FIXED CODE ###

from collections import deque

def cal():
    h, w = map(int, input().split())
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False]*w+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    for i in range(h):
        a = input()
        for j in range(w):
            if a[j] == '#':
                q.append([i+1, j+1, 0])
                counts[i+1][j+1] = True

    while q:
        x, y, z = q.popleft()    
        if not counts[x+1][y]:
            counts[x+1][y] = True
            q.append([x+1, y, z+1])
        if not counts[x-1][y]:
            counts[x-1][y] = True
            q.append([x-1, y, z+1])
        if not counts[x][y+1]:
            counts[x][y+1] = True
            q.append([x, y+1, z+1])
        if not counts[x][y-1]:
            counts[x][y-1] = True
            q.append([x, y-1, z+1])
    print(z)
    

cal()
### BUGGY CODE ###

N, X, Y = map(int, input().split())
X -= 1
Y -= 1
edge = []
for i in range(N):
    edge.append([])
    if i != 0:
        edge[i].append(i - 1)
    if i != N-1:
        edge[i].append(i + 1)
edge[X].append(Y)
edge[Y].append(X)

answer = [0] * (N - 1)
for i in range(N):
    queue = []
    for e in edge[i]:
        queue.append(e)
    counter = 0
    d = [N + 10] * N
    d[i] = 0
    # i is start
    while counter < len(queue):
        node = queue[counter]
        min_dist = N + 10
        for e in edge[node]:
            if d[e] < min_dist:
                min_dist = d[e]
            if d[e] == N + 10:
                queue.append(e)
        d[node] = min_dist + 1
        counter += 1
    for i in d:
        answer[i] += 1
for a in answer[1:]:
    print(a//2)
print('0')

### FIXED CODE ###

N, X, Y = map(int, input().split())
X -= 1
Y -= 1
edge = []
for i in range(N):
    edge.append([])
    if i != 0:
        edge[i].append(i - 1)
    if i != N-1:
        edge[i].append(i + 1)
edge[X].append(Y)
edge[Y].append(X)

answer = [0] * (N - 1)
for i in range(N):
    queue = []
    for e in edge[i]:
        queue.append(e)
    counter = 0
    d = [N + 10] * N
    d[i] = 0
    # i is start
    while counter < len(queue):
        node = queue[counter]
        min_dist = N + 10
        for e in edge[node]:
            if d[e] < min_dist:
                min_dist = d[e]
            if d[e] == N + 10:
                queue.append(e)
        d[node] = min_dist + 1
        counter += 1
    for i in d:
        answer[i] += 1
for a in answer[1:]:
    print(a//2)
print('0')
### BUGGY CODE ###

def main():
  s = input()
  divisor = 10 ** 9 + 7
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  lut = [i % 13 for i in range(130)]
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      for j in range(13):
        dpij = dpi[j]
        j10 = j * 10
        for k in range(10):
          dpi1[lut[j10 + k]] += dpij
    else:
      t = int(s[i])
      for j in range(13):
        dpi1[lut[j * 10 + t]] += dpi[j]
    for k in range(13):
      dp[i + 1][k] %= divisor
  print(dp[len(s)][5])
main()


### FIXED CODE ###

s = ''.join(reversed(input()))
multiplier = 1
divisor = 10 ** 9 + 7
p = [0 for i in range(13)]
if s[0] != '?':
  p[int(s[0])] = 1
else:
  for j in range(10):
    p[j] = 1
for i in range(1, len(s)):
  multiplier = (10 * multiplier) % 13
  np = [0 for j in range(13)]
  if s[i] != '?':
    r = int(s[i]) * multiplier
    for j in range(13):
      np[(j + r) % 13] = p[j]
  else:
    for j in range(10):
      r = j * multiplier
      for k in range(13):
        np[(k + r) % 13] += p[k]
  for j in range(13):
    p[j] = np[j] % divisor
print(p[5] % divisor)
### BUGGY CODE ###


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

ans = []
for i in range(0, 2 ** N):
    x = 1
    a = 0
    for n in range(N):
        if i & x:
            a += V[n] - C[n]
        x = x << 1
    ans.append(a)
print(max(ans))

### FIXED CODE ###


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

ans = 0
for i in range(N):
    x = V[i] - C[i]
    if x > 0:
        ans += x
print(ans)
### BUGGY CODE ###

n=int(input())
lamp=[]
status=1
count=0
possible=1
for i in range(n):
  p=int(input())
  lamp.append(p)
if 2 in set(lamp):
  while status!=2 or count==n:
    status=lamp[status-1]
    count+=1
  if count!=n:
    print(count)
  else:
    print(-1)
else:
  print(-1)

### FIXED CODE ###

n=int(input())
lamp=[]
status=1
count=0
possible=0
for i in range(n):
  p=int(input())
  lamp.append(p)
while status!=2:
  if lamp[status-1]!=0:
    var=lamp[status-1]
    lamp[status-1]=0
    status=var
    count+=1
  else:
    possible+=1
    break
if possible==0:
  print(count)
else:
  print(-1)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
max = 0
x = 0
for i in range(n - k + 1):
    s = sum(p[i : i + k])
    if s > max:
        max = s
        x = i
ans = 0
for i in range(x, x + k):
    ans += (p[i] + 1) / 2
print('{:.12f}'.format(ans))

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
s = max = sum(p[0 : k])
x = 0
for i in range(0, n - k):
    s = s - p[i] + p[i + k]
    if s > max:
        max = s
        x = i + 1
ans = 0
for i in range(x, x + k):
    ans += (p[i] + 1) / 2
print('{:.12f}'.format(ans))
### BUGGY CODE ###

import heapq

xs, ys, xt, yt = map(int, input().split())
N = int(input())
XYR = [list(map(int, input().split())) for i in range(N)]
XYR.append([xs, ys, 0])
XYR.append([xt, yt, 0])
L = [[9999999999]*(N+2) for i in range(N+2)]
for i in range(N+2):
    for j in range(i, N+2):
        x1, y1, r1 = XYR[i]
        x2, y2, r2 = XYR[j]
        L[i][j] = L[j][i] = max(((x1-x2)**2+(y1-y2)**2)**0.5-r1-r2, 0.0)


# 計算量 O((E+V)logV)
num = N+2  # グラフのノード数
start = num-2

distance = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する
distance[start] = 0
q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
heapq.heappush(q, (0, start))  # 始点をpush

while len(q) != 0:
    prov_cost, src = heapq.heappop(q)  # pop

    # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
    if distance[src] < prov_cost:
        continue

    # 他の頂点の探索
    for destination, cost in enumerate(L[src]):
        if distance[destination] > distance[src] + cost:
            distance[destination] = distance[src] + cost  # distの更新
            heapq.heappush(q, (distance[destination], destination))  # キューに新たな仮の距離の情報をpush
            prev[destination] = src  # 前の頂点を記録

print(distance[-1])


### FIXED CODE ###

import heapq

xs, ys, xt, yt = map(int, input().split())
N = int(input())
XYR = [list(map(int, input().split())) for i in range(N)]
XYR.append([xs, ys, 0])
XYR.append([xt, yt, 0])
L = [[9999999999]*(N+2) for i in range(N+2)]
for i in range(N+2):
    for j in range(i, N+2):
        x1, y1, r1 = XYR[i]
        x2, y2, r2 = XYR[j]
        L[i][j] = L[j][i] = max(((x1-x2)**2+(y1-y2)**2)**0.5-r1-r2, 0.0)


# 計算量 O((E+V)logV)
num = N+2  # グラフのノード数
start = num-2

distance = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する
distance[start] = 0
q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
heapq.heappush(q, (0, start))  # 始点をpush

while len(q) != 0:
    prov_cost, src = heapq.heappop(q)  # pop

    # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
    if distance[src] < prov_cost:
        continue

    # 他の頂点の探索
    for destination, cost in enumerate(L[src]):
        if distance[destination] > distance[src] + cost:
            distance[destination] = distance[src] + cost  # distの更新
            heapq.heappush(q, (distance[destination], destination))  # キューに新たな仮の距離の情報をpush
            prev[destination] = src  # 前の頂点を記録

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

import sys

N = int(input())
a = []

for _ in range(N):
    x = int(sys.stdin.readline())
    if x in a:
        a.remove(x)
    else:
        a.append(x)
        
print(len(a))

### FIXED CODE ###

from collections import defaultdict

N = int(input())

a = defaultdict(lambda: 0)

for _ in range(N):
    x = int(input())
    if a[x]:
        a[x] -= 1
    else:
        a[x] += 1

print(sum(a.values()))
### BUGGY CODE ###

INF = float("inf")
dp = [[0] * 2 for _ in range(1000005)]

s = input()
s = s[::-1]
s += "0"
n = len(s)

for i in range(n+1):
    for j in range(2):
        dp[i][j] = INF
dp[0][0] = 0

for i in range(n):
    for j in range(2):
        x = int(s[i])
        x += j
        for a in range(10):
            ni = i+1
            nj = 0
            b = a- x
            if b < 0:
                nj = 1
                b += 10
            dp[ni][nj] = min(dp[ni][nj], dp[i][j]+a+b)

ans = dp[n][0]
print(ans)

### FIXED CODE ###

dp = [0, 1]

s = input()
s = s[::-1]
s += "0"

for i in range(len(s)):
    dp0, dp1 = dp
    dp[0] = min(dp0, dp1 + 1) + int(s[i])
    dp[1] = min(dp0, dp1 - 1) + 10 - int(s[i])

print(min(dp))
### BUGGY CODE ###

import sys 
from collections import deque
import itertools
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def main():
    tmp = deque(LI())
    n,k = tmp.popleft(),tmp.popleft()
    a = LI()
    for _ in range(k):
        table = [0]*(n+1)
        for j in range(n):
            table[max(0,j-a[j])] += 1
            table[min(n-1,j+a[j])+1] -=1
        a = list(itertools.accumulate(table))
    for i in range(n):
        print(str(a[i])+' ',end='')
    return

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
from itertools import accumulate

def solve(n,k,a):
    for _ in range(k):
        if a==[n]*n:    return a
        t = [0]*(n+1)
        for i,x in enumerate(a):
            t[max(0,i-x)] += 1
            t[min(n,i+x+1)] -=1
        a = list(accumulate(t))[:-1]
    return a

n,k = map(int,sys.stdin.readline().rstrip().split())
a = list(map(int,sys.stdin.readline().rstrip().split()))

print(*solve(n,k,a))
### BUGGY CODE ###

def main():
    import sys
    from collections import defaultdict,deque
    from itertools import count
    input=sys.stdin.readline
    n=int(input())
    d=defaultdict(count().__next__)
    es=[]
    for i in range(1,n+1):
        *a,=map(int,input().split())
        for j,k in zip(a,a[1:]):
            x,y=i,j
            if y<x:x,y=y,x
            v,w=i,k
            if w<v:v,w=w,v
            es+=(d[x*n+y],d[v*n+w]),
    s=len(d)
    outs=[[]for _ in range(s)]
    ins=[0]*s
    f=set(range(s))
    for i,j in es:
        outs[i]+=j,
        f-={j}
        ins[j]+=1
    q=deque(f)
    l=0
    data=[0]*s
    m=0
    while q:
        i=q.popleft()
        l+=1
        t=data[i]+1
        if t>m:m=t
        for j in outs[i]:
            ins[j]-=1
            if ins[j]<1:q+=j,
            if t>data[j]:data[j]=t
    print(-(l<s)or m)
main()

### FIXED CODE ###

def main():
    from collections import defaultdict,deque
    from itertools import count
    (n,),*a=[list(map(int,t.split()))for t in open(0)]
    d=defaultdict(count().__next__)
    es=[]
    for i,b in enumerate(a,1):
        for j,k in zip(b,b[1:]):
            x,y=i,j
            if y<x:x,y=y,x
            v,w=i,k
            if w<v:v,w=w,v
            es+=(d[x*n+y],d[v*n+w]),
    s=len(d)
    outs=[[]for _ in range(s)]
    ins=[0]*s
    f=set(range(s))
    for i,j in es:
        outs[i]+=j,
        f-={j}
        ins[j]+=1
    q=deque(f)
    r=[]
    data=[0]*s
    m=0
    while q:
        i=q.popleft()
        r+=i,
        t=data[i]+1
        if t>m:m=t
        for j in outs[i]:
            ins[j]-=1
            if ins[j]<1:q+=j,
            if t>data[j]:data[j]=t
    print(-(len(r)<s)or m)
main()
### BUGGY CODE ###

s = input()
p = 2019
n = len(s)
u_i = []
ans = 0
l = [0 for i in range(p)]
l[0] = 1
for i in range(n):
    l[int(s[i:])%p] += 1

for i in l:
    ans+= i*(i-1)//2
print(ans)

### FIXED CODE ###

p = 2019
s = input()
n = len(s)
l = [0 for i in range(p)]
l[0] = 1
ten = 1
cnt = 0
 
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    for i in range(n):
        cnt = (cnt + int(s[-i-1]) * ten) % p
        l[cnt] += 1
        ten = (ten * 10) % p
    for i in l:
        if i > 1:
            ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

L, R = map(int, input().split())
ans = 2018
for i in range(L, R):
  if i % 2019 == 0:
    ans = 0
    break
  for j in range(L+1, R+1):
    ans = min(ans, i * j % 2019)
print(ans)

### FIXED CODE ###

L, R = map(int, input().split())
ans = 2018
for i in range(L, R):
  if i % 2019 == 0:
    ans = 0
    break
  for j in range(L+1, R+1):
    if j % 2019 == 0:
      ans = 0
      break
    ans = min(ans, i * j % 2019)
print(ans)
### BUGGY CODE ###

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

l = []

for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    bit_c = 0
    for x in c:
        bit_c = bit_c | (1<<(x-1))
    l.append([a,bit_c])


ans = 10**9

for i in range(2 ** m):
    cost = 0
    chk = 0
    for j in range(m):
        if ((i>>j) &1):
            cost += l[j][0]
            chk = chk | l[j][1]
    if chk == 2**n-1:
        ans = min(ans,cost)

if ans == 10**9:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

l = []

for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    bit_c = 0
    for x in c:
        bit_c = bit_c | (1<<(x-1))
    l.append([a,bit_c])

dp = [[float("INF")]*(2**n+1) for _ in range(m+1)]

dp[1][0] = 0
dp[1][l[0][1]] = l[0][0]

for i in range(2,m):
    for j in range(2**n):
        dp[i][j] = dp[i-1][j]
    for j in range(2**n):
        dp[i][j | l[i-1][1]] = min(dp[i][j|l[i-1][1]],dp[i-1][j|l[i-1][1]],dp[i-1][j]+l[i-1][0])

if dp[m-1][2**n-1] >= 10**12:
    print(-1)
else:
    print(dp[m-1][2**n-1])
### BUGGY CODE ###

from bisect import bisect_left, bisect_right

def solve():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))

    As.sort()
    i = bisect_left(As, K)
    Bs = As[:i]
    M = len(Bs)

    def isOK(x):
        isFounds = [False] * K
        isFounds[0] = True
        for i, B in enumerate(Bs):
            if i == x: continue
            for s in reversed(range(K-B)):
                if isFounds[s]:
                    isFounds[s+B] = True
        return any(isFounds[K-Bs[x]:])

    ng, ok = -1, M
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    print(ok)


solve()


### FIXED CODE ###

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

As.sort(reverse=True)

minAOK = As[0]+1
sumSubsets = set([0])
for A in As:
    if A >= K:
        minAOK = A
        continue
    for sumSubset in sumSubsets.copy():
        if K - A <= sumSubset:
            minAOK = A
        if sumSubset + A < K:
            sumSubsets.add(sumSubset + A)

ans = len([A for A in As if A < minAOK])
print(ans)
### BUGGY CODE ###

import math 
 
K = int(input())
sum = 0
 
for i in range(K):
    for j in range(K):
        for k in range(K):
            sum += math.gcd(math.gcd((i+1),(j+1)),(k+1))
 
print(sum)

### FIXED CODE ###

from math import gcd

K = int(input())
sum = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            sum += gcd(gcd(i,j),k)

print(sum)
### BUGGY CODE ###

from collections import deque,Counter

N,K = map(int,input().split())
R,S,P = map(int,input().split())
T = input()

T = T.translate(str.maketrans({'r': 'p', 's': 'r','p': 's'}))
cnt = Counter(T)
dic = {"r":R, "s":S, "p":P}

ans = cnt["r"]*R + cnt["s"]*S +cnt["p"]*P
checked = []
for i in range(N-K+1):
    if i%K in checked:
        continue
    else:
        j = i
        tmp = 0
        while j <len(T):
            if tmp == T[j]:
                ans -= dic[T[j]]
                tmp = 0
            else:
                tmp = T[j]
            j += K
        checked.append(i%K)

print(ans)

### FIXED CODE ###

from collections import deque,Counter

N,K = map(int,input().split())
R,S,P = map(int,input().split())
T = input()

T = T.translate(str.maketrans({'r': 'p', 's': 'r','p': 's'}))
cnt = Counter(T)
dic = {"r":R, "s":S, "p":P}

ans = cnt["r"]*R + cnt["s"]*S +cnt["p"]*P
checked = []
for i in range(N-K+1):
    if i%K in checked:
        continue
    else:
        j = i
        tmp = 0
        while j <len(T):
            if tmp == T[j]:
                ans -= dic[T[j]]
                tmp = 0
            else:
                tmp = T[j]
            j += K
        checked.append(i%K)

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

import math
k = int(input())

ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      ans += math.gcd(a,math.gcd(b,c))

print(ans)


### FIXED CODE ###

import math
k = int(input())

ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    tmp = math.gcd(a,b)
    for c in range(1,k+1):
      ans += math.gcd(c,tmp)

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

import sys
from math import factorial

input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))

mod = 10**9 + 7

a.sort()

li = []
for i in range(n-1):
    li.append(a[i+1]-a[i])

ans = 0

dp = [1]
for i in range(1,n+1):
    dp.append(dp[-1]*i)

def comb(n,k):
    return dp[n] // dp[k] // dp[n-k]

comb1 = comb(n,k)

for i in range(n-1):
    if i+1 < k and n-i-1 < k:
        ans += li[i] * comb1
    elif i+1 < k:
        ans += li[i] * (comb1 - comb(n-i-1,k))
    elif n-i-1 < k:
        ans += li[i] * (comb1 - comb(i+1,k))
    else:
        ans += li[i] * (comb1 - comb(n-i-1,k) - comb(i+1,k))

print(ans%mod)


### FIXED CODE ###

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

mod = 10**9 + 7

a.sort(reverse = True)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """

    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

comb = Combination(100010)
ans = 0

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

a = a[::-1]

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

print(ans)