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

S = input()
N = len(S)
CNT = [0]*2019
CNT[0] = 1

for i in range(1, N+1):
    CNT[int(S[:i]) * pow(10, N-i)%2019] += 1
ans = 0
for cnt in CNT:
    if cnt==0: continue
    ans += (cnt*(cnt - 1)) // 2
print(ans)


### FIXED CODE ###

S = list(map(int, list(input())))[::-1]
N = len(S)
CNT = [0]*2019
CNT[0] = 1
num = 0
d = 0
for i in range(N):
    num += S[i]*pow(10, d, 2019)
    num %= 2019
    CNT[num] += 1
    d += 1
ans = 0 
for cnt in CNT:
    ans += (cnt*(cnt - 1)) // 2
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    a = [input() for i in range(n)]
    num = 0
    for i in range(len(a)):
        a[i] = "".join(sorted(a[i]))
    a.sort()
    for i in range(len(a)):
        e = a[i]
        j = 1
        while i+j < len(a) and e == a[i+j]:
            num = num + 1
            j = j + 1
    print(num)


main()


### FIXED CODE ###

def main(text=""):
    n = int(input())
    a = [input() for i in range(n)]
    #a = text.split("\n")[1:]
    num = 0
    for i in range(len(a)):
        a[i] = "".join(sorted(a[i]))
    a.sort()
    i = 0
    while i < len(a):
        e = a[i]
        j = 1
        while i+j < len(a) and e == a[i+j]:
            j = j + 1
        if j != 1:
            num = num + combination(j)
            i = i+j
        else:
            i = i+1
    print(num)


def combination(x):
    return int(x*(x-1)/2)


main()
### BUGGY CODE ###

import copy

n = int(input())
list1 = list(map(int,input().split()))
list2 = copy.copy(list1)

for x in range(n):
    kei = 0
    list2 = copy.copy(list1)
    del list2[x]
    for m in range(n-1):
        l = list2.pop(0)
        if l in list2:
            kei += list2.count(l)

    print(kei,sep="\n")


### FIXED CODE ###

import collections

n = int(input())
list1 = list(map(int,input().split()))
list2 = collections.Counter(list1)

kei1=0

for j in list2.values():
    kei1 += j * (j-1) // 2

for x in list1:
    print(kei1 - (list2[x] -1))
### BUGGY CODE ###

import bisect
primes = [0,0] + [1]*49999
for i in range(2, 223):
    if primes[i]:
        for j in range(i*i, 50001, i):
            primes[j] = 0

primes = [k for k, b in enumerate(primes) if b]
while True:
    n = int(input())
    if n == 0:
        break
    ans = 0
    mid = n // 2
    if mid in primes and n%2==0:
        ans += 1
    l, r = bisect.bisect_left(primes, mid), bisect.bisect_left(primes, n)
    left = [v for v in primes[:l]]
    right = [v for v in primes[l:r]]
    for i in right:
        for j in left:
            if i+j == n:
                ans += 1
                break
            if i+j > n:
                break
    print(ans)

### FIXED CODE ###

import bisect
primes = [0, 0] + [1] * 49999
for i in range(2, 224):
    if primes[i]:
        for j in range(i*i, 50001, i):
            primes[j] = 0
