Harryxun/stf_run huggingface dataset:
n, k = map(int, input().split())
s = input().rstrip()

#s = "0001111011110"
#n, k = len(s), 1

s="1"+s

k_pt = 0
cur_tail = 0
for cur in range(1, n):

  cur_tail+=1

  if  s[cur-1] == '1' and s[cur] == '0':
    k_pt+=1

  if  s[cur_tail-1] == '0' and s[cur_tail] == '1':
    k_pt-=1

  if k_pt <= k:
      cur_tail-=1

print(cur-cur_tail)


### FIXED CODE ###

n, k = map(int, input().split())
s = input().rstrip()


#n, k = 5, 3
#s = "00010"

m = 0
cur_s = cur_e = 0

while True:
  while cur_e < n and s[cur_e] == '1':
    cur_e+=1
  
  if k <= 0 or cur_e >= n:
    wm = cur_e - cur_s
    if wm > m:
      m = wm
      
    if cur_e >= n:
      break
 
    while cur_s < n and s[cur_s] == '1':
      cur_s+=1
    while cur_s < n and s[cur_s] == '0':
      cur_s+=1
    k+=1

  if k > 0:
    while cur_e < n and s[cur_e] == '0':
      cur_e+=1
    k-=1
    
print(m)
def op_print(data,a,b):
    print(data[a:b])
def op_reverse(data,a,b):
    return data[:a] + data[::-1][-b:-a] + data[:b]
def op_replace(data,a,b,q):
    return data.replace(data[a:b],q) 

data = input()
q = int(input())
for _ in range(q):
    op = list(map(str,input().split()));op[2]+=1
    if(op[0] == "print"):
        op_print(data,int(op[1]),int(op[2]))
    elif(op[0] == "reverse"):
        data = op_reverse(data,int(op[1]),int(op[2]))
    elif(op[0] == "replace"):
        data = op_replace(data,int(op[1]),int(op[2]),op[3])


### FIXED CODE ###

s=input()
for _ in range(int(input())):
    o=input().split()
    a,b=map(int,o[1:3]);b+=1
    c=o[0][2]
    if c=='p':s=s[:a]+o[3]+s[b:]
    elif c=='i':print(s[a:b])
    elif c=='v':s=s[:a]+s[a:b][::-1]+s[b:]
def main():
    n, m = map(int, input().split())
    p = [0] + list(map(int, input().split()))
    cnt = 0
    global parent
    parent = list(range(n+1))
    for _ in range(m):
        x, y = map(int, input().split())
        unite(x, y)
    for i in range(1, n+1):
        if root(i) == root(p[i]):
        cnt += 1
    print(cnt)

def root(x):
    if parent[x] == x:
        return x
    parent[x] = root(parent[x])
    return parent[x]

def unite(x, y):
    root_x = root(x)
    if root_x != root(y):
        parent[root_x] = y

if __name__ == "__main__":
    main()

### FIXED CODE ###

N, M = map(int, input().split())
# p = [int(i) for i in input().split()]
p = map(int,input().split())
# graph = [[]]*(N+1)
graph = [[] for _ in range(N+1)]
group = [0]*(N+1)
ans = 0
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p, 1):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i
        space.extend(graph[point])
    ans += (group[num] == group[i])
print(ans)
s = input()
str3=inputs[2]
str4=inputs[3]
str5=inputs[4]
str6=inputs[5]

iscoffee=False
if str3==str4 and str5==str6:
    iscoffee=True
print(str(iscoffee))

### FIXED CODE ###

inputs=input()

print("Yes" if inputs[2]==inputs[3] and inputs[4]==inputs[5] else "No")
from collections import Counter

N=int(input())
A=list(map(int,input().split()))
c=Counter(A)
commons=c.most_common()

ans=0

dic={}
for common in commons:
    dic[common[0]]=common[1]
    ans+=common[0]*common[1]
# print(dic)
# print(ans)

