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

import numpy as np
def main():
    N,W = map(int,input().split())
    wvlist = []
    dp =[[0 for i in range(W+1)] for j in range(N+1)]
    for i in range(N):
        lista = list(map(int,input().split()))
        wvlist.append(lista)
    sumax = sum(wvlist[i][0] for i in range(N))
    sumin = min(wvlist[i][0] for i in range(N))
    vamax = sum(wvlist[i][1] for i in range(N))
    if sumax <= W:
        print(vamax)
    elif sumin > W:
        print(0)
    else:
        for i in range(N):
            for j in range(W+1):
                if wvlist[i][0] <= j:
                    dp[i+1][j] = max(dp[i+1][j],dp[i][j-wvlist[i][0]]+wvlist[i][1])
                else:
                    dp[i+1][j] = dp[i][j]
        print(np.amax(dp))            
        
    
    
main()

### FIXED CODE ###

N,W = map(int,input().split())
array = []
for i in range(N):
    wv = list(map(int,input().split()))
    array.append(wv)
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j-array[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j],dp[i][j-array[i][0]]+array[i][1])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[-1][-1])
### BUGGY CODE ###

casen=0
if casen==0:
    a=[]
    c=[]
    n=int(input())
    for i in range(n):
        ai,bi=map(int,input().split())
        a.append([ai,bi])
    for i in range(n):
        ci,di=map(int,input().split())
        c.append([ci,di])
elif casen==1:
    n=3
    a=[[2,0],[3,1],[1,3]]
    c=[[4,2],[0,4],[5,5]]
elif casen==2:
    n=3
    a=[[0,0],[1,1],[5,2]]
    c=[[2,3],[3,4],[4,5]]
elif casen==3:
    n=2
    a=[[2,2],[3,3]]
    c=[[0,0],[1,1]]
elif casen==4:
    n=5
    a=[[0,0],[7,3],[2,2],[4,8],[1,6]]
    c=[[8,5],[6,9],[5,4],[9,1],[3,7]]
elif casen==5:
    n=5
    a=[[0,0],[1,1],[5,5],[6,6],[7,7]]
    c=[[2,2],[3,3],[4,4],[8,8],[9,9]]

a.sort()
c.sort()

t=[]
for ia in range(n):
    s=[]
    for ic in range(n):
        if a[ia][0]<c[ic][0] and a[ia][1]<c[ic][1]:
            s.append(ic)
    t.append([len(s),s])
#    print(s)
    
t.sort()
#print("t: ",t)

tyn2=[]
icnt=0

def pcnt(icnt,ia,t,n,tyn2,icntmax):
#    print("icnt:",icnt," ia:",ia," n:",n," icntmax:",icntmax,",",t[ia][1],",",tyn2)
    ia1=ia
    if ia>=n-1:
        icntmax=max(icnt,icntmax)
#        print("return icnt:",icnt," icntmax:",icntmax,tyn2)
        if len(tyn2)>0:
            tyn2.pop(-1)
        ia=ia-1
        return icntmax,ia
#    print(ia)
    icnt1=icnt
    for it in t[ia][1]:
        ia=ia1+1
        if not it in tyn2:
            icnt=icnt1+1
            tyn2.append(it)
            icntmax,ia=pcnt(icnt,ia,t,n,tyn2,icntmax)
    ia=ia+1
    icntmax,ia=pcnt(icnt,ia,t,n,tyn2,icntmax)
#    tyn2.pop(-1)
    return icntmax,ia

ia=-1    
icntmax=0
icntmax,ia=pcnt(icnt,ia,t,n,tyn2,icntmax)

print(icntmax)        
    


### FIXED CODE ###

casen=0
if casen==0:
    a=[]
    c=[]
    n=int(input())
    for i in range(n):
        ai,bi=map(int,input().split())
        a.append([ai,bi])
    for i in range(n):
        ci,di=map(int,input().split())
        c.append([ci,di])
elif casen==1:
    n=3
    a=[[2,0],[3,1],[1,3]]
    c=[[4,2],[0,4],[5,5]]
elif casen==2:
    n=3
    a=[[0,0],[1,1],[5,2]]
    c=[[2,3],[3,4],[4,5]]
elif casen==3:
    n=2
    a=[[2,2],[3,3]]
    c=[[0,0],[1,1]]