values = [i for i, k in enumerate(primes) if k]
while True:
    n = int(input())
    if n == 0:
        break
    I = bisect.bisect(values, n//2)
    print(len([1 for v in values[:I] if primes[n-v]]))
### BUGGY CODE ###

def main():
    n,m=map(int,input().split())
    ab = {}
    ab1 = {}
    for _ in range(m):
        a,b=map(int,input().split())
        ab.setdefault(a,[]).append(b)
        ab.setdefault(b,[]).append(a)
        ab1.setdefault(a,[]).append(b)
        ab1.setdefault(b,[]).append(a)
    g = []
    g.append(set([1]))
    marked = set()
    marked.add(1)
    while ab:
        g_add = set()
        for k in g[-1]:
            for x in ab[k]:
                if x not in marked:
                    g_add.add(x)
                    marked.add(x)
            del ab[k]
        g.append(g_add)
    if len(marked) < n:
        print('No')
        return
    print('Yes')
    result = [None] * n
    for i,s in enumerate(g):
        for k in s:
            result[k-1] = [e for e in g[i-1] if e in ab1[k]]
    for i in range(1,n):
        print(result[i][0])

main()

### FIXED CODE ###

def main():
    n,m=map(int,input().split())
    ab = {}
    ab1 = {}
    for _ in range(m):
        a,b=map(int,input().split())
        ab.setdefault(a,set()).add(b)
        ab.setdefault(b,set()).add(a)
        ab1.setdefault(a,set()).add(b)
        ab1.setdefault(b,set()).add(a)
    g = []
    g.append(set([1]))
    marked = set()
    marked.add(1)
    while ab:
        g_add = set()
        for k in g[-1]:
            for x in ab[k]:
                if x not in marked:
                    g_add.add(x)
                    marked.add(x)
            del ab[k]
        g.append(g_add)
    if len(marked) < n:
        print('No')
        return
    print('Yes')
    result = [None] * n
    for i,s in enumerate(g):
        if not i:
            continue
        for k in s:
            result[k-1] = (g[i-1]&ab1[k]).pop()
    for i in range(1,n):
        print(result[i])

main()
### BUGGY CODE ###

s = str(input())
n = int(input())

cand = [s[0]]
for i in range(len(s)):
    if len(cand) == n and s[i] > cand[-1]:
        continue
    for j in range(i, len(s)):
        tmp = s[i:j+1]
        #print(i,j, tmp, cand)
        if tmp in cand:
            continue
        cand += [tmp]
        #cand = sorted(cand)
        cand.sort()
        if len(cand) > n:
            cand.pop()


print(cand.pop())


### FIXED CODE ###

s = str(input())
n = int(input())

cand = [str(s[0])]
for i in range(len(s)):
    if len(cand) == n and s[i] > cand[-1]:
        continue
    for j in range(i, len(s)):
        tmp = s[i:j+1]
        #print(i,j, tmp, cand)
        if len(cand) == n and tmp > cand[-1]:
            break
        if tmp in cand:
            continue
        cand += [tmp]
        #cand = sorted(cand)
        cand.sort()
        if len(cand) > n:
            cand.pop()


print(cand.pop())
### BUGGY CODE ###

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

z = 1
for i in range(k):
    z = z * a[i]

for i in range(n-k):
    t = a[k+i] * z / a[i]
    if z < t:
        print("Yes")
    else:
        print("No")
    z = t

### FIXED CODE ###

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

for i in range(n-k):
    if a[k+i] > a[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
for j in range(q):
  bc = list(map(int, input().split()))
  res = bc[0]
  for j in range(n):
    if a[j] == res:
      a[j] = bc[1]
    else:
      a[j] = a[j]
  print(sum(a))

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int, input().split()))
count = collections.Counter(a)
q = int(input())
s = sum(a)

for i in range(q):
  b, c = map(int, input().split())
  s = s - (b - c) * count[b]
  
  count[c] += count[b]
  count[b] = 0
  print(s)
### BUGGY CODE ###


def main():
#    with open("input.txt", "r") as f:
#        t = f.readlines()
#        N = int(t[0].split()[0])
#        K = int(t[0].split()[1])
#        h = t[1].split()
    N, K  = map(int, input().split())
    h = list(map(int, input().split()))
#    print(h)
#    print(len(h))
    dp = [10**9] * max(N,K)
    dp[0] = 0

    for i in range(N):
        j = 0
        L = min(K, i)
        while j <= L:
            #print(i)
            if dp[i] > dp[i-j] + abs(int(h[i])-int(h[i-j])):
                dp[i] = dp[i-j] + abs(int(h[i])-int(h[i-j]))
            j += 1
    print(dp[N-1])

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K  = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10**9] * N
    dp[0] = 0

    for i in range(N):
        dp[i] = min([dp[i-j] + abs(h[i]-h[i-j]) for j in range(min(K,i)+1)])
    print(dp[N-1])

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