Q=int(input())
for i in range(Q):
    b,c=map(int,input().split())
    ans+=(c-b)*dic[b]
    dic[c]+=dic[b]
    dic[b]=0
    # print(dic)
    print(ans)


### FIXED CODE ###

from collections import Counter

N=int(input())
A=list(map(int,input().split()))
c=Counter(A)
commons=c.most_common()

ans=0

dic={}
for common in commons:
    dic[common[0]]=common[1]
    ans+=common[0]*common[1]
# print(dic)
# print(ans)

Q=int(input())
for i in range(Q):
    b,c=map(int,input().split())
    if b not in dic:
        print(ans)
        continue
    else:
        pass
    if c not in dic:
        ans+=(c-b)*dic[b]
        print(ans)
        dic[c]=dic[b]
        dic[b]=0
        continue
    else:
        pass
    ans+=(c-b)*dic[b]
    dic[c]+=dic[b]
    dic[b]=0
    print(ans)
n = int(input())
for i in range(n):
    x1, y1, x2, y2, x3, y3, x4, y4 = map(float, input().split(" "))
    if abs((y1 - y2) / (x1 - x2) - (y4 - y3)/ (x4 - x3)) < 1e-10: print("YES")
    else: print("NO")


### FIXED CODE ###

n = int(input())
for i in range(n):
    x1, y1, x2, y2, x3, y3, x4, y4 = map(float, input().split())
    if abs((x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3)) < 1e-10: print("YES")
    else: print("NO")
import sys
input = sys.stdin.readline
N, M = map(int, input().split(" "))
A = [int(i) for i in input().split()]
count = 0
for i in range(N):
    for k in range(i,N):
        S = sum(A[i:k+1])
        if S % M ==0:
            count = count +1
 
print(count)


### FIXED CODE ###