elif casen==4:
    n=5
    a=[[0,0],[7,3],[2,2],[4,8],[1,6]]
    c=[[8,5],[6,9],[5,4],[9,1],[3,7]]
elif casen==5:
    n=5
    a=[[0,0],[1,1],[5,5],[6,6],[7,7]]
    c=[[2,2],[3,3],[4,4],[8,8],[9,9]]

c.sort()
a.sort(key=lambda x:x[1])
#a.reverse()

icnt=0
ic2=0
for ic in range(len(c)):
    for ia in range(len(a)-1,-1,-1):
        if a[ia][0]<c[ic][0] and a[ia][1]<c[ic][1]:
            icnt=icnt+1
            del a[ia]
            break
        else:
            continue
        break

print(icnt)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(1, N):
    for j in range(i, N):
        ans += A[i - 1] * A[j]
print(ans % (10**9 + 7))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
s = sum(A) % mod
ans = 0
for i in range(N):
    s -= A[i]
    if 0 > s:
        s += mod
    ans += A[i] * s
    ans %= mod
print(ans)
### BUGGY CODE ###

s=input()
MOD=10**9+7
dp=[[0 for i in range(13)] for j in range(2)]

if s[0]=='?':
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(s[0])]=1

i=1
for c in s[1:]:
  c = -1 if c=='?' else int(c)

  D=dp[i%2]
  S=dp[(i-1)%2]
  if c==-1:
    for k in range(13):
      for j in range(k*10,k*10+10):
        D[j%13]+=S[k]
  else:
    for k in range(13):
      D[(k*10+c)%13]+=S[k]

  for j in range(13):
    S[j]=0
    D[j]%=MOD
  i += 1

print(dp[(i-1)%2][5])


### FIXED CODE ###

S=input()
a=[0]*13
a[0]= 1

for c in S:
  dp=[0]*13
  for i in range(13):
    dp[(i*10)%13]=a[i]%(10**9+7)
  dp+=dp

  if c=='?':
    for i in range(13):
      a[i]=sum(dp[i+4:i+14])
  else:
    for i in range(13):
      a[i]=dp[i+13-int(c)]

print(a[5]%(10**9+7))
### BUGGY CODE ###

import itertools
import numpy
N, M, Q = map(int,input().split())
abcd = []*Q
d_list = []
sum_d = 0
for _ in range(Q):
  abcd.append(list(map(int,input().split())))

A = [chr(i) for i in range(N)]

for A in itertools.product(range(1,M+1),repeat=N):
  flag = True
  for n in range(N-1):
    if A[n+1] < A[n]:
      flag = False
  if flag == True:
    for i in range(Q):
      if A[abcd[i][1]-1]-A[abcd[i][0]-1] == abcd[i][2]:
        d_list.append(abcd[i][3])
        
    if sum_d <= sum(d_list):
      sum_d = sum(d_list)
    d_list.clear()
print(sum_d)

### FIXED CODE ###

import itertools
import numpy
N, M, Q = map(int,input().split())
abcd = []*Q
d_list = []
sum_d = 0
for _ in range(Q):
  abcd.append(list(map(int,input().split())))

A = [1 for i in range(N)]
for A in itertools.combinations_with_replacement(range(1, M+1), N):
  for i in range(Q):
    if A[abcd[i][1]-1]-A[abcd[i][0]-1] == abcd[i][2]:
      d_list.append(abcd[i][3])
  if sum_d <= sum(d_list):
    sum_d = sum(d_list)
  d_list.clear()
print(sum_d)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    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):
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
                
    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]

    
f=lambda:map(int,input().split())
N,M=f()
uf=UnionFind(N+1)

p=list(f())
for _ in [0]*M:
    uf.unite(*f())

index_list=[[] for _ in [0]*(N+1)]
group_list=[[] for _ in [0]*(N+1)]
for i in range(1,N+1):
    index_list[uf.find_root(i)].append(p.index(i)+1)
    group_list[uf.find_root(i)].append(i)
    
res=0
for i in range(1,N+1):
    if i==uf.find_root(i):
        res+=len(set(index_list[i]) & set(group_list[i]))

print(res)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    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):
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
                
    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]

    
f=lambda:map(int,input().split())
N,M=f()
uf=UnionFind(N+1)

