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

#coding:utf-8



def main():
    
    def dbg(*something):
        if DEBUG:
            print(*something)


    #正の宝石を戻すことはない
    #負の宝石を戻すのは後半
    from sys import stdin
    from math import ceil,floor
    DEBUG = False
    N,K = list(map(int,stdin.readline().split()))
    V = list(map(int,stdin.readline().split()))


    #残りk回のとき深さk以下の場所に正の宝石がない→終了
    #i回の操作で取れる石>それまでにとるi-1個の石の和
    #深さiにある石vの価値：v - (それまでにとるi-1個の石の和　except (k-i)個の負の石)
    '''
    '''




    def tansaku(left,right,rK,N,score):
        dbg(V[left:right+1],rK,N,score)

        N.sort()
        max_v = score + sum(N[rK:])


        # n = []
        for i in range(left,min(rK+left, ceil((right - left +1)/2)+left)):
            
            if V[i] <= 0:
                #n.append(V[i])
                continue

            #next_V = V[i+1:left+lenV]
            next_rK = rK - 1 - (i - left)
            next_tmp_v = tansaku(i+1,right,  next_rK, N+V[left:i], score+V[i])
            max_v = max(next_tmp_v , max_v)


            break

        # n = []
        for i in range(right ,max(right - ceil((right-left+1)/2)  ,right-rK)  ,-1 ):
            
            if V[i] <= 0:
                #n.append(V[i])
                continue

            #next_V = V[:i]
            next_rK = rK - 1 - (right - i)
            #next_tmp_v = tansaku(   left,   i- left -1  ,next_rK,N+n,score+V[i])
            next_tmp_v = tansaku(   left,   i-1  ,next_rK,N+V[i+1:right+1],score+V[i])
            max_v = max(next_tmp_v , max_v)
            break


        return max_v

    print(tansaku(0,len(V)-1,K,[],0))





if __name__ == '__main__':
    main()


### FIXED CODE ###

#coding:utf-8



def main():
    
    def dbg(*something):
        if DEBUG:
            print(*something)


    #正の宝石を戻すことはない
    #負の宝石を戻すのは後半
    from sys import stdin
    from math import ceil,floor
    DEBUG = False
    N,K = list(map(int,stdin.readline().split()))
    V = list(map(int,stdin.readline().split()))
    
    max_value = 0
    dbg([i for i in range(3,-1,-1)])
    for getnum in range(1,min(N+1,K+1)):  #取る宝石の総数
        for a in range(getnum + 1):  #左から石を取る回数
            J = [0] * getnum #石
            b = getnum - a #右から石を取る回数
            for i in range(a):
                J[i] = V[i]
            for i in range(b):
                J[a+i] = V[-i-1]
            J.sort()
            #dbg(J,a,b)
            t = min(K-getnum,getnum) #捨てる石
           
            for i in range(t): 
                if J[i] >= 0:
                    t = i
                    break
            #dbg(J,i,t,a,b,J[t:])
            tmp_max = sum(J[t:])

            max_value = max(max_value,tmp_max)
    print(max_value)



if __name__ == '__main__':
    main()
### BUGGY CODE ###

N=int(input())
A=[int(input()) for n in range(N)]
m=max(A)
for i in range(N):
	print(m) if A[i]<m else print(max(A[:i]+A[i+1:]))


### FIXED CODE ###

N=int(input())
A=[int(input()) for n in range(N)]
m=max(A)
n=sorted(A,reverse=True)[1]
for i in range(N):
    if A[i]<m:
        print(m)
    else:
        print(n)
### BUGGY CODE ###

import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

n,a,b,c = get_nums_l()
d = {
    "A": a,
    "B": b,
    "C": c
}
S = []
for _ in range(n):
    S.append(input())

def dfs(i, x, history):

    if d[S[i][1-x]] == 0:
        return False

    d[S[i][x]] += 1
    d[S[i][1-x]] -= 1

    history.append(S[i][x])

    if i == n-1:
        return True

    ok = dfs(i+1, 0, history)
    if ok:
        return ok

    ok = dfs(i+1, 1, history)

    if ok:
        return ok

    # バックトラック
    history.pop()
    d[S[i][x]] -= 1
    d[S[i][1-x]] += 1

    return False

history = deque()
ok = dfs(0, 0, history) or dfs(0, 1, history)

print("Yes" if ok else "No")
if ok:
    for s in history:
        print(s)


### FIXED CODE ###

import random
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,a,b,c = get_nums_l()
d = {
    "A": a,
    "B": b,
    "C": c
}
S = []
for _ in range(n):
    S.append(input())

