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

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N,K = list(map(int,input().split()))
A = sorted(list(map(int,input().split())))
B = [A[i+1]-A[i]  for i in range(len(A)-1)]
lim = math.ceil(len(B)/2)

L = 10**9+7
ans = 0
multi = combinations_count(N,K)
for j in range(lim):
    front = j + 1
    back = N - front
    tmp_b = 0
    tmp_f = 0
    if front >= K:
        tmp_f = combinations_count(front,K) % L
    if back >= K:
        tmp_b = combinations_count(back,K) % L
    if j == (len(B)-1)/2:
        ans += (multi - tmp_b - tmp_f)*(B[j]) % L
    else:
        ans += (multi - tmp_b - tmp_f)*(B[j]+B[len(B)-1-j]) % L
print(ans%L)

### FIXED CODE ###

import math

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5+5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N,K = list(map(int,input().split()))
A = sorted(tuple(map(int,input().split())))
B = tuple(A[i+1]-A[i]  for i in range(len(A)-1))
lim = math.ceil(len(B)/2)

L = 10**9+7
ans = 0
multi = cmb(N,K,mod)
for j in range(lim):
    front = j + 1
    back = N - front
    tmp_b = 0
    tmp_f = 0
    if front >= K:
        tmp_f = cmb(front,K,mod)
    if back >= K:
        tmp_b = cmb(back,K,mod)
    if j == (len(B)-1)/2:
        ans += (multi - tmp_b - tmp_f)*(B[j]) % L
    else:
        ans += (multi - tmp_b - tmp_f)*(B[j]+B[len(B)-1-j]) % L
print(ans%L)
### BUGGY CODE ###

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

### FIXED CODE ###

from collections import*
from bisect import*
s=input()
n=len(s)
t=input()
d=defaultdict(list)
for i,c in enumerate(s):
    d[c].append(i)
m=-1
o=0
for c in t:
    if not d[c]:
        print(-1)
        exit()
    i=bisect(d[c],m)
    if len(d[c])==i:
        o+=1
        m=d[c][0]
    else:
        m=d[c][i]
print(o*n+m+1)
### BUGGY CODE ###

import sys
n, y = map(int, input().split())
for a in range(n+1):
	
	for b in range(n+1):
		
		for c in range(n+1):
			if a + b + c == n :
				if 10000*a + 5000*b + 1000*c == y:
					print('{} {} {}'.format(a,b,c))
					sys.exit()
print('-1 -1 -1')

### FIXED CODE ###

import sys
n, y = map(int, input().split())

for a in list(range(n+1)):
	for b in list(range(n+1-a)):
		c = n - a - b
		if a+b+c==n and 10000*a + 5000*b + 1000*c==y:
			print('{} {} {}'.format(a,b,c))
			sys.exit()

print('-1 -1 -1')
### BUGGY CODE ###

s=list(input())
q=int(input())
ans=0
for i in range(q):
    query=input().split()
    if query==['1']:
        ans+=1
    else:
        if query[1]=='1' and ans%2==0:
            s.insert(0,query[2])
        elif query[1]=='1' and ans%2==1:
            s.append(query[2])
        elif query[1]=='2' and ans%2==0:
            s.append(query[2])
        else:
            s.insert(0,query[2])
if ans%2==1:
    s.reverse()
print(''.join(s))



### FIXED CODE ###

s=list(input())
q=int(input())
ans=0
mae=[]
ato=[]
for i in range(q):
    query=input().split()
    if query==['1']:
        ans+=1
    else:
        if query[1]=='1' and ans%2==0:
            mae.append(query[2])
        elif query[1]=='1' and ans%2==1:
            ato.append(query[2])
        elif query[1]=='2' and ans%2==0:
            ato.append(query[2])
        else:
            mae.append(query[2])
if ans%2==1:
    s.reverse()
    ato.reverse()
    s=ato+s+mae
else:
    mae.reverse()
    s=mae+s+ato
print(''.join(s))
### BUGGY CODE ###