n=int(input())
s=''
while n != 0:
    s = str( n % 2 ) + s
    n = - ( n // 2 )
print(s*(s != '') or 0)
N=int(input())
xyh=[list(map(int, input().split())) for i in range(N)]

for i in range(101):
  for j in range(101):
    check=True
    h=abs(xyh[0][0]-i)+abs(xyh[0][1]-j)+xyh[0][2]
    
    for k in range(1, N):
      temph=abs(xyh[k][0]-i)+abs(xyh[k][1]-j)+xyh[k][2]
      if h!=temph:
        check=False
        
    if check:
      if 0<=h and h<=pow(10, 9):
      print(' '.join([str(i), str(j), str(h)]))

### FIXED CODE ###

N=int(input())
xyh=[list(map(int, input().split())) for i in range(N)]
 
for i in range(101):
  for j in range(101):
    check=True
    k=0
    while xyh[k][2]==0:
      k+=1
      
    h=abs(xyh[k][0]-i)+abs(xyh[k][1]-j)+xyh[k][2]
    
    for k in range(N):
      temph=abs(xyh[k][0]-i)+abs(xyh[k][1]-j)+xyh[k][2]
      if xyh[k][2]==0:
        if temph<h:
          check=False
      else:
        if h!=temph:
          check=False
        
    if check==True and 0<h:
        print(' '.join([str(i), str(j), str(h)]))
        exit()
        
sonnnakannsuuhateigisiteinai()
n = input()
num = input(n)
ans = 0
for digit in range(1,10):
    if int(num/digit) == 111:
        ans = num
        break
    elif int(num/digit) < 111:
        ans = digit*100+digit*10+digit
        break
print(ans)

### FIXED CODE ###

n = input()
num = int(n)
ans = 0
for digit in range(1,10):
    if num/digit == float(111):
        ans = num
        break
    elif num/digit < float(111):
        ans = digit*100+digit*10+digit
        break
print(ans)
# coding: utf-8

num_array = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print("{}".format(num_array[k-1]))


### FIXED CODE ###

# coding: utf-8

num_array = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

k = int(input())

print("{}".format(num_array[k-1]))
import re
N,M=map(int, input().split())

A=[]
B=[]

for n in range(N):
    A.append(input())

for m in range(M):
    B.append(input())
        
# check
for m in range(M):
    for n in range(N):
        # Bのm行目と一致
        # Bのm+1行目と一致するかチェック
        span =[m.span() for m in re.finditer(B[m], A[n])]
        #print(span)
        if span==[]:
            continue
        allgood=False
        # フィルタが1行ならYesを返す
        if M==1:
            print("Yes")
            exit()
        for i in range(1, M):
            #print((B[i],A[i+n][span[0][0]:span[0][1]]))
            if (B[i]==A[i+n][span[0][0]:span[0][1]]):
                allgood=True
                continue
            else:
                allgood=False
                break
        if allgood==True:
            print("Yes")
            exit()

print("No")



### FIXED CODE ###

import re
N,M=map(int, input().split())

A=[]
B=[]

for n in range(N):
    A.append(input())

for m in range(M):
    B.append(input())
        
if N<M:
    print("No")
    exit()
# check
for n in range(N):
      # Bのm行目と一致
      # Bのm+1行目と一致するかチェック
      span =[m.span() for m in re.finditer(B[0], A[n])]
      #print(span)
      if span==[]:
          continue
      allgood=False
      for sp in span:
        for i in range(min(M,N)):
            if n+i>=N:
                allgood=False
                break
            #print(n)
            #print((B[i],A[n+i][span[0][0]:span[0][1]]))
            if (B[i]==A[n+i][sp[0]:sp[1]]):
                allgood=True
                continue
            else:
                allgood=False
                break
        if allgood==True:
            print("Yes")
            exit()

print("No")
# https://atcoder.jp/contests/abc088/tasks/abc088_b?lang=ja

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

a.sort(reverse=True)

alice_score = 0
bob_score = 0

for i in range(len(a)):
    if i % 2 == 0:
        alice_score += a[i]
    else:
        bob_score += a[i]

print(alice_score - bob_score)
# https://atcoder.jp/contests/abc088/tasks/abc088_b?lang=ja

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

a.sort(reverse=True)

alice_score = 0
bob_score = 0

for i in range(len(a)):
    if i % 2 == 0:
        alice_score += a[i]
    else:
        bob_score += a[i]

print(alice_score - bob_score)


### FIXED CODE ###

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

a.sort(reverse=True)

alice_score = 0
bob_score = 0

for i in range(len(a)):
    if i % 2 == 0:
        alice_score += a[i]
    else:
        bob_score += a[i]

print(alice_score - bob_score)
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 0
time = 0
n = 0
m = 0
for i in range(N+M):
    if n < N and m < M:
        if A[n] <= B[m]:
            time += A[n]
            n += 1
        else:
            time += B[m]
            m += 1
    else:
        if n >= N and m >= M:
            break
        elif n == N -1:
            time += B[m]
            m += 1
        elif m == M -1:
            time += A[n]
            n += 1
    if time < K:
        ans += 1
    else:
        break
print(ans)

### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A_sum = [0]
for i in range(N):
    A_sum.append(A[i] + A_sum[i])
B_sum = [0]
for i in range(M):
    B_sum.append(B[i] + B_sum[i])    
import bisect
ans = 0
for i in range(N+1):
    a = A_sum[i]
    if K-a >=0:
        b_idx = bisect.bisect(B_sum, K-a) - 1
        if b_idx  < 0:
            b_idx = 0
        ans = max(ans, i+b_idx)
print(ans)
a=map(int, raw_input().split())
a=sorted(a)
for i in range 2:
    print L[i] + " "

### FIXED CODE ###

a = map(int, raw_input().split())
a.sort()
for i in range(len(a)):
    print a[i],
l=[]
N,W=list(map(int,(input().split())))
for i in range(N):
	item=list(map(int,input().split))
	l.append([item[1],item[0]])
	N-=1
# n=4
# l=[[2,3],[1,2],[3,4],[2,2]] #w,v
# W=5

def solve(i,w):
	if i==n or w<0:
		return(0)
	elif w-l[i][0]<0:
		return(0)
	else:
		return(max(solve(i+1,w),l[i][1]+solve(i+1,w-l[i][0])))

print(solve(0,W))

### FIXED CODE ###

value=[0]
weight=[0]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	value.append(item[0])
	weight.append(item[1])

dp=[[0 for j in range(W+1)] for i in range(n+1)]
for i in range(n+1):
	for j in range(W+1):
		if i==0:
			res=0
		elif j-weight[i]<0:
			res=dp[i-1][j]
		else:
			res=max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j])
		dp[i][j]=res