def dfs(i, x, history):

    if d[S[i][1-x]] == 0:
        return False

    d[S[i][x]] += 1
    d[S[i][1-x]] -= 1

    history.append(S[i][x])

    if i == n-1:
        return True

    nex = random.randint(0, 1)

    ok = dfs(i+1, nex, history)
    if ok:
        return ok

    ok = dfs(i+1, 1-nex, history)

    if ok:
        return ok

    # バックトラック
    history.pop()
    d[S[i][x]] -= 1
    d[S[i][1-x]] += 1

    return False

history = deque()
ok = dfs(0, 0, history) or dfs(0, 1, history)

print("Yes" if ok else "No")
if ok:
    for s in history:
        print(s)
### BUGGY CODE ###

n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
maximum = arr[-1]
tf = [True] * (maximum+1)
cnt = 0
        
for i in range(n):
  ai = arr[i]
  if tf[ai] == True:
    cnt += 1
    for j in range(maximum//ai):
      tf[(j+1)*ai] = False
    if ai in arr[i+1:]:
      cnt -= 1
    

print(cnt)

### FIXED CODE ###

n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
m = arr[-1]
li = [0]*(m+1)
cnt = 0
        
for i in arr:
  for j in range(i, m+1, i):
    li[j] += 1

for i in arr:
  if li[i] == 1:
    cnt += 1

print(cnt)
### BUGGY CODE ###

from bisect import bisect_right as br
import heapq
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort()
A=[a for a,b in AB]
B=[b for a,b in AB]
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  #worksにlatest日以内に報酬を貰える仕事を追加する
  if not A or A[0]>latest:
    pass
  else:
    while A and A[0]<=latest:
    #for _ in range(br(A,latest)):
      A=A[1:]
      #index=br(works,B[0])
      #works=works[:index]+B[0]+works[index:]
      heapq.heappush(works,-B[0])
      B=B[1:]
  if not works:
    continue
  #ans+=works.pop(-1)
  ans-=heapq.heappop(works)

print(ans)


### FIXED CODE ###

import heapq
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort(reverse=True)
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  while AB and AB[-1][0]<=latest:
    a,b=AB.pop()
    heapq.heappush(works,-b)
  if not works:
    continue
  ans-=heapq.heappop(works)

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

n, w = map(int, input().split())
lis = [[0, 0]]
for i in  range(n):
    lis.append(list(map(int, input().split())))

dp = [[0 for i in range(w+1)] for i in range(n+1)]
#print(dp)
#print(lis)

for i in range(1, n+1):
    for j in range(w+1):
        if j - lis[i][0] < 0:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-lis[i][0]] + lis[i][1])
print(dp[n][w])

### FIXED CODE ###

n, w = map(int, input().split())
lis = [[0, 0]]
for i in  range(n):
    lis.append(list(map(int, input().split())))

dp = [[0 for i in range(w+1)] for i in range(n+1)]
#print(dp)
#print(lis)

for i in range(1, n+1):
    for j in range(w+1):
        if j - lis[i][0] < 0:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-lis[i][0]] + lis[i][1])
print(dp[n][w])
### BUGGY CODE ###

S = input()
a = len(S)
L_1 = [0]
for i in range(a):
    L_1.append(int(S[:i+1])%3)
L_2 = [0]
for i in range(a):
    L_2.append(int(S[:i+1])%673)
k = 0
M = []
for j in range(a+1):
  M.append(10**j % 673)
#x文字目からy文字目
for x in range(1,a+1):
    for y in range(x,a+1):
        if L_1[y] == L_1[x-1]:
            if (L_2[x-1]*M[y-x+1] - L_2[y]) % 673 == 0:
                k += 1
print(k)

### FIXED CODE ###

S = input()
a = len(S)
mod = 0
ten = 1
L = [0]*2019 #余りの列
L[0] = 1
for i in range(a-1,-1,-1):
    mod = (int(S[i])*(ten)+mod) %2019
    L[mod] += 1
    ten = (ten*10)%2019
ans = 0
for i in L:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

K, S = map(int, input().split())
ans = 0

for i in range(K + 1):
    s = i
    if s > S:
        break
    for j in range(K + 1):
        s = i + j
        if s > S:
            break
        for k in range(K + 1):
            s = i + j + k
            if S == s:
                ans += 1
                break

print(ans)

### FIXED CODE ###

K, S = map(int, input().split())
ans = 0

for i in range(K + 1):
    s = i
    if s > S:
        break
    for j in range(K + 1):
        s = i + j
        if s > S:
            break
        Z = S - s
        if 0 <= Z <= K:
            ans += 1

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