import collections
INF = 10**18
def bfs(starth,startw):
    d = [[-1]*w for i in range(h)]
    d[starth][startw] = 0
    q = collections.deque([])
    q.append((starth,startw))
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while q:
        p = q.popleft()
        nowh = p[0]
        noww = p[1]
        for i in range(4):
            nexth = nowh + dy[i]
            nextw = noww + dx[i]
            if 0<=nextw<w and 0<=nexth<h:
                if d[nexth][nextw] == -1 and li[nexth][nextw] != "#":
                    q.append([nexth,nextw])
                    d[nexth][nextw] = d[nowh][noww] + 1
    return d
h,w = map(int,input().split())
li = [list(input()) for i in range(h)]
cost = [[INF]*w for i in range(h)]
koho = []
for i in range(h):
    for j in range(w):
        if li[i][j] == "#":
            koho.append([i,j])
for i in range(len(koho)):
    starth = koho[i][0]
    startw = koho[i][1]
    a = bfs(starth,startw)
    for j in range(h):
        for k in range(w):
            cost[j][k] = min(cost[j][k],a[j][k])

ans = -1
for i in range(h):
    for j in range(w):
        ans = max(cost[i][j],ans)
print(ans)


### FIXED CODE ###

import collections
INF = 10**18
h,w = map(int,input().split())
li = [list(input()) for i in range(h)]
koho = []
d = [[-1]*w for i in range(h)]
q = collections.deque([])
for i in range(h):
    for j in range(w):
        if li[i][j] == "#":
            d[i][j] = 0
            q.append([i,j])
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while q:
    p = q.popleft()
    y = p[0]
    x = p[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<w and 0<=ny<h:
            if d[ny][nx] == -1:
                q.append([ny,nx])
                d[ny][nx] = d[y][x] + 1
ans = -1
for i in range(h):
    for j in range(w):
        ans = max(ans,d[i][j])
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(str, input().split()))
Q = int(input())
S = []
c = 0

for i in range(Q):
    B, C = map(str,input().split())
    if B in A:
        c = A.count(B)
        string = ",".join(A)
        string_new = string.replace(B, C,c)
        A =  string_new.split(",")

    S.append(sum(map((lambda x: int(x)), A)))


for s in S:
    print(s)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
S = []
c = 0
s = sum(A)
table = [0] * 100010
# A = pd.Series(A)
# for a in A:
#     print(a)

for i in A:
    table[i] += 1

for i in range(Q):
    B, C = map(int,input().split())
    # if B in A:
    # c = A.count(B)
    c = table[B]
    s += (C - B) * c
    table[C] += table[B]
    table[B] = 0
    # print(s)
        # print((C - B) * c) 
        # string = ",".join(A)
        # string_new = string.replace(B,C)
        # A =  string_new.split(",")
        # s = sum(map((lambda x: int(x)), A))
    S.append(s)

        # A.replace(B, C,c)
        # while B in A:
        #     A[A.index(B)] = C
    # for a in A:
    #     print(a)
    # else:
        # S.append(s)



for s in S:
    print(s)
### BUGGY CODE ###

h,w,m=map(int,input().split())
B=[[] for i in range(h)]
H=[0]*h
W=[0]*w
for i in range(m):
    p,q=map(int,input().split())
    B[p-1].append(q-1)
    H[p-1]+=1
    W[q-1]+=1
mH=max(H)
mW=max(W)
CH=[]
for i in range(h):
    if H[i]==mH:
        CH.append(i)
CW=[]
for i in range(w):
    if W[i]==mW:
        CW.append(i)
flag=0
for ch in CH:
    for cw in CW:
        if cw in B[ch]:
            continue
        else:
            flag=1
            break
if flag:
    print(mH+mW)
else:
    print(mH+mW-1)

### FIXED CODE ###

h,w,m=map(int,input().split())
B=[[] for i in range(h)]
H=[0]*h
W=[0]*w
for i in range(m):
    p,q=map(int,input().split())
    B[p-1].append(q-1)
    H[p-1]+=1
    W[q-1]+=1
mH=max(H)
mW=max(W)
CH=[]
for i in range(h):
    if H[i]==mH:
        CH.append(i)