print(dp[n][W])
w, h, n = [int(i) for i in input().split()]
table = [[0 for _ in range(w)] for _ in range(h)]

for _ in range(n):
    x, y, a = [int(i) for i in input().split()]
    if a == 1:
        table[0][0] += 1
        if x < w:
            table[0][x] -= 1
    elif a == 2:
        table[0][x] += 1
    elif a == 3:
        table[0][0] += 1
        if y < h:
            table[y][0] -= 1
    elif a == 4:
        table[y][0] += 1

for i in range(len(table)):
    for j in range(1, len(table[i])):
        table[i][j] += table[i][j-1]
for i in range(1, len(table)):
    for j in range(len(table[i])):
        table[i][j] += table[i-1][j]
count = 0
for i in range(len(table)):
    for j in range(len(table[i])):
        if table[i][j] == 0:
            count += 1
print(count)


### FIXED CODE ###

w, h, n = [int(i) for i in input().split()]
table = [[0 for _ in range(w)] for _ in range(h)]

for _ in range(n):
    x, y, a = [int(i) for i in input().split()]
    if a == 1:
        table[0][0] += 1
        if x < w:
            table[0][x] -= 1
    elif a == 2:
        if x < w:
            table[0][x] += 1
    elif a == 3:
        table[0][0] += 1
        if y < h:
            table[y][0] -= 1
    elif a == 4:
        if y < h:
            table[y][0] += 1

for i in range(len(table)):
    for j in range(1, len(table[i])):
        table[i][j] += table[i][j-1]
for i in range(1, len(table)):
    for j in range(len(table[i])):
        table[i][j] += table[i-1][j]
count = 0
for i in range(len(table)):
    for j in range(len(table[i])):
        if table[i][j] == 0:
            count += 1
print(count)
print(x,y)
point=0
if x == 1: 
    point = point + 300000
elif x == 2:
    point = point + 200000
elif x == 3:
    point = point + 100000
if y == 1: 
    point = point + 300000
    if x == 1:
        point = point + 400000
elif y == 2:
    point = point + 200000
elif y == 3:
    point = point + 100000
print(point)
    


### FIXED CODE ###

(x,y) = map(int,input().split())
point=0
if x == 1: 
    point = point + 300000
elif x == 2:
    point = point + 200000
elif x == 3:
    point = point + 100000
if y == 1: 
    point = point + 300000
    if x == 1:
        point = point + 400000
elif y == 2:
    point = point + 200000
elif y == 3:
    point = point + 100000
print(point)
n = int(input())
dic = {}
for i in range(1,n+1):
    s,p = map(str,input().split())
    dic[i]=s+str(1/int(p))
for s in sorted(dic.items(),key=lambda x:x[1]):
    print(s[0])

### FIXED CODE ###

n = int(input())

map_list = [[0,'abc',0] for i in range(n)]

for i in range(n):
    input_line = input().split()
    map_list[i]=[i,input_line[0],int(input_line[1])]

ans_li = sorted(map_list,key=lambda x:(x[1],-x[2]))
for ans in ans_li:
    print(ans[0]+1)
n = input()
print("Yes" if n==n[::-] else "No")

### FIXED CODE ###