n = int(input())
for i in range(1,n+1):
    ans = 0
    for x in range(33):
        for y in range(33):
            for z in range(33):
                if (x+y+z)**2 -(x*y+y*z+z*x) == i and x>=1 and y>=1 and z>=1:
                    ans += 1
    print(ans)
                

### FIXED CODE ###

cnt=[0] * 11000
n = int(input())

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            value = (x+y+z)**2 -(x*y+y*z+z*x)
            if value <= n:
                cnt[value] += 1

for i in range(1,n+1):
    print(cnt[i])
### BUGGY CODE ###

n = int(input())
s = str(input())
count = {'R': 0, 'G': 0, 'B': 0}
for c in s:
    count[c] += 1
R, G, B = count.values()
ans = R * G * B

for i in range(n - 1):
    for j in range(i + 1, n):
        k = j + j - i
        if k >= n:
            continue
        if (s[i] != s[j]) & (s[i] != s[k]) & (s[j] != s[k]):
            ans -= 1
            
print(ans)

### FIXED CODE ###

n = int(input())
s = str(input())
ans = s.count('R') * s.count('G') * s.count('B')

for i in range(n - 1):
    for j in range(i + 1, n):
        k = j + j - i

        if k >= n:
            break

        if (s[i] != s[j]) & (s[i] != s[k]) & (s[j] != s[k]):
            ans -= 1
            
print(ans)
### BUGGY CODE ###

N = int(input())
A_LI = sorted(map(int, input().split()))
A_SET = set(A_LI)
ans = 0
for a in A_SET:
    cnt = A_LI.count(a)
    if cnt < a:
        ans += cnt
    else:
        ans += cnt - a
print(ans)


### FIXED CODE ###

N = int(input())
A_LI = sorted(map(int, input().split()))
a_dict = {}
ans = 0
pre = None
for a in A_LI:
    if a not in a_dict:
        if pre in a_dict:
            # 出揃った値について取り除く個数を求める
            if a_dict[pre] < pre:
                ans += a_dict[pre]
            else:
                ans += a_dict[pre] - pre
        pre = a
        a_dict[a] = 1
    else:
        a_dict[a] += 1
# 最後の値について取り除く個数を求める
if a_dict[pre] < pre:
    ans += a_dict[pre]
else:
    ans += a_dict[pre] - pre
print(ans)
### BUGGY CODE ###

n, k, q = map(int, input().split())

correct = []
for _ in range(q):
    a = int(input())
    correct.append(a)

for i in range(1, n+1):
    if k - (q - correct.count(i)) > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n, k, q = map(int, input().split())

point = [k-q] * n
for _ in range(q):
    a = int(input())
    point[a-1] += 1

for p in point:
    if p > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

s = input().strip('\n')
q = int(input().strip('\n'))

j = ''.join
turn = 0
for _ in range(q):
    query = input().strip('\n')
    if len(query) == 1:
        turn += 1
    else:
        two, f, c = query.split()
        if f == '1':
            if turn % 2 == 0:
                s = j([c, s])
            else:
                s = j([s, c])
        else:
            if turn % 2 == 0:
                s = j([s, c])
            else:
                s = j([c, s])

if turn % 2 == 0:
    print(s)