CW=[]
for i in range(w):
    if W[i]==mW:
        CW.append(i)
CW=set(CW)
flag=0
if len(CH)*len(CW)>m:
    flag=1
else:
    for ch in CH:
        b=set(B[ch])
        if CW<=b:
            continue
        else:
            flag=1
            break
if flag:
    print(mH+mW)
else:
    print(mH+mW-1)
### BUGGY CODE ###

import math 

def mygcd(x,y,z):
	return math.gcd(math.gcd(x,y),z)

mysum = 0
K = int(input())
for i in range(1,K+1):
	for j in range(1,K+1):
		for k in range(1,K+1):
			mysum += mygcd(i,j,k)

print(mysum)

### FIXED CODE ###

from math import gcd 

mysum = 0
K = int(input())
for i in range(1,K+1):
	for j in range(1,K+1):
		for k in range(1,K+1):
			mysum += gcd(gcd(i,j),k)

print(mysum)
### BUGGY CODE ###

from collections import Counter

def div(n):
    lower_div, upper_div = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_div.append(i)
            if i != n // i:
                upper_div.append(n // i)
        i += 1
    return lower_div + upper_div[::-1]

n = int(input())
A = list(map(int, input().split()))
s = set(A)
c = Counter(A)
cnt = 0
for a in A:
    if c[a] >= 2:
        continue
    else:
        d = set(div(a))
        if len(d - s) == len(d) - 1:
            cnt += 1
print(cnt)


### FIXED CODE ###

from collections import Counter
n = int(input())
A = sorted(map(int, input().split()))
M = A[-1]
c = Counter(A)
s = set()
ans = 0
for a in A:
    if a in s:
        continue
    if c[a] == 1:
        ans += 1
    i = 1
    while a * i <= M:
        s.add(a * i)
        i += 1
print(ans)
### BUGGY CODE ###

import fractions
A,B = map(int,input().split())

L = range(2,fractions.gcd(A,B)+1)
# print(list(L))
prime = []

for i in L:
    if (A%i != 0) or (B%i != 0):
        continue

    primecheck = True
    for j in prime:
        if i%j == 0:
            primecheck = False

    if primecheck == True:
        prime.append(i)
prime.append(1)

# print(prime)
print(len(prime))

### FIXED CODE ###

import math
A,B = map(int,input().split())
N = max(A,B)
prime = []

tA = A
tB = B
for i in range(2, math.ceil(N**0.5)+1):
    Aflag = False
    Bflag = False
    if tA%i==0:
        Aflag = True
        while tA%i==0:
            tA //= i
    if tB%i==0:
        Bflag = True
        while tB%i==0:
            tB //= i
    if Aflag == True and Bflag == True:
        prime.append(i)

if tA!=1 and tA == tB:
    prime.append(tA)

# print(prime)
print(len(prime)+1)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
dp=[[0 for j in range(k+1)] for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    r=[0]*(k+2)
    for j in range(1,k+2):
        r[j]=(r[j-1]+dp[i-1][j-1])%mod
    for j in range(k+1):
        dp[i][j]=(r[j+1]-r[max(0,j-a[i-1])])%mod
print(dp[n][k]%mod)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
dp=[[0 for j in range(k+1)] for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    r=[0]*(k+2)
    for j in range(1,k+2):
        r[j]=(r[j-1]+dp[i-1][j-1])%mod
    for j in range(k+1):
        dp[i][j]=(r[j+1]-r[max(0,j-a[i-1])])%mod
print(dp[n][k]%mod)
### BUGGY CODE ###

import math
num_limit = int(input())
s_limit = int(num_limit**0.5)
for i in range(1,num_limit+1):
    xyz_count = 0
    s_limit = int(i ** 0.5)
    for j in range(1,s_limit+1):
        if i <= j**2:
            break
        for k in range(1,j+1):
            if i <= j**2 + k**2 + j*k:
                break
            for l in range(1,k+1):
                if i < j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    break
                elif i == j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    if j > k:
                        if k > l:
                            xyz_count += 6
                        else:
                            xyz_count += 3
                    elif k == l:
                        xyz_count += 1
                    else:
                        xyz_count += 3
    print(xyz_count)

### FIXED CODE ###

num_limit = int(input())
num_list = [0] * num_limit
j_limit = int(num_limit ** 0.5)
for j in range(1,j_limit+1):
    for k in range(1,j + 1):
        for l in range(1,k+1):
            if num_limit >= j**2 + k**2 + l**2 + j*k + k*l + l*j:
                if j > k:
                    if k > l:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 6
                    else:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                elif k > l:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                else:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 1
for i in num_list:
    print(i)
### BUGGY CODE ###

from sys import stdin

N, M = map(int, stdin.readline().split())
A = list(map(int, stdin.readline().split()))
lst = []
for _ in range(M):
    B, C = map(int, stdin.readline().split())
    lst.extend([C]*B)
lst.sort(reverse=True)
A.sort()
for i in range(min(len(A), len(lst))):
    A[i] = max(A[i], lst[i])

print(sum(A))

### FIXED CODE ###

from sys import stdin, exit

N, M = map(int, stdin.readline().split())
A = list(map(int, stdin.readline().split()))
p = [(A[i], 1) for i in range(N)]
for _ in range(M):
    B, C = map(int, stdin.readline().split())
    p.append((C, B))

p.sort(reverse=True)

ans, cnt = 0, N
for (v, c) in p:
    use = min(c, cnt)
    ans += use * v
    cnt -= use

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

from operator import itemgetter


class BIT:
    """一点加算、区間取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def build(self, array):
        """arrayを初期値とするBinaryIndexTreeを構築する O(N)"""
        for i in range(self.size):
            self.bit[i + 1] = array[i]
        for i in range(1, self.size):
            if i + (i & -i) > self.size:
                continue
            self.bit[i + (i & -i)] += self.bit[i]

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目の要素にvalを加える"""
        i += 1
        while i <= self.size:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


n, q = map(int, input().split())
c = list(map(int, input().split()))
query = [list(map(int, input().split())) + [i] for i in range(q)]


bit = BIT(n)
memo = {}

ans = [0] * q
query = sorted(query, key=itemgetter(1))
ind = 0
for l, r, i in query:
    while ind < r:
        if c[ind] in memo:
            old_ind = memo[c[ind]]
        else:
            old_ind = -1
        memo[c[ind]] = ind
        bit.add(ind, 1)
        if old_ind != -1:
            bit.add(old_ind, -1)
        ind += 1
    ans[i] = bit.get_sum(l - 1, r)

for i in range(q):
    print(ans[i])

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from operator import itemgetter


class BIT:
    """一点加算、区間取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def build(self, array):
        """arrayを初期値とするBinaryIndexTreeを構築する O(N)"""
        for i in range(self.size):
            self.bit[i + 1] = array[i]
        for i in range(1, self.size):
            if i + (i & -i) > self.size:
                continue
            self.bit[i + (i & -i)] += self.bit[i]

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目の要素にvalを加える"""
        i += 1
        while i <= self.size:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


n, q = map(int, input().split())
c = list(map(int, input().split()))
query = [list(map(int, input().split())) + [i] for i in range(q)]


bit = BIT(n)
memo = {}
ans = [0] * q
query = sorted(query, key=itemgetter(1))
ind = 0

for l, r, i in query:
    while ind < r:
        if c[ind] in memo:
            old_ind = memo[c[ind]]
        else:
            old_ind = -1
        memo[c[ind]] = ind
        bit.add(ind, 1)
        if old_ind != -1:
            bit.add(old_ind, -1)
        ind += 1
    ans[i] = bit.get_sum(l - 1, r)

print("\n".join(map(str, ans)))
### BUGGY CODE ###

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

dp = [[-float('inf')] * (N + 1) for _ in range(2 * N + 1)]
for i in range(2 * N + 1):
    dp[i][0] = 0
for i in range(2 * N):
    for j in range(1, N + 1):
        dp[i + 1][j] = max(dp[i][j], dp[i][j - 1] + A[i])

dp2 = [0] * (N + 1)
for i in range(N + 1):
    B = A[i + N:]
    B.sort()
    dp2[i] = sum(B[:N])

ans = -float('inf')
for i in range(N + 1):
    S1 = dp[i + N][N]
    S2 = dp2[i]
    ans = max(ans, S1 - S2)

print(ans)


### FIXED CODE ###

from heapq import heappush, heapreplace


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

dp = [0] * (N + 1)
q = []
cnt = 0
for i in range(N):
    a = A[i]
    heappush(q, a)
    cnt += a
dp[0] = cnt
for i in range(N, 2 * N):
    a = A[i]
    if a > q[0]:
        cnt += a - heapreplace(q, a)
    dp[i - N + 1] = cnt


dp2 = [0] * (N + 1)
q = []
cnt = 0
for i in range(2 * N, 3 * N):
    a = A[i]
    heappush(q, -a)
    cnt += a
dp2[N] = cnt
for i in range(2 * N - 1, N - 1, -1):
    a = A[i]
    if a < -q[0]:
        cnt += a - (-heapreplace(q, -a))
    dp2[i - N] = cnt

ans = -float('inf')
for i in range(N + 1):
    ans = max(ans, dp[i] - dp2[i])
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
R = 0
G = 0
B = 0
nsum = 0
for s in S:
    if s == "R":
        R += 1
    elif s == "G":
        G += 1
    else:
        B += 1
count = 0
for i in range(N):
    for k in range(i+1,N):
        if not S[i] == S[k]:
            if 2*k - i <= N - 1:
                if S[i] != S[2*k - i] and S[k] != S[2*k - i]:
                    count += 1
print(R*G*B - count)

### FIXED CODE ###

N = int(input())
S = input()
R = 0
G = 0
B = 0
nsum = 0
for s in S:
    if s == "R":
        R += 1
    elif s == "G":
        G += 1
    else:
        B += 1
count = 0
for i in range(N):
    for k in range(i+1,N):
        if not S[i] == S[k]:
            if 2*k - i <= N - 1:
                if S[i] != S[2*k - i] and S[k] != S[2*k - i]:
                    count += 1
print(R*G*B - count)
### BUGGY CODE ###

from collections import deque
n,m = map(int,input().split())
li = [list(map(int,input().split())) for _ in range(m)]
g = [[] for _ in range(n)]
l = [0 for _ in range(n)]
seen = [0 for _ in range(n)]

for x,y in li:
    x -= 1
    y -= 1
    g[x].append(y)
    g[y].append(x)

def bfs():
    que = deque([])
    l[0] = 0
    seen[0] = 1
    for i in g[0]: 
        que.append((i,0))
    while que:
        a,b = que.popleft()
        seen[a] = 1
        if not l[a]:l[a] = b+1
        for i in g[a]:
            if i != b and not l[i]:
                
                que.append((i,a))

bfs()
if all(seen):
    print('Yes')
    for i in l[1:]:
        print(i)
else:
    print('No')

### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())
li = [list(map(int,input().split())) for _ in range(m)]
g = [[] for _ in range(n)]
l = [float('inf')] * n

for x,y in li:
    x -= 1
    y -= 1
    g[x].append(y)
    g[y].append(x)

def bfs():
    que = deque()
    l[0] = 0
    que.append(0)
    while que:
        a = que.popleft()
        for i in g[a]:
            if l[i] != float('inf'):continue
            l[i] = a
            que.append(i)
bfs()
for i in l:
    if i == float('inf'):
        print('No')
        exit()
print('Yes')
for i in l[1:]:
    print(i+1)
### BUGGY CODE ###

import numpy as np

N=int(input())
A=list(map(int,input().split()))
mod=10**9+7
ans=0

ans = sum([x*y % mod for x in A[0:N-1] for y in A[A.index(x)+1:N]])%mod

print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
aa = 0
b = 0
for i in range(n):
    aa += a[i] ** 2  
    b += a[i]
    #aa %= mod
    #b %= mod
print((b ** 2 - aa)//2%mod)
### BUGGY CODE ###

N, Y = map(int, input().split())
# i: man, j: gosen, k: sen
output_flag=0
for i in range(0, N+1):
    while output_flag==0:
        for j in range(0, N+1-i):
            k = N-i-j
            if 10000*i+5000*j+1000*k==Y:
                print(i, j, k)
                output_flag=1
                break
    if output_flag==1:
        break
if output_flag==0:
    print(-1, -1, -1)

### FIXED CODE ###

N, Y = map(int, input().split())
man = -1
gosen = -1
sen = -1
for i in range(0, N+1):
    for j in range(0, N+1-i):
        k = N-i-j
        total = 10000*i+5000*j+1000*k
        if total==Y:
            man = i
            gosen = j
            sen = k
print(man, gosen, sen)
### BUGGY CODE ###

n = input()
b = input().split()
a = [int(b[i]) for i in range(len(b))]


def check(a):
  sum = 0
  for i in range(len(a)):
    if(i == 0):
      if(a[i] == 0):
        return (i, +1)
      sum += a[0]
      continue
    if(sum > 0):
      sum += a[i]
      if(a[i] == 0 or sum >= 0):
        return (i, -1)

    elif(sum < 0):
      sum += a[i]
      if(a[i] == 0 or sum <= 0):
        return (i, +1)
    else:
      if(a[i-1] > 0):
        return (i, -1)
      else:
        return (i, +1)



  return True

ans = 0
while(True):
  c = check(a)
  if(c == True):
    break

  a[c[0]] += c[1]

  ans += 1



print(ans)

### FIXED CODE ###


def check1(a):
  sum = 0
  ans = 0
  for i in range(len(a)):
    if(i % 2 == 0):
      sum += a[i]
      if(sum >= 0):
        a[i] -= abs(sum)+1
        ans += abs(sum)+1
        sum -= abs(sum)+1
    else:
      sum += a[i]
      if(sum <= 0):
        a[i] += abs(sum)+1
        ans += abs(sum)+1
        sum += abs(sum)+1
  return ans

def check2(a):
  sum = 0
  ans = 0
  for i in range(len(a)):
    if(i % 2 == 0):
      sum += a[i]
      if(sum <= 0):
        a[i] += abs(sum)+1
        ans += abs(sum)+1
        sum += abs(sum)+1
    else:
      sum += a[i]
      if(sum >= 0):
        a[i] -= abs(sum)+1
        ans += abs(sum)+1
        sum -= abs(sum)+1
  return ans



n = input()
b = input().split()
a = [int(b[i]) for i in range(len(b))]
a2 = list(a)

ans1 = check1(a)
ans2 = check2(a2)


print(ans1) if(ans1<ans2) else print(ans2)
### BUGGY CODE ###

n = int(input())
a = map(int, input().split())
multi = 1

for i in a:
  multi *= i

if multi > pow(10,18):
  print("-1")
else:
  print(multi)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
multi = 1

for i in a:
  multi *= i
  if multi > pow(10,18):
    break
if multi > pow(10,18):
  print("-1")
else:
  print(multi)
### BUGGY CODE ###

def resolve():
    s = list(input())
    n = len(s)
    #s_cu = [] 
    counter = [0] * 2019

    counter[0] += 1
    temp=""
    for i in range(1, n+1):
        c=s.pop()
        temp = c + (temp if i != 1 else "")
        #s_cu.append(temp)
        counter[int(temp) % 2019] += 1

    ans = 0
    for i in counter:
        ans += (i * (i - 1)) // 2

    print(ans)
resolve()

### FIXED CODE ###

#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
def resolve():
    S=input()
    n=len(S)
    
    S2=[0]*n
    digit=0
    for i in range(n-1,-1,-1):
        s=int(S[i])
        S2[i]=(s*pow(10,digit,2019))%2019
        digit+=1
    #print(S2)

    S3=[0]*n;subsum=0
    for j,s2 in enumerate(S2):
        subsum+=s2;subsum%=2019;S3[j]=subsum
    S3.append(0)
    #print(S3)

    from collections import Counter
    c=Counter(S3).values()
    ans=0
    for k in c:
        if k>1:
            ans+=(k*(k-1))//2
    print(ans)
#%%submit!
resolve()