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

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)

for i in range(M):
    A[0] //= 2
    A.sort(reverse=True)

print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
a = []
for i in A:
    heapq.heappush(a, -i)

for i in range(M):
    heapq.heappush(a, -(-heapq.heappop(a) // 2))

print(-sum(a))
### BUGGY CODE ###

mod = 10**9 + 7
n = int(input())
nums = list(map(int, input().split(" ")))

ans = 0

for i in range(n):
    for j in range(i+1, n):
        ans += (nums[i] * nums[j]) % mod

print(ans % mod)

### FIXED CODE ###

mod = 10**9 + 7
n = int(input())
nums = list(map(int, input().split(" ")))

ans = 0

ans = sum(nums) * sum(nums) - sum([num*num for num in nums])

print((ans // 2) % mod)
### BUGGY CODE ###

N = int(input())
Stemp = str(input())
S = []
for i in range(N):
  temp = int(Stemp[i])
  S.append(temp)
#print(S)
#i桁目までみて、1文字目がx、2文字目がy、3文字目がzのがあるか
dp = [[0]*10 for _ in range(N+1)]
dpp = [[[0 for _ in range(10)] for _ in range(10)] for _ in range(N+1)]
dppp = [[[[0]*10 for _ in range(10)] for _ in range(10)] for _ in range(N+1)]

for i in range(N):
  now = S[i] #i桁目 1index
  #dp[i+1][now] = 1
  for x in range(10):
    if x == now:
      dp[i+1][x] = 1
      #print(dp[i+1][x])
    else:
      dp[i+1][x] = max(dp[i][x],dp[i+1][x])
    for y in range(10):
      if y == now and dp[i][x] == 1:
        dpp[i+1][x][y] = 1
      else:
        dpp[i+1][x][y] = max(dpp[i][x][y],dpp[i+1][x][y])
      for z in range(10):
        if z == now and dpp[i][x][y] == 1:
          dppp[i+1][x][y][z] = 1
        else:
          dppp[i+1][x][y][z] = max(dppp[i][x][y][z],dppp[i+1][x][y][z])
#print(dp)
#print(dpp)
#print(dppp)
ans = 0
for i in range(10):
  for j in range(10):
    for k in range(10):
      ans += dppp[N][i][j][k]
        
print(ans)       

### FIXED CODE ###

N = int(input())
Stemp = str(input())
S = []
for i in range(N):
  temp = int(Stemp[i])
  S.append(temp)
ans = set([])
L = [[] for _ in range(10)]
for i in range(N):
  L[S[i]].append(i)
#print(L)
for v in range(1000):
  a = v//100
  b = (v-a*100)//10
  c = v-a*100-b*10
  if not L[a]:
    continue
  left = min(L[a])
  Flag = False
  for x in L[b]:
    if x > left:
      mid = x
      Flag = True
      break
  if not Flag:
    continue
  Flag = False
  for y in L[c]:
    if y > mid:
      right = y
      Flag = True
      break
  if not Flag:
    continue
  ans.add(v)
  #print(v,left,mid,right)
print(len(ans))
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(x) for x in input().split()]

inf = 10 ** 5

Cost = [inf] * N
Cost[0] = 0

for i in range(1, N):
    tmp = [Cost[i - k] + abs(h[i] - h[i - k]) if i - k >= 0 else inf for k in range(1,K + 1)]
    Cost[i] = min(tmp)

print(Cost[-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(x) for x in input().split()]

Cost = [0] * N
Cost[0] = 0

for i in range(1, N):
    tmp = [Cost[k] + abs(h[i] - h[k]) for k in range(max(0, i - K),i)]
    Cost[i] = min(tmp)

print(Cost[-1])
### BUGGY CODE ###

n = int(input())
power = 1
for i in range(1,n+1):
    power *= i
print(power % (10**9 + 7))


### FIXED CODE ###

n = int(input())
power = 1
for i in range(1,n+1):
    power = (i*power)%(10**9+7)
print(power)
### BUGGY CODE ###

N=int(input())
listL=list(map(int,input().split()))
listL.sort()
ans=0
for i in range(0,N-2):
  for k in range(i+1,N-1):
    for t in range(k+1,N):
      IF=listL[i]+listL[k]-listL[t]
      if IF>0:
        ans+=1
      else:
        break
print(ans)

### FIXED CODE ###

from bisect import bisect, bisect_left
 
N=int(input())
L=list(map(int,input().split()))
L.sort()
 
ans = 0
for i in range(N-2):
  a=L[i]
  for k in range(i+1,N-1):
    b=L[k]
    t=bisect_left(L,a+b)
    ans+=t-k-1
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
s = n % k
t = s
for _ in range(t):
  if abs(s-k)<s:
    s = abs(s-k)
print(s)

### FIXED CODE ###

n,k = map(int,input().split())
s = n % k
list = [s]
for _ in range(s):
  if abs(s-k) in list:
    break
  elif abs(s-k)<s:
    list.append(abs(s-k))
print(min(list))
### BUGGY CODE ###

s = input()
l = len(s)
cnt = 0

for i in range(l):
    for j in range(i, l):
        if int(s[i:j + 1])%2019 == 0 and int(s[i:j + 1]) != 0:
            cnt +=1

print(cnt)

### FIXED CODE ###

s = input()
mod = 2019
l = [0]*mod
l[0] = 1 #余りが0の場合が1足りないので補う
ans = 0
r = 0
t = 1

for i in s[::-1]:
    r += int(i)*t
    r %= mod # 余りをrに代入してしまっても、後の計算に支障が無い。
    l[r] += 1
    t *= 10
    t %= mod # t *= 10を使用しても、ここの余りを使用しても、r%modの答えは変わらない。

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

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

k, n = map(int, input().split())
a = list(map(int, input().split()))
ans = []
ans.append(max(a) - min(a))
for i in range(n):
    if a[i] > k // 2:
        a[i] = (k - a[i]) * -1
    ans.append(max(a) - min(a)) 
print(min(ans))

### FIXED CODE ###

k, n = map(int, input().split())
a = list(map(int, input().split()))
l = [a[0] + k - a[-1]]
for i in range(1, n):
    l.append(a[i] - a[i - 1])
print(sum(l) - max(l))
### BUGGY CODE ###

import math
#N = int(input())
N, M =  map(int,input().split())
#W =list(map(int,input().split()))
a = [(int(input())) for i in range(M)]


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

def stair_count(start,end):
    #print(start,end)
    aida = end - start
    total = 1
    i = aida-1
    #print("aida/2={}".format(aida/2))
    kazu = 1
    while (aida%2==0 and i >= (aida/2)) or (aida%2!=0 and i>(aida/2)):
        total += comb(i,kazu)
        kazu += 1
        i -= 1
    return total

start = 0
answer = 1
for i in range(1,N):
    #print("i={}".format(i))
    if i in a:
        if i == start:
            print(0)
            exit()
        else:
            answer = (answer * stair_count(start, i-1))
            start = i+1
    elif i == N-1:
        answer = (answer * stair_count(start, N))
    else:
        continue
    #print("answer={}".format(answer))
print(answer%1000000007)


### FIXED CODE ###

#N = int(input())
N, M =  map(int,input().split())
#W =list(map(int,input().split()))
a = [(int(input())) for i in range(M)]

import sys

sys.setrecursionlimit(100000)
memo  =[-1]*(N+2)
def stair_count(n):
    if memo[n]!= -1:
        return memo[n]
    if n==0 or n==1:
        memo[n] =1
        return memo[n]
    memo[n] = stair_count(n-1) + stair_count(n-2)
    return memo[n]

start = 0
answer = 1
for i in a:
        if i == start:
            print(0)
            exit()
        else:
            n = i-1-start
            answer = (answer * stair_count(n))
            start = i+1
n = N -start
answer = (answer * stair_count(n))
print(answer%1000000007)
### BUGGY CODE ###

N = int(input())

sche = [[0,0] for i in range(N)]

for i in range(N):
    tmp_a, tmp_b = map(int, input().split())
    sche[i][0] = tmp_a
    sche[i][1] = tmp_b



def search_lms(N, sche, now):
    sub_time = 10000000000
    num = 0
    for i in range(len(sche)):
        if sub_time > sche[i][1]:
            sub_time = sche[i][1]
            num = i
    return num
        #差の最小値を見つける

now = 0
tmp = 0
for i in range(N):
    tmp = search_lms(N, sche, now)
    if now + sche[tmp][0] > sche[tmp][1]:
        print("No")
        exit()
    now += sche[tmp][0]
    sche.pop(tmp)

print("Yes")

### FIXED CODE ###

N = int(input())
work = [list(map(int, input().split())) for i in range(N)]

work = sorted(work, key = lambda x: x[1])

time = 0
for i in range(N):
    time += work[i][0]
    if time > work[i][1]:
        print("No")
        exit()
print("Yes")
### BUGGY CODE ###

c = input()
s = []
for i in c:
    s.append(i)

list_a = []
list_z = []

while "A" in s:
    list_a.append(s.index("A"))
    s[s.index("A")] = "b"

while "Z" in s:
    list_z.append(s.index("Z"))
    s[s.index("Z")] = "v"

answer = list_z[-1] - list_a[0] + 1
print(answer)
 

### FIXED CODE ###

S = input()
print(S.rfind("Z") - S.find("A")+1)
### BUGGY CODE ###

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

a_types = set(A)

count_dict = {}
for each in a_types:
    count_dict[each] = A.count(each)

all_types = 0
for value in count_dict.values():
    all_types += value * (value - 1) // 2

result_dict = {}
for each in a_types:
    result_dict[each] = int(all_types - count_dict[each] + 1)

for a in A:
    print(result_dict[a])

### FIXED CODE ###

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

c = [0]*n

for i in range(n):
    c[a[i]-1] = c[a[i]-1] + 1
    
total = 0
for x in c:
    total = total + x*(x-1)//2

for i in range(n):
    print(total - c[a[i]-1] + 1)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
count = 0
for i in range(N):
    if A[i] == min(A[0:i+1]):
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
count = 0
min_number = A[0]
for i in range(N):
    if A[i] <= min_number:
        min_number = A[i]
        count += 1
print(count)
### BUGGY CODE ###

N = int(input())
S = input()

dp = [[0] * (N+1) for i in range(N+1)]

for i in range(N-1,-1,-1):
    for j in range(N-1,-1,-1):
        # print(i,j)
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1 

# print(dp)
ans = 0
for i in range(N):
    for j in range(N):
       val = min(abs(i-j),dp[i][j])
       ans = max(val,ans)

print(ans) 

### FIXED CODE ###

N = int(input())
S = input()

dp = [[0] * (N+1) for i in range(N+1)]

for i in range(N-1,-1,-1):
    for j in range(N-1,-1,-1):
        # print(i,j)
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1 

# print(dp)
ans = 0
for i in range(N):
    for j in range(N):
       val = min(abs(i-j),dp[i][j])
       ans = max(val,ans)

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

import sys
input = lambda: sys.stdin.readline().rstrip()
 
x=int(input())
a=1
while True:
    for b in range(a + 1):
        if a**5+b**5==x:
            print(a,-b)
            sys.exit()
        elif a**5-b**5==x:
            print(a,b)
            sys.exit()
        else:
            a+=1



### FIXED CODE ###

import sys
input = sys.stdin.readline

x = int(input())
a = 1
while True:
    for b in range(0, a):
        if a**5 - b**5 == x:
            print(a, b)
            sys.exit()
        if a**5 + b**5 == x:
            print(a, -b)
            sys.exit()
    a += 1
### BUGGY CODE ###

n=int(input())
k=int(input())
count=0
for i in range(10**(k-1),n+1):
  s=str(i)
  n=len(s)
  if k>1:
      if '0' not in s:
          #print(s)
          if n==k:
              count+=1
      else:
          if n-s.count('0')==k:
              count+=1
  else:
      if n-s.count('0')==k:
          count+=1
       
print(count)
        

### FIXED CODE ###

N = int(input())
K = int(input())

strN = str(N)
maxD = len(strN)

dp = [[[0]*(K+1) for j in range(2)] for i in range(maxD+1)]
dp[0][0][0] = 1
for d, Nd in enumerate(strN):
    Nd = int(Nd)
    for isLeN in range(2):
        for m in range(K+1):
            x = 0
            if not isLeN and x > Nd: continue
            isLeN2 = isLeN or x < Nd
            dp[d+1][isLeN2][m] += dp[d][isLeN][m]
            for x in range(1, 10):
                if not isLeN and x > Nd: continue
                isLeN2 = isLeN or x < Nd
                m2 = m+1
                if m2 > K: continue
                dp[d+1][isLeN2][m2] += dp[d][isLeN][m]
#    print(d+1, Nd, dp[d+1])

#print(dp[-1])
print(dp[-1][0][K]+dp[-1][1][K])
### BUGGY CODE ###

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

kitai = [None]*(1000+1)
for i in range(1, 1001):
    kitai[i] = (0.5*i*(i+1))/i

ans = 0
for i in range(0, N-K+1):
    temp = 0
    for j in range(K):
        temp += kitai[P[i+j]]
    if ans < temp:
        ans = temp

print(ans)


### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
P = list(map(int, input().split()))

kitai = [None]*(1001)
for i in range(1, 1001):
    kitai[i] = (0.5*i*(i+1))/i

ruiseki = P.copy()
ruiseki[K-1] = sum(ruiseki[0:K])
for i in range(K, N):
    ruiseki[i] = ruiseki[i-1]+P[i]-P[i-K]

ind = np.array(ruiseki).argmax()
temp = P[ind-K+1:ind+1]
ans = 0
for t in temp:
    ans+=kitai[t]
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
line = list(input().split())
setted_line = list(set(line))
origin_num = len(setted_line) 
pairs = {}
for i in range(origin_num):
  count = line.count(setted_line[i])
  pairs[setted_line[i]] = count
sorted_pairs = sorted(pairs.items(), key = lambda x:x[1])
answer = 0
gap = origin_num - k
if gap <= 0:
  answer = 0
else:
   for j in range(gap):
    answer += sorted_pairs[j][1]
print(answer)

### FIXED CODE ###

import collections
n,k = map(int,input().split())
line = list(input().split())
c = collections.Counter(line)
answer = 0
if k > len(c):
  answer = 0
else:
  gap = len(c) - k
  sorted_c = list(sorted(c.items(),key = lambda x:x[1]))
  for i in range(gap):
    answer += int(sorted_c[i][1])
print(answer)
### BUGGY CODE ###

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

sum_all = 0
p = 1
for i in range(60):
    ones = 0
    zeros = 0

    x = 1 << i
    for a in A:
        if a & x:
            ones += 1
        else:
            zeros += 1

    sum_all += p * ones * zeros % MOD
    p *= 2 % MOD


print(sum_all % MOD)

### FIXED CODE ###

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

sum_all = 0
p = 1
for i in range(60):
    ones = 0
    zeros = 0

    x = 1 << i
    for a in A:
        if a & x:
            ones += 1
        else:
            zeros += 1

    sum_all += p * ones * zeros % MOD
    p *= 2 % MOD


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

#D - String Formation
S = list(str(input()))
Q = int(input())
q = [input().split() for i in range(Q)]

#print(S)
#print(q)

for i in range(Q):
    tmp1 = ""
    if q[i][0] == '1':
        S = S[::-1]
       # tmp1 = S[0]
       # S[0] = S[-1]
       # S[-1] = tmp1
    else:
        if q[i][1] == "1":
            S.insert(0,q[i][2])
        else:
            S.append(q[i][2])
ans = ''.join(S)
print(ans)

### FIXED CODE ###

#D - String Formation
S=input()
Q=int(input())
query=[]
for _ in range(Q):
    query.append(input().split())

flag = True
t=""
u=""

for i in query:
    if i[0]=="1":
        u,t=t,u
        flag = not flag
#        S=S[::-1]
    else:
        if i[1]=="1":
            t+=i[2]
        else:
            u+=i[2]
if flag:
    print(t[::-1]+S+u)
else:
    print(t[::-1]+S[::-1]+u)
### BUGGY CODE ###

K = int(input())
N = len(input())

mod = 10 ** 9 + 7
comb_i = pow(26, K, mod)
ans = comb_i
for i in range(1, K + 1):
  comb_i = (comb_i * (N - 1 + i)) % mod
  comb_i = (comb_i * 25) % mod
  comb_i = (comb_i * pow(i, -1, mod)) % mod
  comb_i = (comb_i * pow(26, -1, mod)) % mod
  ans = (ans + comb_i) % mod
  
print(ans)

### FIXED CODE ###

K = int(input())
N = len(input())

mod = 10 ** 9 + 7
div = pow(26, -1, mod)
comb_i = pow(26, K, mod)
ans = comb_i
for i in range(1, K + 1):
  comb_i = (comb_i * (N - 1 + i) * pow(i, -1, mod)) % mod
  comb_i = (comb_i * 25 * div) % mod
  ans = (ans + comb_i) % mod
  
print(ans)
### BUGGY CODE ###

import numpy as np

k=int(input())
ans=0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans+=np.gcd(a,np.gcd(b,c))
print(ans)

### FIXED CODE ###

import math

k=int(input())
ans=0
for a in range(1,k+1):
    for b in range(1,a+1):
        for c in range(1,b+1):
            if (a==b) and (b==c):
                ans+=math.gcd(a,math.gcd(b,c))
            if ((a!=b) and (b==c)) or ((a==b) and (b!=c)):
                ans+=3*math.gcd(a,math.gcd(b,c))
            if ((a!=b) and (b!=c)):
                ans+=6*math.gcd(a,math.gcd(b,c))
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 標準入力を取得
N = int(input())

# 求解処理
F = [0 for n in range(N + 1)]
for n in range(1, N + 1):
    for i in range(1, N // n + 1):
        F[n * i] += 1
            
ans = sum([n * F[n] for n in range(N + 1)])

# 結果出力
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 標準入力を取得
N = int(input())

def g(N: int) -> int:
    return int(N * (N + 1) / 2)

# 求解処理
ans = 0
for n in range(1, N + 1):
    ans += n * g(N // n)
            
# 結果出力
print(ans)
### BUGGY CODE ###

# 各々の要素が何番目に何回数えられるかを考える。
import sys

input = sys.stdin.buffer.readline

n = int(input())
C = list(map(int, input().split()))
C.sort(reverse=True)
mod = 10 ** 9 + 7
N = n + 5
bikkuri = [0] * N
bikkuri[0] = 1
gyaku = [0] * N
for i in range(1, N):
    bikkuri[i] = (i * bikkuri[i - 1]) % mod
gyaku[N - 1] = pow(bikkuri[N - 1], mod - 2, mod)
for i in range(N - 1, 0, -1):
    gyaku[i - 1] = (gyaku[i] * i) % mod


def comb(n, r):
    if r < 0 or n - r < 0:
        return 0
    return (bikkuri[n] * gyaku[r] * gyaku[n - r]) % mod


ans = 0
for i in range(n):
    for k in range(n + 1):
        for a in range(i + 1):
            ans += comb(i, a) * (a + 1) * C[i] * comb(n - (i + 1), k - (a + 1))
            ans %= mod
ans *= pow(2, n, mod)
ans %= mod
print(ans)


### FIXED CODE ###

# 各々の要素が何番目に何回数えられるかを考える。
import sys

input = sys.stdin.buffer.readline

n = int(input())
C = list(map(int, input().split()))
C.sort(reverse=True)
mod = 10 ** 9 + 7
N = n + 5
bikkuri = [0] * N
bikkuri[0] = 1
gyaku = [0] * N
for i in range(1, N):
    bikkuri[i] = (i * bikkuri[i - 1]) % mod
gyaku[N - 1] = pow(bikkuri[N - 1], mod - 2, mod)
for i in range(N - 1, -1, -1):
    gyaku[i - 1] = (gyaku[i] * i) % mod


def comb(n, r):
    if r < 0 or n - r < 0:
        return 0
    return (bikkuri[n] * gyaku[r] * gyaku[n - r]) % mod


ans = 0
for i in range(n):
    ans += (i + 2) * C[i] * pow(2, 2 * n - 2, mod)
    ans %= mod
print(ans)
### BUGGY CODE ###

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7

dp = [0] * (1 << n)
dp[0] = 1

# 配るDP
for bit in range((1 << n) - 1):
    i = bin(bit).count('1')
    for j in range(n):
        if a[i][j] and ((bit >> j) & 1) ^ 1:
            newbit = bit | (1 << j)
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[(1 << n) - 1])


### FIXED CODE ###

mod = 10**9+7
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
dp = [0]*(1 << n)
dp[0] = 1
for i in range(1, 1 << n):
    k = bin(i).count("1")
    for j in range(n):
        if i >> j & 1 and a[k-1][j]:
            dp[i] += dp[i ^ (1 << j)]
    dp[i] %= mod
print(dp[(1 << n)-1])
### BUGGY CODE ###

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

u = set(s)
m = 0
ans = []

for i in u:
    mae = len(s)
    s = [j for j in s if j != i]
    ato = len(s)
    num = mae - ato

    if num > m:
        ans = [i]
        m = num
    elif num == m:
        ans.append(i)

ans.sort()

print('\n'.join(map(str, ans)))
#for i in range(len(ans)):
#    print(ans[i])

        


### FIXED CODE ###

import collections

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

c = collections.Counter(s)
common = c.most_common()

count = common[0][1]
ans = []
for i in common:
  if i[1] == count:
    ans.append(i[0])
  else:
    break
ans.sort()
print(*ans,sep='\n')
### BUGGY CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance


N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
S, T = map(int, input().split())
G2 = [[] for _ in range(N+1)]


def dfs(nodes, v):
    if nodes[0] != -1:
        if (v, 1) in G2[nodes[0]]:
            return
        G2[nodes[0]].append((v, 1))
    for u in G[v]:
        dfs(nodes[1:] + [v], u)


dfs([-1] * 3, S)
dist = dijkstra(G2, N+1, S)
print(dist[T] if dist[T] != float('inf') else -1)


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
S, T = map(int, input().split())
queue = deque()
queue.append((S, 0))
visited = [[False] * 3 for _ in range(N+1)]
while queue:
    u, d = queue.popleft()
    if visited[u][d % 3]:
        continue
    visited[u][d % 3] = True
    if d % 3 == 0 and u == T:
        print(d // 3)
        exit()
    for v in G[u]:
        queue.append((v, d+1))
print(-1)
### BUGGY CODE ###

n = input()
 
A = map(int, raw_input().split())
  
q = input()
  
M = map(int, raw_input().split())
 
def solve(i, m):
  if m == 0:
    return True
  if i >= n:
    return False
  res = solve(i+1, m) or solve(i+1, m - A[i])
  return res
 
 
for m in M:
  if solve(0,m):
    print "yes"
  else:
    print "no"

### FIXED CODE ###

n = input()

A = map(int, raw_input().split())
   
q = input()
   
M = map(int, raw_input().split())
  
def solve(i, m):
  if m == 0:
    return True
  if i >= n or m > sum(A):
    return False
  res = solve(i+1, m) or solve(i+1, m - A[i])
  return res
  
  
for m in M:
  if solve(0,m):
    print "yes"
  else:
    print "no"
### BUGGY CODE ###

a,b=map(int,input().split())
x=a
for i in range(a+1,b+1):
    x^=i
print(x)

### FIXED CODE ###

a,b=map(int,input().split())
xa=0
if a==b:
    print(a)
elif b-a<4:
    x=0
    for i in range(a,b+1):
        x^=i
    print(x)
else:
    if a%4:
        for i in range(4-a%4):
            xa^=a+i
    xb=0
    if b%4 != 3:
        for i in reversed(range(b%4+1)):
            xb^=b-i
    print(xa^xb)
### BUGGY CODE ###

N = int(input())
C = [0] * N
mod = 10 ** 9 + 7
dic = [ [ ] for _ in range(2*(10**5)+1)]
for i in range(N):
    C[i] = int(input())
    if i > 0 and C[i] == C[i-1]:
        continue
    dic[C[i]].append(i)

dp = [0] * N
dp[0] = 1
for i in range(1,N):
    dp[i] = dp[i-1] % mod
    if C[i] == C[i-1]:
        continue
    for prev in dic[C[i]]:
        if prev < i:
            if prev > 0:
                dp[i] += dp[prev-1]
            else:
                dp[i] += 1
        dp[i] %= mod

print(dp[N-1] % mod)

### FIXED CODE ###

N = int(input())
C = [0] * N
mod = 10 ** 9 + 7
dic = [-1]*(2*(10**5)+1)
prevIdx = [0] * N
for i in range(N):
    C[i] = int(input())
    if i > 0 and C[i] == C[i-1]:
        continue
    prevIdx[i] = dic[C[i]]
    dic[C[i]] = i

dp = [0] * N
dp[0] = 1
acc = [0] * N
acc[0] = 1
for i in range(1,N):
    dp[i] = dp[i-1] % mod
    if C[i] == C[i-1] or prevIdx[i] == -1:
        acc[i] = dp[i-1]
        continue
    
    dp[i] += acc[prevIdx[i]]
    acc[i] = acc[prevIdx[i]] + dp[i-1]
    acc[i] %= mod
    dp[i] %= mod

print(dp[N-1] % mod)
### BUGGY CODE ###

def main():
    s = input()
    # si = tuple(int(c) for c in s)  # integers of one digit
    # ms = {2019 * x for x in range(10 ** 200000 - 1 // 2019)}
    ans = 0
    lg = len(s)
    # to slice till the last letter, +1 is needed.
    for i in range(lg + 1):
        for j in range(i + 4, lg + 1):
            j2 = j
            # 2019 = 673 * 3
            # if sum(si[i:j2]) % 3 != 0:
            #     continue
            if int(s[i:j2]) % 2019 == 0:
                ans += 1

    return ans


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


### FIXED CODE ###

# https://www.hamayanhamayan.com/entry/2020/04/26/232032
s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力