p=list(f())
p_index=[[] for _ in [0]*(N+1)]
for i in range(1,N+1):
    p_index[p[i-1]]=i
for _ in [0]*M:
    uf.unite(*f())


index_list=[[] for _ in [0]*(N+1)]
group_list=[[] for _ in [0]*(N+1)]

for i in range(1,N+1):
    index_list[uf.find_root(i)].append(p_index[i])
    group_list[uf.find_root(i)].append(i)
    
res=0
for i in range(1,N+1):
    if i==uf.find_root(i):
        res+=len(set(index_list[i]) & set(group_list[i]))

print(res)
### BUGGY CODE ###

n = int(input())
l = input().split()

for i in range(0,n):
	l[i] = int(l[i])

counting = 0
list_i = []
for i in range(0,100000):
	counting = 0
	for j in range(n):
		if (l[j] == i or l[j] == i-1 or l[j] == i+1):
			counting += 1		
	list_i.append(counting)
			 
print(max(list_i))

### FIXED CODE ###

n = int(input())
l = input().split()

for i in range(0,n):
	l[i] = int(l[i])

dict_i = {}
for i in range(-1,100001):
	dict_i[i] = 0
	
for j in range(n):
	dict_i[l[j]] += 1
	dict_i[l[j] + 1] += 1
	dict_i[l[j] - 1] += 1
print(max(dict_i.values()))
### BUGGY CODE ###

n,m=map(int,input().split())
gate=[]
for i in range(m):
    gate.append([int(i) for i in input().split()])
count=0
for k in range(1,n+1):
    g=0
    for j in gate:
        if j[0]<=k<=j[1]:
            g+=1
    if g==m:
        count+=1
print(count)


### FIXED CODE ###

n,m=map(int,input().split())
card=[]
L=1
R=n
for i in range(m):
    card.append([int(i) for i in input().split()])
for j in card:
    if j[0]<=R:
        if L<=j[0]:
            L=j[0]
            
    else:
        print(0)
        quit()
    if L<=j[1]:
        if j[1]<=R:
            R=j[1]
            
    else:
        print(0)
        quit()
print(R-L+1)
### BUGGY CODE ###

n = int(input())
S = input()

ans = 0
for i in range(1000):
    pin = str(i).zfill(3)

    ind = 0
    for s in S:
        if pin[ind] == s:
            ind += 1
        if ind >= 3:
            ans += 1
            break

print(ans)


### FIXED CODE ###

from collections import defaultdict
n = int(input())
S = input()

d = defaultdict(list)
for i, s in enumerate(S):
    d[s].append(i)

ans = 0
for p in range(1000):
    p1, p2, p3 = str(p).zfill(3)

    i0 = -1
    for i in d[p1]:
        if i > i0:
            i1 = i
            break
    else:
        continue

    for i in d[p2]:
        if i > i1:
            i2 = i
            break
    else:
        continue

    for i in d[p3]:
        if i > i2:
            ans += 1
            break


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

import collections
MOD = 2019

def mod(n):         
  return n % MOD

def modpow(a, n):   #mod(a**n)を高速で求める
    res = 1  
    digit = len(str(bin(n))) - 2
    for i in range(digit):
      if (n >> i) & 1:
        res *= mod(a)
        res = mod(res)
      a = mod(a**2)
    return mod(res)

s = input()
lst = []
n = 0
for i in range(len(s)):
  n += mod(int(s[len(s)-i-1])*modpow(10, i))
  lst.append(mod(n))
lst.append(0)
ans = 0
for i in range(2018):
  m = lst.count(i)
  ans += m*(m-1)//2
print(ans)

### FIXED CODE ###

import collections
MOD = 2019

def mod(n):         
  return n % MOD

def modpow(a, n):   #mod(a**n)を高速で求める
    res = 1  
    digit = len(str(bin(n))) - 2
    for i in range(digit):
      if (n >> i) & 1:
        res *= mod(a)
        res = mod(res)
      a = mod(a**2)
    return mod(res)

s = input()
lst = []
n = 0
for i in range(len(s)):
  n += mod(int(s[len(s)-i-1])*modpow(10, i))
  lst.append(mod(n))