N = input()
print("Yes" if N[0]==N[2] or N[0]==N[1]==N[2] else "No")
n = int(input())
p = [str(input()) for _ in range(n)]
import collections
c = collections.Counter(p)
m = max(c.values())
keys = [k for k, v in d.items() if v == m]
sorted(keys)
for i in keys:
    print(i)

### FIXED CODE ###

n = int(input())
p = [str(input()) for _ in range(n)]
import collections
c = collections.Counter(p)
m = max(c.values())
keys = [k for k, v in c.items() if v == m]
keys.sort()
for i in keys:
    print(i)
import numpy as np

info = np.array(input().split(" "), dtype="int64")
o = info[1] + info[2]
if o == 0:
    print(0)
else:
    q, mod = divmod(info[0], o)
    if mod > info[1]:
        print((q+1)* info[1])
    else:
        print(q*info[1] + mod)

### FIXED CODE ###

inf = input().split()
info = list(map(int, inf))
o = info[1] + info[2]
if o == 0:
    print(0)
else:
    q, mod = divmod(info[0], o)
    if mod > info[1]:
        print((q+1)* info[1])
    else:
        print(q*info[1] + mod)
import sys
h, w, n = [int(i) for i in sys.readline().split()]
m = 1000000007
fact = [1, 1]
for i in range(2, 200002):
    fact.append(fact[-1] * i)
inv = [pow(i, m - 2, m) for i in fact]
f = lambda i: fact[i[0] + i[1]] * inv[i[0]] * inv[i[1]] % m
dp = [0] * (n + 1)
p = [[int(i) - 1 for i in sys.readline().split()] for j in range(n)]
p = sorted(p + [[h - 1, w - 1]])
for i in range(n + 1):
    h1, w1 = p[i]
    tot = f([h1, w1])
    for j in range(i):
        if p[j][1] > w1:
            continue
        tot = (tot - dp[j] * f([h1 - p[j][0], w1 - p[j][1]]) % m) % m
    dp[i] = tot
print(dp[-1])

### FIXED CODE ###

import sys
h, w, n = [int(i) for i in sys.stdin.readline().split()]
m = 1000000007
fact = [1, 1]
for i in range(2, 200002):
    fact.append(fact[-1] * i % m)
inv = [pow(i, m - 2, m) for i in fact]
f = lambda i: fact[i[0] + i[1]] * inv[i[0]] * inv[i[1]] % m
dp = [0] * (n + 1)
p = [[int(i) - 1 for i in sys.stdin.readline().split()] for j in range(n)]
p = sorted(p + [[h - 1, w - 1]])
for i in range(n + 1):
    h1, w1 = p[i]
    tot = f([h1, w1])
    for j in range(i):
        if p[j][1] > w1:
            continue
        tot = (tot - dp[j] * f([h1 - p[j][0], w1 - p[j][1]]) % m) % m
    dp[i] = tot
print(dp[-1])
def test(n):
    x = n * 8 // 100
    y = n * 10 // 100
    return (x==a) & (y==b)

if __name__ == "__main__":
    answer = -1
    a, b = map(int, input().split())
    for n in range(int(2e+4)):
        if test(n):
            ans = n
            break
    print(ans)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
A,B = map(int,read().split())
 
def test(n):
    x = n * 8 // 100
    y = n * 10 // 100
    return (x == A) and (y == B)
 
answer = -1
for n in range(20000):
    if test(n):
        answer = n
        break
print(answer)
w, h , x ,y ,r = map(int,input().split())

xLongLeft = x-r
xLongRight = x + r

yLongTop = y + r
yLongBot = y - r