else:
     print(s[::-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline

s = input().strip()
q = int(input())
query = [list(input().strip().split()) for _ in range(q)]

left = ''
right = ''
t = False
for ls in query:
    if len(ls) == 1:
        t = not t
    else:
        two, f, c = ls
        if f == '1':
            if t:
                right += c
            else:
                left += c
        else:
            if t:
                left += c
            else:
                right += c

if t:
    print(right[::-1] + s[::-1] + left)
else:
    print(left[::-1] + s + right)
### BUGGY CODE ###

S=list(map(str,input()))
N=len(S)
Q=[0]*N
for i in range(N):
  p=i
  for j in range(1000):
    if S[p]=="R":
      p=p+1
    else:
      p=p-1
  Q[p]=Q[p]+1
print(*Q)

### FIXED CODE ###

S=list(map(str,input()))
N=len(S)
Q=[0]*N
R=[]
R1=[0]*N
L1=[0]*N
L=[]
V=[0]*N
for i in range(0,N):
  if S[i]=="R" and S[i+1]=="L":
    R.append(i)
  elif S[i]=="L" and S[i-1]=="R":
    L.append(i)
  else: V[i]=1

for i in R+L:
  Q[i]=1

x=0
for r in R:
  while x!=r:
    R1[x]=r
    x=x+1
x=N-1
for l in reversed(L):
  while x!=l:
    L1[x]=l
    x=x-1

for i in range(N):
  if V[i]==1:
    if S[i]=="R":
      if (R1[i]-i)%2==0:
        Q[R1[i]]=Q[R1[i]]+1
      else:
        Q[R1[i]+1]=Q[R1[i]+1]+1
    else:
      if (i-L1[i])%2==0:
        Q[L1[i]]=Q[L1[i]]+1
      else:
        Q[L1[i]-1]=Q[L1[i]-1]+1

print(*Q)
### BUGGY CODE ###

import math

N, M = map(int, input().split())
N, M = max(N,M), min(N,M)

if N == M:
    ans = math.factorial(N) ** 2 * 2
elif N - M == 1:
    ans = math.factorial(N) * math.factorial(M)
else:
    ans = 0

print(ans)


### FIXED CODE ###

import math

N, M = map(int, input().split())
N, M = max(N,M), min(N,M)
MOD = 10**9+7

if N == M:
    ans = math.factorial(N) ** 2 * 2
elif N - M == 1:
    ans = math.factorial(M) ** 2 * N
else:
    ans = 0

print(ans % MOD)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[a[i]-(i+1) for i in range(n)]
ans=9999999999999999
for bi in set(b):
    ans=min(ans,sum([abs(b[j]-bi) for j in range(n)]))
print(ans)

### FIXED CODE ###

import statistics
n=int(input())
a=list(map(int,input().split()))
b=[a[i]-(i+1) for i in range(n)]
b_median=statistics.median(b)
ans=int(sum([abs(b[i]-b_median) for i in range(n)]))
print(ans)
### BUGGY CODE ###

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

P=list(map(int,input().split()))

Swap=["" for i in range(M)]

for i in range(M):
    Swap[i]=set(map(int,input().split()))


i=1
finish=M
judge=1
judge_2=0


while judge==1:
    judge=0
    i=1

    while finish>1 and i <= finish-1:
        for j in range(i):
            if Swap[i] & Swap[j] != set():
                Swap[j]=Swap[i]|Swap[j]
                del Swap[i]
                judge=1
                judge_2=1
                finish-=1
                break
            
        #print(i,finish,judge,Swap)

        if judge_2==0:
            i+=1
        else:
            judge_2=0
        

#print(Y,j,k,Unstacked)

Other=set(range(1,N+1))
for l in range(finish):
    Other=Other - Swap[l]
    #print(l,Y,Other)

#print(Other)

Other=list(Other)

count=0

for i in range(finish):
    for j in list(Swap[i]):
        if P[j-1] in Swap[i]:
            #print(i,j,P[j-1],Y[i])
            count+=1
        

for m in Other:
    if P[m-1]==m:
        #print(m)
        count+=1

print(count)
        


### FIXED CODE ###

N, M = map(int,input().split())
P=list(map(int,input().split()))

Group=[i for i in range(N+1)]


Swap=[None]*M
for i in range(M):
    Swap[i]=sorted(map(int,input().split()))

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

for i in range(M):
    if find(Swap[i][1]) != find(Swap[i][0]):
        Group[find(Swap[i][1])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[find(Swap[i][0])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))

count=0

for i in range(N):
    if find(P[i])==find(i+1):
        count+=1


print(count)
### BUGGY CODE ###

k,s = map(int,input().split())
counter = 0
x = 0
while x <= k and x <= s:
    y = 0
    while y <= k and x+y<= s:
        z = s-y-x
        if 0<=z<=k:
            counter += 1
        y += 1
    x += 1
print(counter)

### FIXED CODE ###

k,s = map(int,input().split())
counter = 0
for x in range(k+1):
    if s-x >= k:
        for y in range(k+1):
            z = s-x-y
            if 0<=z<=k:
                counter += 1
    else:
        for y in range((s-x)+1):
            z = s-x-y
            if 0<=z<=k:
                counter += 1
print(counter)
### BUGGY CODE ###

r,g,b,n=map(int,input().split())

rlim=n//r
blim=n//b

blist=[]
for i in range(blim+1):
    blist.append(i*b)

cnt=0
for i in range(rlim+1):
    glim=(n-i*r)//g
    for j in range(glim+1):
        if (n-i*r-j*g) in blist:
            cnt+=1
print(cnt)

### FIXED CODE ###

r,g,b,n=map(int,input().split())

lst=[r,g,b]
lst.sort()
r=lst[2]
g=lst[1]
b=lst[0]

rlim=n//r
glim=n//g
blim=n//b

"""
blist = [i*b for i in range(blim+1)]

glist = [i*g for i in range(glim+1)]

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return True
        if guess > item:
            high = mid -1
        else:
            low = mid + 1
    return False
"""

cnt=0

for i in range(rlim+1):
    glim=(n-i*r)//g
    for j in range(glim+1):
        if (n-i*r-j*g)%b==0:
            cnt+=1
print(cnt)
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**18
    MX = 10**10
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,L = LI()
    road = [[0] * N for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        if c <= L:
            road[a-1][b-1] = c
            road[b-1][a-1] = c

    town = [[-1 for _ in range(N)] for _ in range(N)]

    for s in range(N):

        q = [(0,s)]
        town[s][s] = 0
        heapq.heapify(q)
        while q:
            z,u = heapq.heappop(q)
            if town[s][u] < z: continue
            n = z // MX
            w = z % MX
            for v in range(N):
                c = road[u][v]
                if c == 0: continue
                nn = n
                nw = w + c
                if nw > L:
                    nw = c
                    nn += 1

                nz = nn * MX + nw
                if town[s][v] < 0 or town[s][v] > nz:
                    town[s][v] = nz
                    heapq.heappush(q,(nz,v))

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        if town[s-1][t-1] < 0:
            print(-1)
        else:
            print(town[s-1][t-1]//MX)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq


def wf(d,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

def main():
    INF = 10**18
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,L = LI()
    road = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        if c <= L:
            road[a-1][b-1] = c
            road[b-1][a-1] = c

    road = wf(road,N)


    gas = [[INF] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if road[i][j] <= L:
                gas[i][j] = 1

    gas = wf(gas,N)

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        if gas[s-1][t-1] == INF:
            print(-1)
        else:
            print(gas[s-1][t-1]-1)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math
Q=int(input())
l=[0 for i in range(Q)]
r=[0 for i in range(Q)]
M=0
for i in range(Q):
    l[i],r[i]=map(int,input().split())
    if M<r[i]:
        M=r[i]
P=[True for i in range(M+1)]
P[0]=False
P[1]=False
S=[False for i in range(M+1)]
for i in range(2,int(math.sqrt(M))+1):
    if P[i]:
        for j in range(i*2,M+1,i):
            P[j]=False
for i in range(M+1):
    if P[i] and i%2==1:
        if P[(i+1)//2]:
            S[i]=True
R=[S[:i+1].count(True) for i in range(M+1)]
for i in range(Q):
    print(R[r[i]]-R[l[i]-1])


### FIXED CODE ###

import math
Q=int(input())
l=[0 for i in range(Q)]
r=[0 for i in range(Q)]
M=0
for i in range(Q):
    l[i],r[i]=map(int,input().split())
    if M<r[i]:
        M=r[i]
P=[True for i in range(M+1)]
P[0]=False
P[1]=False
S=[False for i in range(M+1)]
for i in range(2,int(math.sqrt(M))+1):
    if P[i]:
        for j in range(i*2,M+1,i):
            P[j]=False
R=[0 for i in range(M+1)]
k=0
for i in range(M+1):
    if P[i] and i%2==1:
        if P[(i+1)//2]:
            S[i]=True
            k+=1
    R[i]=k
for i in range(Q):
    print(R[r[i]]-R[l[i]-1])
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
M = 10**9+7

def nCr(n, r, mod=10**9+7):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

ans = 0
for i in range(K-1,N):
    t = nCr(i,K-1,M)
    ans += t*A[i]
A.sort(reverse=True)
for i in range(K-1,N):
    t = nCr(i,K-1,M)
    ans -= t*A[i]
print(ans%M)


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
M = 10**9+7

""" def nCr(n, r, mod=10**9+7):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod """
def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac

ans = 0
fac,ifac = make_tables(M,N)
for i in range(K-1,N):
    t = cmb(i,K-1,M,fac,ifac)
    ans += t*A[i]
A.sort(reverse=True)
for i in range(K-1,N):
    t = cmb(i,K-1,M,fac,ifac)
    ans -= t*A[i]
print(ans%M)
### BUGGY CODE ###

def main():
    s = list(input())
    s.reverse()
    MOD = 2019
    tot = 0
    ans = 0
    d = [0 for _ in range(MOD)]
    for i in range(len(s)):
        d[tot] += 1
        x = (10 ** i) % MOD
        p = int(s[i]) * x
        p %= MOD
        tot = (tot + p) % MOD
        ans += d[tot]
    return ans


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

def main():
    s = list(input())
    s.reverse()
    MOD = 2019
    tot = 0
    ans = 0
    d = [0 for _ in range(MOD)]
    for i in range(len(s)):
        d[tot] += 1
        x = pow(10, i, MOD)
        p = int(s[i]) * x
        p %= MOD
        tot = (tot + p) % MOD
        ans += d[tot]
    return ans


if __name__ == '__main__':
    print(main())