lst.append(0)
lst.sort()
ans = 0
counter = 1
stock = lst[0]
for i in range(1, len(lst)):
  if stock == lst[i]:
    counter += 1
  else:
    ans += counter*(counter - 1)//2
    counter = 1
    stock = lst[i]
if counter >= 2:
  ans += counter*(counter - 1)//2
print(ans)
### BUGGY CODE ###

N, A, B = map(int, input().split())
round_count = 0

med = N / 2 + 0.5
maxAB = 10 ** 18

for i in range(maxAB):
    if abs(A - B) % 2 == 0:
        if A > B:
            A = A - 1
            B = B + 1
        else:
            A = A + 1
            B = B - 1
    else:
        medAB = (A + B) / 2
        if medAB > med:
            A = A + 1
            B = B + 1
        else:
            A = A - 1
            B = B - 1

    if A < 1:
        A = 1
    elif A > N:
        A = N
    elif B < 1:
        B = 1
    elif B > N:
        B = N

    round_count = round_count + 1

    if A == B:
        break

print(round_count)

### FIXED CODE ###

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

med = N / 2 + 0.5
Sub = B - A

if (Sub) % 2 == 0:
    round_count = Sub // 2
else:
    round_count = min(A - 1, N - B) + 1 + (Sub - 1) // 2
            
print(round_count)
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

S = str(input())
n = len(S)
if n==1:
  if S=='5' or S=='?':
    print(1)
  else:
    print(0)
  exit()

dp=[[0 for j in range(13)] for i in range(n)]
for i in range(n):
  if i==0:
    if S[i]!='?':
      dp[i][int(S[i])*10**(n-1) %13] += 1
    else:
      for j in range(10):
        dp[i][j*10**(n-1) %13] += 1
  else:
    if S[i]!='?':
      for k in range(13):
        dp[i][(k+int(S[i])*10**(n-i-1))%13] += dp[i-1][k]
    else:
      for j in range(10):
        for k in range(13):
          dp[i][(k+j*10**(n-i-1))%13] += dp[i-1][k]
    for k in range(13):
      dp[i][k] %= mod
print(dp[n-1][5])

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

S = str(input())
n = len(S)
if n==1:
  if S=='5' or S=='?':
    print(1)
  else:
    print(0)
  exit()

dp=[[0]*13 for i in range(n)]
for i in range(n):
  if i==0:
    if S[i]!='?':
      dp[i][int(S[i])] += 1
    else:
      for j in range(10):
        dp[i][j] += 1
  else:
    if S[i]!='?':
      for k in range(13):
        dp[i][(k*10+int(S[i]))%13] += dp[i-1][k]
    else:
      for j in range(10):
        for k in range(13):
          dp[i][(k*10+j)%13] += dp[i-1][k]
    for k in range(13):
      dp[i][k] %= mod
print(dp[n-1][5])
### BUGGY CODE ###

N=int(input())

c=list(input())


#c[1]=c[2]
sta=1
ans=0
for i in range(N):
    if(c[i]=='W'):
        for j in range(sta,N):
            if(-j+N<=i):
                break
            if(c[-j]=='R'):
                temp=c[-j]
                c[-j]=c[i]
                c[i]=temp
                sta=j
                ans=ans+1
                break


print(ans)


### FIXED CODE ###

N=int(input())

c=list(input())


#c[1]=c[2]
sta=1
ans=0
for i in range(N):
    if(-sta+N<i):
        break
    if(c[i]=='W'):
        for j in range(sta,N):
            if(-j+N<=i):
                print(ans)
                exit()
                break
            if(c[-j]=='R'):
                temp=c[-j]
                c[-j]=c[i]
                c[i]=temp
                sta=j
                ans=ans+1
                break


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

N = int(input())
A = tuple(map(int,input().split()))
S = ''

for i in range(N):
    n = A.index(i+1)
    S += str(n+1) + ' '

print(S)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
O = [0] * N

for i , a  in enumerate(A): #リストAのインデックスiと値a
    O[a-1] = i+1

print(*O)
### BUGGY CODE ###

import heapq
import copy