# use faster method than input()
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def manhattan(pos1, pos2):
    return abs(pos1[0]-pos2[0]) + abs(pos2[1]-pos1[1])


H, W, D = map(int, input().split())
A = [(0, 0)]*(H*W)
for r in range(H):
    l = list(map(int, input().split()))
    for c in range(W):
        A[l[c]-1] = (r, c)

dist = [0]*(H*W)
for i in range(H*W):
    if i+D < H*W:
        dist[i] = manhattan(A[i], A[i+D])


Q = int(input())
L = []

ans_list = [0]*Q
for i in range(Q):
    ans = 0
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    while a+D <= b:
        ans += dist[a]
        a += D
    ans_list[i] = ans

for ans in ans_list:
    print(ans)


### FIXED CODE ###

# use faster method than input()
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def manhattan(pos1, pos2):
    return abs(pos1[0]-pos2[0]) + abs(pos2[1]-pos1[1])


H, W, D = map(int, input().split())
A = [(0, 0)]*(H*W)
for r in range(H):
    l = list(map(int, input().split()))
    for c in range(W):
        A[l[c]-1] = (r, c)

dist = [0]*(H*W)
for i in range(D, H*W):
    dist[i] = dist[i-D]+manhattan(A[i], A[i-D])


Q = int(input())
L = []

ans_list = [0]*Q
for i in range(Q):
    ans = 0
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    ans = dist[b]-dist[a]
    ans_list[i] = ans

for ans in ans_list:
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def main():
    S = list(input())
    BW = {'B':[], 'W':[]}
    cnt = {'B':0, 'W':0}
    pre = S[0]
    cnt[pre] += 1
    for i in range(1, len(S)):
        now = S[i]
        if pre == now:
            cnt[pre] += 1
        else:
            BW[pre].append(cnt[pre])
            cnt[pre] = 0
            cnt[now] = 1
            pre = now
        # print(cnt)
        # print(BW)
    if cnt[pre] != 0:
        BW[pre].append(cnt[pre])

    if S[0] == 'W':
        BW['W'].pop(0)
    if S[-1] == 'B':
        BW['B'].pop(-1)
    ans = 0
    for i in range(len(BW['B'])):
        ans += sum(BW['B'][:i+1])*BW['W'][i]
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
def main():
    S = list(input())
    Bcnt = 0
    ans = 0
    for i in range(len(S)):
        if S[i] == 'B':
            Bcnt += 1
        else:
            ans += Bcnt
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

resultCount = 0
NGNum = float('inf')
for i in range(N):
    isMitasu = True
    # 計算量削減のため、既に駄目だと分かっている数の場合計算しない
    if P[i] < NGNum:
        for j in range(i):
            if P[i] > P[j]:
                isMitasu = False
                # 計算量削減のため、駄目だった数を控える
                if P[i] < NGNum:
                    NGNum = P[i]
                break
    else:
        isMitasu = False
    if isMitasu:
        resultCount += 1
print(resultCount)

### FIXED CODE ###

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


# 最小値更新して越えてたらアウト
resultCount = 0
minNum = P[0]
for i in range(N):
    isMitasu = True
    if i != 0:
        if P[i] > minNum:
            isMitasu = False
        else:
            # 最小値更新
            minNum = P[i]
    if isMitasu:
        resultCount += 1
print(resultCount)
### BUGGY CODE ###

from collections import deque

N,X,Y = map(int,input().split())

L= [[1]]+[[i-1,i+1] for i in range(1,N-1)]+ [[N-2]]
L[X-1].append(Y-1)
L[Y-1].append(X-1)

def BFS(x,L,k):
  cnt=0
  d=[-1 for _ in range(N)] #距離
  d[x]=0
  v=deque([x])
  
  while len(v)>0:
    a=v.popleft()
    for num in L[a]:
      if d[num]==-1:
        d[num]=d[a]+1
        v.append(num)
        if d[num]==k:
          cnt+=1
  return cnt