if((xLongLeft >= 0 and yLongBot >= 0) and (xLongRight <= w and yLongTop <= h):
   print('Yes')
else:
   print('No')



### FIXED CODE ###

w, h , x ,y ,r = map(int,input().split())

xLongLeft = x-r
xLongRight = x + r

yLongTop = y + r
yLongBot = y - r

if((xLongLeft >= 0 and yLongBot >= 0) and (xLongRight <= w and yLongTop <= h)):
   print('Yes')
else:
   print('No')
A,B,K=map(int,input().split())
nums = list(range(A,B+1))
result = set()
L = min(B-A+1,K)
for i in range(L):
    result.add(nums[i])
nums.sort(reverse=True)
for j in range(L):
    result.add(nums[j])
for x in result:
    print(x)

### FIXED CODE ###

A,B,K=map(int,input().split())
result = []
L = min(B-A+1,K)
for i in range(A,A+L):
    if i not in result:
        result.append(i)
for j in range(B,B-L,-1):
    if j not in result:
        result.append(j)
result.sort()
for x in result:
    print(x)
import sys
import math
readline = sys.stdin.readline

def main():
  p = 1000000007
  N = int(readline().strip())
  A = {}
  B = {}
  ans = 0
  for i in range(N):
    s = ''
    ai, bi = map(int, readline().split())
    if ai == 0 and bi == 0:
      ans += 1
      continue
    gi = math.gcd(ai, bi)
    ai = int(ai / gi)
    bi = int(bi / gi)
    if ai != 0 and bi != 0:
      if ai < 0 and bi < 0:
        ai = -ai
        bi = -bi
      elif ai < 0:
        ai = -ai
        s = '-'
      elif bi < 0:
        bi = -bi
        s = '-'
    elif ai == 0 and bi != 0:
      ai = 0
      bi = 1
    elif bi == 0 and ai != 0:
      ai = 1
      bi = 0
      s = '-'
    xi = s + str(ai) + '/' + str(bi)
    if s == '':
      s = '-'
    else:
      s = ''
    yi = s + str(bi) + '/' + str(ai)
    if xi in A:
      A[xi] += 1
    else:
      A[xi] = 1
      B[xi] = yi
    C = {}
    for i in B:
      if i in C:
        continue
      elif B[i] not in B:
        C[i] = [A[i], 0]
      elif B[i] in C:
        continue
      else:
        C[i] = [A[i], A[B[i]]]
  r = 1
  for i in C:
    r = r * (pow(2, C[i][0], p) + pow(2, C[i][1], p) -1) % p
  r -= 1
  ans += r
  print(ans)

if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys
import math
readline = sys.stdin.readline

def main():
  p = 1000000007
  N = int(readline().strip())
  A = {}
  ans = 0
  for i in range(N):
    s = ''
    ai, bi = map(int, readline().split())
    if ai == 0 and bi == 0:
      ans += 1
      ans %= p
      continue
    gi = math.gcd(ai, bi)
    ai //= gi
    bi //= gi
    if ai != 0 and bi != 0:
      if ai < 0 and bi < 0:
        ai *= -1
        bi *= -1
      elif ai < 0:
        ai *= -1
        s = '-'
      elif bi < 0:
        bi *= -1
        s = '-'
    elif ai == 0 and bi != 0:
      ai = 0
      bi = 1
    elif bi == 0 and ai != 0:
      ai = 1
      bi = 0
      s = '-'
    xi = s + str(ai) + '/' + str(bi)
    if s == '':
      s = '-'
    else:
      s = ''
    yi = s + str(bi) + '/' + str(ai)
    if xi in A:
      A[xi][0] += 1
      A[xi][0] %= p
    elif yi in A:
      A[yi][1] += 1
      A[yi][1] %= p
    else:
      A[xi] = [1, 0]
  r = 1
  for i in A:
    r *= (pow(2, A[i][0], p) + pow(2, A[i][1], p) -1)
    r %= p
  ans += r - 1
  ans %= p
  print(ans)

if __name__ == '__main__':
  main()
N, R = int(input( , ))
 
if N < 10:
  N = R + 100 * (10 - N) 
  print(N)
  
else:
  N = R
  print(N)

### FIXED CODE ###

N, R = (int(x) for x in input().split())
 
if N < 10:
  N = R + 100 * (10 - N) 
  print(N)
  
else:
  N = R
  print(N)
from scipy.misc import comb

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

Min = 0
Max = 0

a_sort = sorted(a)
for i, num in enumerate(a_sort):
    if i >= k-1:
        Min += comb(i, k-1) * num
    if n-i >= k:
        Max += comb(n-i-1, k-1) * num

print(int((Min - Max) % (10e08+7)))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
 
class Combination():
    # コンストラクタ
    def __init__(self, N:int, P:int):
        self.N = N
        self.P = P
 
        # fact[i] = (i! mod P)
        self.fact = [1, 1]   
        # factinv[i] = ((i!)^(-1) mod P)
        self.factinv = [1, 1]
        # factinv 計算用
        self.inv = [0, 1]    
 
        for i in range(2, N+1):
            self.fact.append((self.fact[-1] * i) % P)
            self.inv.append((-self.inv[P % i] * (P // i)) % P)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % P)
    
    # nCk (mod P)   (ただし、n<=N)
    def getComb(self, n:int, k:int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] * self.factinv[n-k] % self.P
 
def main():
    N,K = map(int,input().split())
    A = sorted([int(i) for i in input().split()])
 
    mod = 10**9+7
 
    COMB = Combination(N,mod)
 
    cmb = [0] * (N-K+1)
    for i in range(N-K+1):
        cmb[i] = COMB.getComb(i+(K-1),K-1)
 
    sum_max = 0
    for i in range(K-1,N):
        sum_max = (sum_max + cmb[i-(K-1)] * A[i]) % mod
 
    sum_min = 0
    for i in range(N-K,-1,-1):
        sum_min = (sum_min + cmb[(N-K)-i] * A[i]) % mod
 
    answer = sum_max - sum_min
    print(answer % mod)
 
if __name__ == "__main__":
    main()
# -*- coding: utf-8 -*-
N = int(input())
A = int(input())
B = int(input())

outValue = 0
for n in range(N+1):
    #inputList = [int(c) for c in str(n)]
    #if A <= sum(inputList) <= B:
    #    outValue += n

print(outValue)


### FIXED CODE ###

# -*- coding: utf-8 -*-
strList = list(map(int, input().split()))

N = strList[0]
A = strList[1]
B = strList[2]

outValue = 0
for n in range(N+1):
    strList = [int(c) for c in str(n)]
    if A <= sum(strList) <= B:
        outValue += n

print(outValue)
import numpy as np


#def area##################################

def zero(n):
	c=list()
	for i in range(n):
		c+=[0]
	return c

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

f_input=map( int,raw_input().split(" ")  )


vec=f_input[0]
col=f_input[1]


#zero teigi
null=list()
for i in range(vec):
	null.append(zero(col))
#print null
cvarea=np.matrix(null)


k=list()
for i in range(col):
	k+=[[0]]
k=np.matrix(k)
varea=k

#print "cvarea="
#print cvarea
#print "varea="
#print varea





#print "kokkara"

for i in range(vec):
	N=map(int,raw_input().split(" "))
#	print N
	M=np.matrix(N)
#	print M
	cvarea[i]+=N
#print "cvarea="
#print cvarea

for i in range(col):
	N=int(raw_input())
	varea[i]+=N
#print "varea="
#print varea

sol=cvarea*varea
for i in range(col):
	print int(sol[i])

### FIXED CODE ###

A=map(int,raw_input().split(" "))
vec=A[0]
col=A[1]

def zero(n):
	zerolist=list()
	for i in range(n):
		zerolist+=[0]
	return(zerolist)
A=list()
for i in range(vec):
	A+=[zero(col)]



for i in range(vec):
	k=map(int,raw_input().split(" "))
	for j in range(col):
		A[i][j]=k[j]

#ok

v=zero(col)

for i in range(col):
	v[i]=int(raw_input())

k=0
for i in range(vec):
	for j in range(col):
		k+=A[i][j]*v[j]
	print k
	k=0