def Dijk(s, t):
    Cost = [-1 for i in range(N)]
    Cost[s] = 0
    Q = copy.deepcopy(Edge[s])
    for node in Q:
        Cost[node[1]] = node[0]
    V = [False for i in range(N)]
    V[s] = True
    while Q:
        Next = heapq.heappop(Q)
        V[Next[1]] = True
        for node in Edge[Next[1]]:
            if V[node[1]] == False:
                if Cost[node[1]] == -1:
                    Cost[node[1]] = Next[0] + node[0]
                else:
                    Cost[node[1]] = min(Next[0] +node[0], Cost[node[1]])
                heapq.heappush(Q, [Cost[node[1]], node[1]])
    return Cost[t]


N, M = map(int, input().split())
Edge = [[] for i in range(N)]
Search = []
for i in range(M):
    a, b, c = map(int,input().split())
    a, b = a-1, b-1
    Edge[a].append([c, b])
    Edge[b].append([c, a])
    Search.append((a, b, c))

Ans = 0
for s in Search:
    for i in range(N):
        if Dijk(i, s[0]) + s[2] == Dijk(i, s[1]):
            break
    else:
        Ans += 1

print(Ans)

### FIXED CODE ###

import heapq

def Dijk(s): #始点Sのダイクストラ, すべての行先への最短距離のリストを返す
    Cost = [float("inf") for i in range(N)]
    Cost[s] = 0
    Q = [[0, s]]
    V = [False for i in range(N)]
    while Q:
        Next = heapq.heappop(Q)
        V[Next[1]] = True
        for node in Edge[Next[1]]:
            if V[node[1]] == False:
                if Next[0] + node[0] < Cost[node[1]]:
                    Cost[node[1]] = Next[0] +node[0]
                    heapq.heappush(Q, [Cost[node[1]], node[1]])
    return Cost


N, M = map(int, input().split())
Edge = [[] for i in range(N)]
Search = []
for i in range(M):
    a, b, c = map(int,input().split())
    a, b = a-1, b-1
    Edge[a].append([c, b])
    Edge[b].append([c, a])
    Search.append((a, b, c))

Ans = 0
Length = []
for i in range(N):
    Length.append(Dijk(i))

for s in Search:
    for i in range(N):
        if Length[i][s[0]] + s[2] == Length[i][s[1]]:
            break
    else:
        Ans += 1

print(Ans)
### BUGGY CODE ###

n,k = map(int, input().split())
l = list(map(int,input().split()))
dp = [0]*n
dp[1] = abs(l[1] - l[0])

for i in range(2,n):
    c = float("inf")
    #1個前から飛んでく、2個前から、、、k個前から飛んでくる最小のコストを求める
    for j in range(min(k,i)):
        c = min(dp[i-(j+1)]+abs(l[i]-l[i-(j+1)]),c)
    dp[i] = c
print(dp[n-1])

### FIXED CODE ###

n,k = map(int, input().split())
l = list(map(int,input().split()))
dp = [0]*n
dp[1] = abs(l[1] - l[0])

for i in range(2,n):
    c = float("inf")
    #1個前から飛んでく、2個前から、、、k個前から飛んでくる最小のコストを求める
    for j in range(min(k,i)):
        c = min(dp[i-(j+1)]+abs(l[i]-l[i-(j+1)]),c)
    dp[i] = c