for k in range(1,N):
  ans=0
  for j in range(N):
    ans+=BFS(j,L,k)
  print(ans//2)

### FIXED CODE ###

N,X,Y=map(int,input().split())
cost=[[] for _ in range(N)]

for i in range(N-1):
  cost[i].append(i+1)
for j in range(1,N):
  cost[j].append(j-1)

cost[X-1].append(Y-1)
cost[Y-1].append(X-1)
#print(cost)

def bfs(v):
    d=[-1]*N
    d[v]=0
    q=[v]
    c=1
    while q:
        q1=[]
        for i in q:
            for j in cost[i]:
                if d[j]==-1:
                    d[j]=c
                    q1.append(j)
        q=q1
        c+=1
        #print(d,q)
    return d

d=dict()
for m in range(N):
  tmp=bfs(m)
  #print(tmp)
  for num in tmp:
    if num not in d:
      d[num]=1
    else:
      d[num] += 1
#print(d)

for z in range(1,N):
  if z in d:
    print(d[z]//2)
  else:
    print(0)
### BUGGY CODE ###

import numpy as np
a,b=list(map(int,input().split()))

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def cf(x1,x2):
    cf=[]
    for i in range(1,gcd(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

def di(z,y):
  for i in range(len(y)):
    if y[i] != 1 and z % y[i] == 0:
      return False
  for i in range(2,int(np.sqrt(z))+1):
    if z % i == 0:
      return False
  return True

tmp=cf(a,b)
sum=0
y=[]
for j in range(len(tmp)):
  if di(tmp[j],y):
    y.append(tmp[j])
    sum += 1

print(sum)

### FIXED CODE ###

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

def cf(x1,x2):
    cf=[]
    n =max(x1,x2)
    m=min(x1,x2)
    for i in range(1,int(m**0.5)+1):
        if m % i == 0:
          if n % i == 0:
            cf.append(i)
          if i != m//i and n % (m//i) == 0:
            cf.append(m//i)
    return cf

def is_prime(z):
  for i in range(2,int(z**0.5)+1):
    if i*i > z:
      break
    if z % i == 0:
      return False
  return True

tmp=cf(a,b)
sum=0
y=[]
for k in tmp:
  if is_prime(k):
    sum += 1

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

"""
最後の2つを決める：[0,x) [x,N)
小問題2つに分割できる。
全ての連続区間を計算すればよい
"""

from functools import lru_cache
import itertools

N = int(input())
A = [int(x) for x in input().split()]

A_cum = tuple(itertools.accumulate(A))

@lru_cache(None)
def min_cost(L,R):
    # 区間[L,R)
    if R - L == 1:
        return 0
    x = min(min_cost(L,i) + min_cost(i,R) for i in range(L+1,R))
    x += A_cum[R-1] - (A_cum[L-1] if L > 0 else 0)
    return x

answer = min_cost(0,N)
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
最後の2つを決める：[0,x) [x,N)
小問題2つに分割できる。
全ての連続区間を計算すればよい
"""

N = int(input())
A = np.array(input().split(), np.int64)

# Acum[L,R] = A[L:R].sum()
Acum = np.zeros((N,N+1), dtype=np.int64)
for L in range(N):
    Acum[L,L+1:] = A[L:].cumsum()

dp = np.zeros((N,N+1), dtype=np.int64)
for size in range(2,N+1):
    for L in range(N-size+1):
        R = L + size
        dp[L,R] = (dp[L,L+1:R] + dp[L+1:R,R]).min() + Acum[L,R]

answer = dp[0,N]
print(answer)
### BUGGY CODE ###

import copy

t_list = []
n, m, q = map(int, input().split())
for i in range(q):
    t_list.append(list(map(int, input().split())))

q = []

for i in range(1, m+1):
    q.append(str(i-1))

while True:
    if len(q[0]) == n:
        break
    else:
        item = q.pop(0)
        for i in range(int(item[-1]), m):
            q.append(''.join([item, str(i)]))

ret = 0

for item in q:
    score = 0
    for t_item in t_list:
        if int(item[t_item[1]-1]) - int(item[t_item[0]-1]) == t_item[2]:
            score += t_item[3]
    ret = max(ret, score)

print(ret)


### FIXED CODE ###

import itertools

t_list = []
n, m, q = map(int, input().split())
for i in range(q):
    t_list.append(list(map(int, input().split())))

q = []

for i in range(1, m+1):
    q.append(i)

ret = 0

for item in itertools.combinations_with_replacement(q, n):
    score = 0
    for t_item in t_list:
        if item[t_item[1]-1] - item[t_item[0]-1] == t_item[2]:
            score += t_item[3]
    ret = max(ret, score)

print(ret)
### BUGGY CODE ###

a = int(input())
num = []
for i in range(1,a+1):
  num.append(i)
ans = sum(num) - max(num)
print(ans)

### FIXED CODE ###

a = int(input())
ans = a*(a-1)//2
print(int(ans))
### BUGGY CODE ###

L,R = map(int, input().split())

ans = 2019
for i in range(L,R):
  for j in range(i + 1,R + 1):
    aa = i * j
    aaa = aa % 2019
    
    if aaa < ans:
      ans = aaa
      
print(ans)

### FIXED CODE ###

L,R = map(int, input().split())

if R - L >= 2019:
  print(0)
else:
  ans = 2019
  for i in range(L,R):
    for j in range(i + 1,R + 1):
      aa = i * j
      aaa = aa % 2019
    
      if aaa < ans:
        ans = aaa
    
      if ans == 0:
        break
      
  print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
l1=set(l)
c=0
for i in l1:
  if l.count(i)>=i:
    c+=l.count(i)-i
  else:
    c+=l.count(i)
print(c)


### FIXED CODE ###

from collections import defaultdict
l=defaultdict(int)
n=int(input())
l1=list(map(int,input().split()))
for i in l1:
  l[i]+=1
b=True
lset=set(l1)
answer=0
for i in lset:
  if l[i]!=i:
    if l[i]<i:
      answer+=l[i]
    else:
      answer+=min(l[i]-i,l[i])
print(answer)
### BUGGY CODE ###

s = input()
n = len(s)

mod = [0]*2019
mod[0] = 1
pre = 0
for i in reversed(range(n)):
    pre = (pre + int(s[i])*10**(n-i-1))%2019
    mod[pre] += 1
print(sum([m*(m-1)//2 for m in mod]))

### FIXED CODE ###

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

mod = [0]*2019
pre = 0
mod[pre] = 1
x = 1
for i in range(n):
    pre += int(s[i])*x
    pre %= 2019
    mod[pre] += 1
    x *= 10
    x %=2019
print(sum([m*(m-1)//2 for m in mod]))
### BUGGY CODE ###

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

def kaijo(n):
    result=1
    for i in range(2,n+1):
        result*=i
    return result
    
def count(n,m):
    return kaijo(n)*kaijo(m)

if n-m==-1 or n-m==1:
    result=count(n,m)
    amari=result%(10**9+7)
    print amari
elif n-m==0:
    result=count(n,m)
    result*=2
    amari=result%(10**9+7)
    print amari
else:
    print 0

### FIXED CODE ###

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

mod=10**9+7

def kaijo(n):
    result=1
    for i in range(2,n+1):
        result*=i
        if result>mod:
            result=result%mod
    return result
    
def count(n,m):
    return kaijo(n)*kaijo(m)

if n-m==-1 or n-m==1:
    result=count(n,m)
    amari=result%mod
    print amari
elif n-m==0:
    result=count(n,m)
    result*=2
    amari=result%mod
    print amari
else:
    print 0
### BUGGY CODE ###

import sys
from bisect import bisect_right as bi_r
from heapq import heapify, heappop, heappush

n, m, v, p, *a = map(int, sys.stdin.read().split())

def main():
    a.sort()
    # return a

    for i in range(n):
        l = bi_r(a, a[i]) - 1
        r = max(0, v - l - 1)
        if r >= p:
            cand = a[l+1:n-p+1]
            ma = cand[-1]
            heapify(cand)
            remain = m * (r - (p - 1))
            while True:
                x = heappop(cand)
                if x == ma:
                    heappush(cand, x)
                    break
                d = ma - x
                if remain < d:
                    remain = 0
                    break
                remain -= d
                heappush(cand, ma)

            if not remain:
                if a[i] + m >= ma:
                    return n - i
            le = len(cand)
            ma += (remain + le - 1) // le
            if a[i] + m >= ma:
                return n - i
        else:
            if a[i] + m >= a[n-p]:
                return n - i

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

### FIXED CODE ###

import sys

n, m, v, p, *a = map(int, sys.stdin.read().split())
a.sort(reverse=True)

def possible(i):
    score = a[i] + m
    if i < p:
        return True
    else:
        every_ok = p - 1 + n - i 
        if every_ok >= v:
            if score >= a[p-1]:
                return True
            else:
                return False
        else:
            s = m * (v - every_ok)
            limit = 0
            for j in range(p-1, i):
                if a[j] > score:
                    return False
                limit += score - a[j]
            if s > limit:
                return False
            return True

def main():
    lo = -1
    hi = n
    while lo + 1 < hi:
        i = (lo + hi) // 2
        if possible(i):
            lo = i
        else:
            hi = i
        
    return lo + 1

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

def isprime(n):
    if n < 2: return 0
    elif n == 2: return 1

    if n % 2 == 0: return 0

    for i in range(3, n, 2):
        if n % i == 0 : return 0

    return 1

N = int(input())
n = [int(input()) for i in range(N)]

a = [i for i in n if isprime(i)]

print(len(a))


### FIXED CODE ###

def isprime(n):
    if n < 2: return 0
    elif n == 2: return 1

    if n % 2 == 0: return 0

    for i in range(3, n, 2):
        if i > n/i: return 1
        if n % i == 0 : return 0

    return 1

N = int(input())
n = [int(input()) for i in range(N)]

a = [i for i in n if isprime(i)]

print(len(a))
### BUGGY CODE ###

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

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
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))

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

N,K = II()
A = III()

sumA = sum(A)

for i in range(1,sumA+1)[::-1]:
  if sumA%i != 0:
    continue
  r = [0]*N
  for j in range(N):
    r[j] = A[j]%i
  sumr = sum(r)
  if sumr%i != 0:
    continue
  r.sort(reverse=True)
  num = 0
  for k in range(sumr//i):
    num += i-r[k]
  if num <= K:
    print(i)
    exit()

### FIXED CODE ###

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

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
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))

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

def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
    if i != n // i:
      divisors.append(n//i)

  divisors.sort(reverse=True)
  return divisors

N,K = II()
A = III()

sumA = sum(A)
kouho = make_divisors(sumA)

for i in kouho:
  if sumA%i != 0:
    continue
  r = [0]*N
  for j in range(N):
    r[j] = A[j]%i
  sumr = sum(r)
  if sumr%i != 0:
    continue
  r.sort(reverse=True)
  num = 0
  for k in range(sumr//i):
    num += i-r[k]
  if num <= K:
    print(i)
    exit()
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
a.sort()
ans=0
def combination(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)
    return a // b
for i in range(n-k+1):
    ans-=a[i]*combination(n-i-1,k-1)%mod
    ans%=mod
a.sort(reverse=True)
for i in range(n-k+1):
    ans+=a[i]*combination(n-i-1,k-1)%mod
    ans%=mod

print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
mod=10**9+7
ans=0
MOD=10**9+7

factorial = [1]
inverse = [1]
for i in range(1, n+2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))
 
 
# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD
for i in range(n-k+1):
    ans-=a[i]*nCr(n-i-1,k-1)%mod
    ans%=mod
a=a[::-1]
for i in range(n-k+1):
    ans+=a[i]*nCr(n-i-1,k-1)%mod
    ans%=mod

print(ans%mod)