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

import itertools
n = int(input())
v = list(map(int,input().split()))
values = []
for root in itertools.permutations(v):
  pot = root[0]
  for i in range(n - 1):
    pot = (pot + root[i + 1]) / 2
    if i == n - 2:
      values.append(pot)
print(max(values))

### FIXED CODE ###

n = int(input())
v = list(map(int,input().split()))
values = []
v = sorted(v)
pot = v[0]
for i in range(n - 1):
  pot = (pot + v[i + 1]) / 2
  if i == n - 2:
    values.append(pot)
print(max(values))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

ruiseki=1
for i in range(n):
  ruiseki=ruiseki*a[i]

if setwise_coprime(a)==1:
  for i in range(n):
    num=math.gcd(a[i],(ruiseki//a[i])%a[i])
    if num!=1:
      print("setwise coprime")
      sys.exit()
  print("pairwise coprime")
else:
  print("not coprime")
  sys.exit()


        












### FIXED CODE ###

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

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

#エラストテネスのふるい
def create_sieve(n):
  sieve=[0]*(n+1)
  for i in range(2,n+1):
    if sieve[i]==0:
      for j in range(i*i,n+1,i):
        sieve[j]=i
  return sieve

#高速素因数分解
def fast_factorization(n, sieve):
  prime={}
  while n>1:
    p=sieve[n]
    #nが素数の場合
    if p==0:
      prime[n]=prime.get(n,0)+1
      break
    #nが素数ではない場合
    else:
      prime[p]=prime.get(p,0)+1
      n=n//p
  return prime

check=set()
if setwise_coprime(a)==1:
  #素因数のダブリをcheck
  sieve=create_sieve(10**6)
  for i in range(n):
    if a[i]!=1:
      s=fast_factorization(a[i], sieve)
      for i in s:
        if i in check:
          print("setwise coprime")
          sys.exit()
        else:
          check.add(i)
  print("pairwise coprime")    
else:
  print("not coprime")
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split(" ")))
B = list(map(int, input().split(" ")))
C = list(map(int, input().split(" ")))
m = 0

A.sort()
B.sort()
C.sort(reverse=True)

for j in B:
    for i in range(N):
        if A[i] >= j:
            break
        if A[N-1] < j:
            i = N
    for k in range(N):
        if j >= C[k]:
            break
        if j < C[N-1]:
            k = N
    m =  m + i * k

print(m)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
 
A.sort()
B.sort()
C.sort()
C.reverse()
 
ans = 0
ai = 0
ci = N-1
for b in B:
    while ai < N and A[ai] < b:
        ai += 1
    while ci >= 0 and C[ci] <= b:
        ci -= 1
    ans += ai * (ci+1)
 
print(ans)
### BUGGY CODE ###

import sys
K=int(input())
L=9*K
if L%7==0:
  L = L//7
for i in range(1,K+1):
  if 10 ** i % L == 1:
    print(i)
    sys.exit()
print(-1)


### FIXED CODE ###

import sys
K=int(input())
L=9*K
if L%7==0:
  L = L//7
n = 1
for i in range(1,K+1):
  n = n * 10 % L
  if n == 1:
    print(i)
    sys.exit()
print(-1)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [[int(i) for i in input().split()] for i in range(m)]

for i in range(m):
        a = sorted(a)
        bc_temp = bc[i]
        for j in range(bc_temp[0]):
                if a[j] < bc_temp[1]:
                        a[j] = bc_temp[1]
                elif a[j] > bc_temp[1]:
                        break

print(sum(a)) 

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [[int(i) for i in input().split()] for i in range(m)]

bc.sort(key = lambda x:x[1], reverse = True)

a.sort()

a_count = 0
for b, c in bc:
        if c > a[a_count]:
                for i in range(b):
                        if c > a[a_count]:
                                a[a_count] = c
                                a_count += 1    
                        else:
                                break
                        if a_count == n:
                                        break

        else:
                break
        if a_count == n:
                break        

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

#!/usr/bin/env pypy3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import math,sys

n = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split()))
#n = int(input())
#a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
acc = a[0]
for i in range(n):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            #print(i)
            for j in range(i+i,LIMIT+1,i):
                #print(i,j)
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
def factrial(N):
     ret = []
     while minPrime[N] != N:
         ret.append(minPrime[N])
         N = N//minPrime[N]
     if N != 1:
         ret.append(N)
     return ret

judge = set([])
pc = True

pairwise = True
p = set() #all prime

for e in a:
    if not pairwise:
        break
    f = set(factrial(e))
    if judge & f != set():
        pc = False
    #     #pairwise = False
    #     print("setwise coprime")
    #     exit(0)
    judge = judge | f
# for i in a:
#     if not pc:
#         break
#     asf = set(factrial(i))

#     if judge & asf != set():
#         pc = False
#     judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")


### FIXED CODE ###

import math
from collections import defaultdict
pc = True
n = int(input())
a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
class Sieve_of_Eratosthenes:
    def __init__(self, N):
        self.sieve = [-1] * (N+1)
 
        for i in range(2,N+1):
            if self.sieve[i] == -1:
                for j in range(1,1+N//i):
                    self.sieve[i*j] = i
 
    def isprime(self, num):
        if num <= 1:
            return False
        else:
            return self.sieve[num] == num
 
    def factorization(self, num):
        ret = set([])
        while num != 1:
            div = self.sieve[num]
            ret.add(div)
            num //= div
        return ret
 
sofe = Sieve_of_Eratosthenes(M)
ddic = defaultdict()
judge = set([])
 
for i in a:
    if not pc:
        break
    asf = sofe.factorization(i)
    
    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
"""
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
max_A = max(A)
bit = bin(K)
if max_A > K:
    bit = bin(max_A)"""
max_f = 0
#for d in range(1,len(bit))[::-1]:
for d in range(41,-2,-1):
    #d=d-2
    if (d != -1 and not (K & 1 << d)):
        continue
    f=0
    #for e in range(2,len(bit))[::-1]:
    for e in range(41,-1,-1):
        #e=e-2
        mask = 1<<e
        num=0
        for a in A:
            if a&mask:
                num+=1
        n_num = N - num
        if e>d:
            if K&mask:
                f += mask*n_num
            else:
                f += mask*num
        elif e==d:
            f += mask*num
        else:
            f += mask*max(n_num,num)
    max_f = max(f,max_f)
print(max_f)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
"""
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
max_A = max(A)
bit = bin(K)
if max_A > K:
    bit = bin(max_A)"""
max_f = 0
#for d in range(1,len(bit))[::-1]:
for d in range(41,-2,-1):
    #d=d-2
    if (d != -1 and not (K & 1 << d)):
        continue
    f=0
    #for e in range(2,len(bit))[::-1]:
    for e in range(41,-1,-1):
        #e=e-2
        mask = 1<<e
        num=0
        for a in A:
            if a&mask:
                num+=1
        n_num = N - num
        if e>d:
            if K&mask:
                f += mask*n_num
            else:
                f += mask*num
        elif e==d:
            f += mask*num
        else:
            f += mask*max(n_num,num)
    max_f = max(f,max_f)
print(max_f)
### BUGGY CODE ###

N = int(input())
T, A = [0]*N, [0]*N

for i in range(N):
    T[i], A[i] = map(int, input().split())
ans = T[0]+A[0]

for i in range(N-1):
    for j in range(10**18):
        if (ans+j)%(T[i+1]+A[i+1])==0:
            if (ans+j)*T[i+1]/(T[i+1]+A[i+1])>=ans*T[i]/(T[i]+A[i]) and (ans+j)*A[i+1]/(T[i+1]+A[i+1])>=ans*A[i]/(T[i]+A[i]):
                ans += j
                break

print(ans)


### FIXED CODE ###

N = int(input())
T, A = [0]*N, [0]*N

for i in range(N):
    T[i], A[i] = map(int, input().split())
t = a = 1
for i in range(N):
    n = max(-(-t//T[i]), -(-a//A[i]))
    t = n*T[i]
    a = n*A[i]
print(t+a)
### BUGGY CODE ###

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

count = [0 for i in range(q)]

list_2 = [i for i in range(q)]
list_3 = [i for i in range(q)]
for i in range(q) :

    a = q_con[i][0] - 1
    b = q_con[i][1] 
    list_2[i] = s[:][a:b]
    list_3[i] = list_2[:][i].replace("AC","")
    p = (len(list_2[i])-len(list_3[i]))/2
    print("{}".format(int(p)))



### FIXED CODE ###

N, Q = map(int,input().split())
S = list(input())

dp = [float("inf") for i in range(N)]
dp[0] = 0
for i in range(1,N):
    if S[i-1] == "A" and S[i] == "C" :
        dp[i] = dp[i-1] + 1
    else :
        dp[i] = dp[i-1]
val = [[] for i in range(Q)]
for i in range(Q) :
    a,b = map(int,input().split())
    val[i] = [a-1,b-1]
for i in range(Q):
    print("{}".format(dp[val[i][1]]-dp[val[i][0]]))
### BUGGY CODE ###

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

boals = ''

while len(boals) < N:
    for i in range(A):
        boals += 'b'
    
    for i in range(B):
        boals += 'r'

print(boals[:N].count('b'))
    
    


### FIXED CODE ###

N,A,B = map(int, input().split())
adds = A + B
times = N // adds
boalsLen = adds * times
count = A * times


while True:
    if boalsLen > N:
        break
    
    tmpBoalsLen = boalsLen + A
    if tmpBoalsLen > N:
        addBoals = N - boalsLen
        count += addBoals
        break
    
    boalsLen = tmpBoalsLen
    boalsLen += B
    count += A

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

N,X=map(int,input().split())
*A,=map(int,input().split())

ans=0
k=A[0]
while k>X:
    ans+=1
    A[0]-=1
    k-=1 

i=0
while i+1<=N-1:
    j=A[i]+A[i+1]
    while j>X:
        A[i+1]-=1
        j-=1
        ans+=1
    i+=1

print(ans)

### FIXED CODE ###

N,X=map(int,input().split())
*A,=map(int,input().split())

ans=0

if A[0]>X:
    ans+=A[0]-X
    A[0]=X 

i=0
while i+1<=N-1:
    if A[i]+A[i+1]>X:
        ans+=A[i]+A[i+1]-X
        A[i+1]=X-A[i]
    i+=1

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

def main():
    N, K = map(int, input().split())
    ans = 0
    for a in range(1, N + 1):
        i = 0
        while True:
            i += 1
            b = K * i - a
            if b < a:
                continue
            elif b > N:
                break
            else:
                j = 0
                while True:
                    j += 1
                    c = K * j - b
                    if c < b:
                        continue
                    elif c > N:
                        break
                    elif (a + c) % K == 0:
                        if len(set([a, b, c])) == 1:
                            ans += 1
                        elif len(set([a, b, c])) == 3:
                            ans += 6
                        else:
                            ans += 3
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    ans = 0
    if K % 2 == 1:
        ans = (N // K) ** 3
    else:
        ans = (N // K) ** 3
        r = K // 2
        ans += len([1 for v in range(1, N+1) if v % K == r]) ** 3
    print(ans)


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

import sys
sys.setrecursionlimit(10**8)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(4*n)
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            #print(node,val)
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    
n=int(input())
hi=[int(k) for k in input().split()]
co=[int(k) for k in input().split()]
#print(hi)
#print(co)
segTree=SegTee()
dp=[0]*(n)
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(max(dp))  
      

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(4*n)
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            #print(node,val)
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    

n = int(raw_input())
hi = list(map(int,raw_input().split()))
co= list(map(int,raw_input().split()))
#print(hi)
#print(co)
segTree=SegTee()
dp=[0]*(n)
ans=0
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  ans=max(ans,dp[i])
  #print(dp[i])
  segTree.update(0,0,n-1,x-1,dp[i])
  #print(segTree.arr)
#print(dp)
print(segTree.query(0,0,n-1,0,n-1))
### BUGGY CODE ###

n = int(input())

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

cnt = 0
for i in range(n):
    for j in range(n):
        if i == j:
            pass
        else:
            a1 = list(s[i])
            b1 = list(s[j])

            a1.sort()
            b1.sort()

            a2 = "".join(a1)
            b2 = "".join(b1)

            if a2 == b2:
                cnt += 1

print(cnt//2)


### FIXED CODE ###

n = int(input())

s = []
for i in range(n):
    tmp = []
    tmp = list(input())
    tmp.sort()
    s.append("".join(tmp))

s.sort()

cnt = 0
t_cnt = 0
for i in range(n-1):
    if s[i] == s[i+1]:
        t_cnt += 1
    elif s[i] != s[i+1]:
        if t_cnt > 1:
            t_cnt += 1

            t = 0
            for j in range(t_cnt):
                t += j

            cnt += t
            t_cnt = 0
        else:
            cnt += t_cnt
            t_cnt = 0

    if i == n-2:

        if t_cnt > 1:
            t_cnt += 1

            t = 0
            for j in range(t_cnt):
                t += j

            cnt += t
            t_cnt = 0
        else:
            cnt += t_cnt
            t_cnt = 0

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

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

from collections import defaultdict

s = ns()
d = defaultdict(int)
d[0] += 1
k = 0
n = 0
for i in range(len(s))[::-1]:
    n += int(s[i])*(10**k)%2019
    n%=2019
    d[n] += 1
    k+=1

ans = 0

for j in d.values():
    if j > 1:
        ans += j*(j-1)//2

print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

from collections import defaultdict

s = ns()
d = defaultdict(int)
d[0] += 1
k = 1
n = 0
for i in range(len(s))[::-1]:
    n += int(s[i])*k%2019
    n%=2019
    d[n] += 1
    k = (k*10)%2019

ans = 0

for j in d.values():
    if j > 1:
        ans += j*(j-1)//2

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

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    s = list(input())
    k = int(input())
    k -= 1

    d1 = defaultdict(list)
    for i, c in enumerate(s):
        d1[c].append(i)
    d2 = sorted(d1.items())

    lens = len(s)
    for d2e in d2:
        subs = set()
        subs.add(d2e[0])
        for d2ee in d2e[1]:
            for i1 in range(d2ee+1, lens + 1):
                subs.add("".join(s[d2ee:i1]))
        if len(subs) > k:
            subsl = list(subs)
            subsl.sort()
            print(subsl[k])
            sys.exit()
        else:
            k -= len(subs)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    s = list(input())
    k = int(input())
    k -= 1

    d1 = defaultdict(list)
    for i, c in enumerate(s):
        d1[c].append(i)
    d2 = sorted(d1.items())

    lens = len(s)
    for d2e in d2:
        subs = set()
        subs.add(d2e[0])
        for d2ee in d2e[1]:
            end = min(lens + 1, d2ee + k + 2)
            for i1 in range(d2ee+1, end):
                subs.add("".join(s[d2ee:i1]))
        if len(subs) > k:
            subsl = list(subs)
            subsl.sort()
            print(subsl[k])
            sys.exit()
        else:
            k -= len(subs)

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

from math import ceil

def update(rt, ra, t, a):
    while rt * a != ra * t:
        if rt * a < ra * t:
            a = int(ceil(ra * t / rt))
        else:
            t = int(ceil(rt * a / ra))
    return t, a

n = int(input())
data = []
for i in range(n):
    elems = input().split()
    t, a = int(elems[0]), int(elems[1])
    data.append((t, a))

t, a = data[0]

for i in range(1, n):
    t, a = update(data[i][0], data[i][1], t, a)

print(t + a)


### FIXED CODE ###

from math import ceil

n = int(input())
data = []
for i in range(n):
    elems = input().split()
    t, a = int(elems[0]), int(elems[1])
    data.append((t, a))

t, a = data[0]

def calcn(r, x):
    n = int(x / r)
    while n * r > x:
        n -= 1
    while n * r < x:
        n += 1
    return n

for i in range(1, n):
    rt, ra = data[i][0], data[i][1]
    na = int(calcn(ra, a))
    nt = int(calcn(rt, t))
    n = max(na, nt)
    t = n * rt
    a = n * ra

print(t + a)
### BUGGY CODE ###

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

R = N
L = [True] * N
for i in range(1,N):
    #L = [L[j] and L[j+1] and A[j]^A[i+j] == A[j]+A[i+j] for j in range(N-i)] + [False]*(i) 
    L = [L[j] and L[j+1] and not (A[j] & A[i+j]) for j in range(N-i)] + [False]*(i) 
    R += sum(L)
    if sum(L) == 0:
        break
print(R)

### FIXED CODE ###

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

result = 0
Right = 0
tmp = 0
for left in range(N):
    for right in range(Right,N):
        if not (tmp & A[right]):
            tmp += A[right]
            Right = right + 1
        else:
            break
    tmp -= A[left]
    result += Right - left
print(result)
### BUGGY CODE ###

import sys
#input = sys.stdin.buffer.readline
from collections import defaultdict

def main():
    N,P = map(int,input().split())
    S = input()
    
    if 10%P == 0:
        ans = 0
        for i,st in enumerate(S[::-1]):
            num = int(st)
            if num % P == 0:
                ans += N-i
    else:
        ans,base = 0,1
        MOD = 0
        d = defaultdict(int)
        d[0] = 1
        for st in S[::-1]:
            num = int(st)
            MOD = (MOD+num*base)%P
            d[MOD] += 1
            base *= 10
        for v in d.values():
            ans += (v*(v-1))//2
        
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline
from collections import Counter

def main():
    N,P = map(int,input().split())
    s = input()
    l = len(s)
    ans = 0
    if 10%P == 0:
        for i,st in enumerate(s[::-1]):
            num = int(st)
            if num%P == 0:
                ans += l-i
    else:
        rest = [0]
        t = 1
        for st in s[::-1]:
            num = int(st)%P
            rest.append(num*t%P)
            t = t*10%P
            
        for i in range(l):
            rest[i+1] += rest[i]

        for i in range(l):
            rest[i+1] %= P
            
        c = Counter(rest)
        c = list(c.values())
        for num in c:
            ans += num*(num-1)//2
    
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

k = int(input())

l = 0
if k % 7 == 0:
    l = 9 * k // 7
else:
    l = 9 * k

for i in range(1, l + 1):
    m = pow(10, i, l)
    if m == 1:
        print(i)
        break
else:
    print(-1)


### FIXED CODE ###

from numba import njit
k = int(input())

l = 0
if k % 7 == 0:
    l = 9 * k // 7
else:
    l = 9 * k

@njit
def fun():
    m = 1
    for i in range(1, l + 1):
        m = m * 10 % l
        if m == 1:
            print(i)
            break
    else:
        print(-1)

fun()
### BUGGY CODE ###

S = input()
S = list(map(int, S))

nums = [0] * (len(S) + 1)
pow10 = 1
counter = dict({0: 1})
for i in range(1, len(S) + 1):
    nums[i] = (nums[i - 1] + pow10 * S[-i]) % 2019
    if nums[i] not in counter:
        counter[nums[i]] = 1
    else:
        counter[nums[i]] += 1

    pow10 *= 10

ans = 0
for count in counter.values():
    if count >= 2:
        ans += count * (count - 1) // 2

print(ans)


### FIXED CODE ###

S = input()
S = list(map(int, S))

t = 1
r = 0
d = [0] * 2019
d[0] += 1
for n in reversed(S):
    r = (r + n * t) % 2019
    t = t * 10 % 2019
    d[r] += 1

ans = 0
for m in d:
    ans += m * (m-1) // 2

print(ans)