print(dp[n-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
print(*[A.index(n+1)+1 for n in range(N)]) # TLE?

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
print(*[i+1 for i in np.argsort(A)])
### BUGGY CODE ###

#import sys
#input = sys.stdin.readline
Q = 10**9+7
def getInv(N):#Qはmod
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv

def getFactorialInv(N):
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    ret = [1]*(N+1)
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
        ret[i] = ret[i-1]*inv[i]
    return ret

def getFactorial(N):
    ret = [1]*(N+1)
    for i in range(2,N+1):
        ret[i] = ret[i-1]*i%Q
    return ret

def main():

    N, K = map( int, input().split())
    if K == 1:
        print(0)
        return
    A = list( map( int, input().split()))
    A.sort()
    ans = 0
#    cnt = 1
    fact = getFactorial(N)
    invfact = getFactorialInv(N)
    for i in range(K-1,N):
        # if i < N-1:
        #     if A[i+1] == A[i]:
        #         cnt += 1
        #         continue
        ans += fact[i]*invfact[K-1]%Q*invfact[i-(K-1)]%Q*A[i]%Q
#        print(A[i], fact[i]*invfact[K-1]%Q*invfact[i-(K-1)]%Q*cnt%Q)
        ans %= Q


    A = A[::-1]
    for i in range(K-1,N):
        # if i < N-1:
        #     if A[i+1] == A[i]:
        #         cnt += 1
        #         continue
        ans -= fact[i]*invfact[K-1]%Q*invfact[i-(K-1)]%Q*A[i]%Q
#        print(A[i], fact[i]*invfact[K-1]%Q*invfact[i-(K-1)]%Q*cnt%Q)
        ans %= Q
    print(ans)
    
if __name__ == '__main__':
    main()


### FIXED CODE ###

#import sys
#input = sys.stdin.readline
Q = 10**9+7
# def getInv(N):#Qはmod
#     inv = [0] * (N + 1)
#     inv[0] = 1
#     inv[1] = 1
#     for i in range(2, N + 1):
#         inv[i] = (-(Q // i) * inv[Q%i]) % Q
#     return inv

def main():

    N, K = map( int, input().split())
    if K == 1:
        print(0)
        return
    A = list( map( int, input().split()))
    A.sort()
    ans = 0

    cnt = 1
    for i in range(K-1,N):
        if i >= K:
            cnt *= i*pow(i-(K-1), Q-2, Q)%Q
            cnt %= Q
        ans += cnt*A[i]

        ans -= cnt*A[N-1-i]
        ans %= Q
    print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*n
for i in range(1,n):
  dp[i]=dp[i-1]+abs(h[i-1]-h[i])
  for j in range(1,k+1):
    if i-j<0:
      break
    dp[i]=min(dp[i],dp[i-j]+abs(h[i-j]-h[i]))
    #print("i",i,"j",j,dp)
print(dp[-1])
### BUGGY CODE ###

import heapq

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
r = [a-1 for a in r]
paper = set()
T = [[] for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    T[a].append((c,b))
    T[b].append((c,a))

memo = {}
def distance(a,b):
    #print('distance(',a,',',b,') =?')
    if a > b:
        a,b = b,a
    if (a,b) in memo.keys():
        return memo[(a,b)]
    q = []
    heapq.heappush(q, (0,a))
    try:
        while True:
            c, t = heapq.heappop(q)
            if t == b:
                memo[(a,b)] = c
                #print('distance(',a,',',b,') =',c)
                return c
            for i in T[t]:
                heapq.heappush(q, (c+i[0],i[1]))
    except IndexError:
        pass

inf = 1 << 60
arrived = [False] * R
ans = inf

def calc(src, rest, total):
    global ans
    if total >= ans:
        return
    if rest == 0:
        ans = min(ans,total)
        return

    for i in range(R):
        if not arrived[i]:
            arrived[i] = True
            calc(r[i], rest-1, total + distance(src,r[i]))
            arrived[i] = False

for i in range(R):
    arrived[i] = True
    calc(r[i], R-1, 0)
    arrived[i] = False

print(ans)


### FIXED CODE ###

import heapq

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
r = [a-1 for a in r]
paper = set()
T = [[] for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    T[a].append((c,b))
    T[b].append((c,a))

inf = 1 << 60
memo = {}
def distance(a,b):
    #print('distance(',a,',',b,') =?')
    if (a,b) in memo.keys():
        #print('distance(',a,',',b,') =',memo[(a,b)])
        return memo[(a,b)]
    d = [inf] * N
    d[a] = 0
    q = []
    heapq.heappush(q, (0,a))
    try:
        while True:
            c, t = heapq.heappop(q)
            if t == b:
                memo[(a,b)] = c
                memo[(b,a)] = c
                #print('distance(',a,',',b,') =',c)
                return c
            for i in T[t]:
                if d[i[1]] > c + i[0]:
                    d[i[1]] = c + i[0]
                    heapq.heappush(q, (c + i[0], i[1]))

    except IndexError:
        pass

arrived = [False] * R
ans = inf

def calc(src, rest, total):
    global ans
    if total >= ans:
        return
    if rest == 0:
        ans = min(ans,total)
        return

    for i in range(R):
        if not arrived[i]:
            arrived[i] = True
            calc(r[i], rest-1, total + distance(src,r[i]))
            arrived[i] = False

for i in range(R):
    arrived[i] = True
    calc(r[i], R-1, 0)
    arrived[i] = False

print(ans)