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

from operator import mul
from functools import reduce
from collections import Counter

def cmb(n, r):
    if n < 2:
        return 0
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


N = int(input())
A = [int(x) for x in input().split()]
C = Counter(A)
ans = {}
for a, b in C.items():
    ans[a] = 0
    for i, j in C.items():
        if a == i:
            ans[a] += cmb(b-1, 2)
        else:
            ans[a] += cmb(j, 2)
for a in A:
    print(ans[a])

### FIXED CODE ###

from collections import Counter

N = int(input())
A = [int(x) for x in input().split()]
C = Counter(A)
ans = {}
cal = sum([b*(b-1)//2 for b in C.values()])
for a, b in C.items():
    ans[a] = cal - (b-1)
for a in A:
    print(ans[a])
### BUGGY CODE ###

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

counter = 0

for p in range(n):
    for q in range(n - p):
        a = s[p]
        b = s[p + q]
        if a == b:
            continue
        for r in range(n - p - q):
            c = s[p + q + r]
            if b != c and c != a and q != r:
                # print(a, b, c, p, q, r)
                counter += 1
print(counter)

### FIXED CODE ###

# -*- coding: utf-8 -*-

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

r_cnt = s.count('R')
g_cnt = s.count('G')
b_cnt = s.count('B')

counter = r_cnt * g_cnt * b_cnt

for i in range(n):
    for p in range(n):
        j = i + p
        k = j + p
        if k >= n:
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            counter -= 1
print(counter)
### BUGGY CODE ###

from collections import deque

n = int(input())
s = deque([int(x) for x in input().split()])
q = int(input())
t = [int(x) for x in input().split()]
cnt = 0

for i in t:
    if i in s:
        cnt += 1
        while i in s:
            s.remove(i)
    else:
        continue
print(cnt)


### FIXED CODE ###

def binarySearch(array, key):
    left = 0
    right = len(array)
    while left < right:
        mid = int((left + right) / 2)
        if key == array[mid]:
            return True
        elif key > array[mid]:
            left = mid + 1
        elif key < array[mid]:
            right = mid
        else:
            print("ERROR")
    return False


n = int(input())
s = [int(x) for x in input().split()]
q = int(input())
t = [int(x) for x in input().split()]
a = [x for x in t if binarySearch(s, x)]
print(len(a))
### BUGGY CODE ###

N,K = map(int, input().split())
S = input()

kukan = []
cnt0 = 0
cnt1 = 0
for n in range(N):
        if S[n] == '0':
                cnt0 +=1
                if cnt1 > 0:
                        kukan.append(cnt1)
                cnt1 = 0
        if S[n] == '1':
                cnt1 +=1
                if cnt0 > 0:
                        kukan.append(cnt0)
                cnt0 = 0
kukan.append(max(cnt1,cnt0))

#print(kukan)
ans = []

if S[0] == '0':
        start = 1
else:
        start = 0
l = len(kukan)
if l == 1:
        print(N)
        exit()

for i in range(l-K):
        if (i+start)%2 == 0:
                #print(i+2*K)
                ans.append(sum(kukan[i:min(l+1,i+2*K+1)]))
        else:
                #print(i+2*K-1)
                ans.append(sum(kukan[i:min(l+1,i+2*K)]))

print(max(ans))

### FIXED CODE ###

N,K = map(int, input().split())
S = input()

kukan = []
cnt0 = 0
cnt1 = 0
for n in range(N):
        if S[n] == '0':
                cnt0 +=1
                if cnt1 > 0:
                        kukan.append(cnt1)
                cnt1 = 0
        if S[n] == '1':
                cnt1 +=1
                if cnt0 > 0:
                        kukan.append(cnt0)
                cnt0 = 0

kukan.append(max(cnt1,cnt0))

#print(kukan)
ans = []

if S[0] == '0':
        start = 1
else:
        start = 0

l = len(kukan)

if l == 1:
        print(N)
        exit()

cnt = [0]*(l+1)
for i in range(1,l+1):
        cnt[i] = cnt[i-1] + kukan[i-1]

#print(cnt)
        


for i in range(1,l-K+1):
        if (i+start)%2 == 1:
                #print(i+2*K)
                ans.append(cnt[min(l,i+2*K)]-cnt[i-1])
        else:
                #print(i+2*K-1)
                ans.append(cnt[min(l,i+2*K-1)]-cnt[i-1])


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

N, K = map(int, input().split())
mod = 10**9 + 7

def com(n, r):
    p, q = 1, 1
    for i in range(r):
        p *= ((n-i)%mod)
        q *= ((r-i)%mod)
    return p*pow(q, mod-2, mod)%mod

for k in range(1, K+1):
    print(com(N-K+1, k)*com(K-1, k-1)%mod)

### FIXED CODE ###

N, K = map(int, input().split())
mod = 10**9 + 7

def com(n, r):
    p, q = 1, 1
    for i in range(r):
        p = p*(n-i)%mod
        q = q*(r-i)%mod
    return p*pow(q, mod-2, mod)%mod

for k in range(1, K+1):
    print(com(N-K+1, k)*com(K-1, k-1)%mod)
### BUGGY CODE ###

from itertools import combinations
N = int(input())
M = list(range(1, N+1))
A = list(map(int, input().split()))

cnt = 0
for a, b in list(combinations(M, 2)):
    if abs(a-b) == A[a-1]+A[b-1]:
        cnt += 1

print(cnt)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
D = defaultdict(int)
ans = 0

for i, x in enumerate(A, 1):
    ans += D[i-x]
    D[x+i] += 1

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

N = int(input())
for h in range(1, 3501):
    for n in range(h, 3501):
        bunshi = N * h * n
        bunbo = 4 * h * n - N * n - N * h
        if bunbo > 0 and bunshi % bunbo == 0:
            print("{} {} {}".format(h, n, bunshi // bunbo))
            exit()

### FIXED CODE ###

N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        waru = 4 * h * n - N * n - N * h
        if waru != 0:
            w = (N * h * n) / waru
            if w > 0 and int(w) / w == 1:
                print("{} {} {}".format(h, n, int(w)))
                exit()
### BUGGY CODE ###

#左の最頻と右の最頻合計すればいいんじゃないの？
#でも最頻がお互い3万種類までありえる
#その場合は最頻をminから順番に組み合わせていって、最頻＋最頻が該当した瞬間breakでよい
#これなら処理回数はmax3万？だし
#最頻+最頻-1しかない場合は、左右ぞれぞれ2位×1位を同様に試すいやこれいらんわ
import collections
a = input().split()
M = int(a[2])
hidari = []
migi = []
c = []
 
for i in range(M):
  b = input().split()
  hidari.append(b[0])
  migi.append(b[1])
  c.append(b)
 
countleft = collections.Counter(hidari)
countright = collections.Counter(migi)
leftmax = countleft.most_common()[0][1]
rightmax = countright.most_common()[0][1]
tempmax = int(leftmax + rightmax)
 
leftkeys = [k for k, v in countleft.items() if v == leftmax]
rightkeys = [k for k, v in countright.items() if v == rightmax]
leftkeyN = int(len(leftkeys))
rightkeyN = int(len(rightkeys))
flag = int(0)
cnt = int(0)
#これで左右の最頻回数はOK
#左右の最頻奴も探した
#ここから最頻同志になってるやつを探す
 
for i in range(leftkeyN):
    if flag != 0:
        break
    else:
        for P in range(rightkeyN):
            for T in range(M):
                if c[T] == [leftkeys[i],rightkeys[P]]:
                    cnt = cnt + 1
            if cnt == 0:
                flag = flag + 1
                break
            else:
                cnt = 0
 
if flag == 0:
    print(int(tempmax - 1))
else:
    print(int(tempmax))
    

### FIXED CODE ###

import collections
a = input().split()
M = int(a[2])
hidari = []
migi = []
c = []
 
for i in range(M):
  b = input().split()
  hidari.append(b[0])
  migi.append(b[1])
  c.append(b)
  
countleft = collections.Counter(hidari)
countright = collections.Counter(migi)
leftmax = countleft.most_common()[0][1]
rightmax = countright.most_common()[0][1]
tempmax = int(leftmax + rightmax)
 
leftkeys = [k for k, v in countleft.items() if v == leftmax]
rightkeys = [k for k, v in countright.items() if v == rightmax]
 
leftkeyN = int(len(leftkeys))
rightkeyN = int(len(rightkeys))
flag = int(0)
cnt = int(0)
#これで左右の最頻回数はOK
#左右の最頻奴も探した
#ここから最頻同志になってるやつを探す
 
for i in range(M):
    goukei = int(countleft.get(c[i][0])) + int(countright.get(c[i][1]))
    if goukei == tempmax:
        cnt += 1
    else:
        pass

if cnt == int(leftkeyN * rightkeyN):
    print(int(tempmax - 1))
else:
    print(int(tempmax))
### BUGGY CODE ###

n, m = map(int, input().split())
bad = [int(input()) for _ in range(m)]
back2 = 0
back1 = 1
MOD = int(1e9+7)

for i in range(n):
    if i + 1 in bad:
        back2, back1 = back1, 0
    else:
        back2, back1 = back1, back2+back1

print(back1%MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(150000)

n, m = map(int, input().split())
bad = [int(input()) for _ in range(m)]
MOD = int(1e9+7)

memo = {0:1, 1:1}
for i in bad:
    memo[i] = 0

def fib(n, mod):
    if n not in memo:
        memo[n] = (fib(n-1, mod) + fib(n-2, mod)) % mod
    return memo[n]

print(fib(n, MOD))
### BUGGY CODE ###

import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF for _ in range(H+MAX+1)]

DP[0] = 0

for h in range(H+1):
    for j, magic in enumerate(MAGICS):
        (damage, mp) = magic
        DP[h + damage] = min(DP[h + damage], DP[h] + mp)

for i in reversed(range(len(DP))):
    DP[i-1] = min(DP[i], DP[i-1])

print(DP[H])


### FIXED CODE ###

import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF] * (H+1)

DP[0] = 0

for h in range(H+1):
    for (damage, mp) in MAGICS:
        DP[h] = min(DP[max(h - damage, 0)] + mp, DP[h])

print(DP[H])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
x,k,d=map(int,input().split())
m=abs(x)
n=0
for i in range(k):
  if x<0:
    x+=d
  else:
    x-=d
  if abs(x)<m:
    m=abs(x)
  else:
    n=k-i
    break
if n%2==0:
  print(m)
else:
  print(abs(x))

### FIXED CODE ###

# -*- coding: utf-8 -*-
x,k,d=map(int,input().split())
m=abs(x)
n=m//d
j=k-n
if j>0:
  if x<0:
    if j%2==0:
      x+=d*n
    else:
      x+=d*(n+1)
  else:
    if j%2==0:
      x-=d*n
    else:
      x-=d*(n+1)
else:
  if x<0:
    x+=d*k
  else:
    x-=d*k
print(abs(x))
### BUGGY CODE ###

S=input()
keta=len(S)
import numpy as np
dp=[[0 for j in range(13)] for i in range(keta)]
DIV=10**9+7

if S[-1]=="?":
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[-1])]=1
  
def convert(bef,add):
  nex=bef+add
  if nex>=13:
    nex-=13
  return nex
  
dig=1
for i in range(1,keta):
  dig*=10
  if S[keta-1-i]=="?":
    for k in range(10):
      d=k*dig%13
      for j in range(13):
        dp[i][convert(j,d)]+=dp[i-1][j]
        dp[i][convert(j,d)]%=DIV
  else:
    ch=int(S[keta-1-i])
    d=ch*dig%13
    for j in range(13):
      dp[i][convert(j,d)]+=dp[i-1][j]
      dp[i][convert(j,d)]%=DIV

print(dp[len(dp)-1][5])

### FIXED CODE ###

# 各桁についての13で割ったあまりを足し合わせると5になる
# "??"の場合、
# 1桁目が"3"だと、13で割ったあまりは3
# 2桁目が"8"だと、13で割ったあまりは2
# 従い83を13で割ったあまりは5
# 下から数えてN桁目までに、あまりの合計がP(0〜12)になっている数がそれぞれいくつあるかをDPする
# dp[i桁目(下から数える)][あまりの合計]

S = input()
N = len(S)
S = S[::-1] # 逆順にしたほうがやりやすい
dp = [[0] * 13 for i in range(N)]
if S[0] != "?":
  dp[0][int(S[0])] = 1 # 指定の数をとりあえずカウント
else:
  for i in range(10):
    dp[0][i] = 1 # 1桁目は、あまり0〜9になる数が一つずつある
     
# あまりリストの管理 桁数が一つ増えるごとに、各数に対しての13で割ったあまりを計算する
amari = [i for i in range(10)]
amarimap = {1:10,10:9,9:12,12:3,3:4,4:1,2:7,7:5,5:11,11:6,6:8,8:2,0:0}

DIV = 10 ** 9 + 7

# 各桁のあまりの数を更新する
# これにより、桁が増えたときに更新すべきあまりの種類（あまり13種類に対して
# ひと桁は10種類しかない）を管理できる
def update_amari():
  for i in range(len(amari)):
    amari[i] = amarimap[amari[i]]

# 2桁目以降をDP
for i in range(1,N):
  update_amari() # 各桁のあまりをアップデート
  if S[i] == "?":
    # あらゆる数が入る
    # i-1桁目の各数のループと、i桁目のあまりの各数のループ
    for j in range(len(dp[i-1])):
      # 前の桁であまりがjだったとき
      for k in amari:
        dp[i][(j + k) % 13] += dp[i-1][j]
        dp[i][(j + k) % 13] %= DIV
  else:
    # 数が決まっている
    for j in range(len(dp[i-1])):
      # あまりが決まっている
      am = amari[int(S[i])]
      dp[i][(j + am) % 13] += dp[i-1][j]
      dp[i][(j + am) % 13] %= DIV
        
# 最終桁までいったときにあまりが5になる数が必要なので、dp[N-1][5]が答え
print(dp[N-1][5])
### BUGGY CODE ###

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

D = [set() for _ in range(N+1)]
D[0].add((3,""))

for i in range(N):
    for curr in D[i]:
        l = curr[0]
        s = curr[1]
        # そのまま
        D[i+1].add((l,s))
        # 末尾の1文字を採用する場合
        if l-1 >= 0:
            D[i+1].add((l-1,s+S[i]))

r = filter(lambda x:x[0]==0, D[N])
print(len(list(r)))

### FIXED CODE ###

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

def f(n):
    n = str(n).zfill(3)
    # print(n)
    found = False
    for i in range(len(S)):
        if S[i] == n[0]:
            found = True
            break
    if found == False:
        return 0
    
    found = False
    for j in range(i+1, len(S)):
        if S[j] == n[1]:
            found = True
            break
    if found == False:
        return 0

    found = False
    for k in range(j+1, len(S)):
        if S[k] == n[2]:
            found = True
            break
    if found:
        return 1
    return 0

ans = 0
for i in range(1000):
    ans += f(i)

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

# import sys
# input = sys.stdin.readline

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

n = int(input())
x = list(input())
xc = x.count("1")
xu = []
xd = []
if xc == 0:
    for i in range(n):
        print(1)
        exit()
t = 1
for i in range(n):
    mod = xc+1
    xu.append(t%mod)
    t *= 2
t = 1
flag = False
for i in range(n):
    mod = xc-1
    if mod == 0:
        xd.append(0)
        flag = True
    else:
        xd.append(t%mod)
        t *= 2
xu.reverse()
xd.reverse()
s_xu = 0
s_xd = 0
for i in range(n):
    if x[i] == "1":
        s_xu += xu[i]
        s_xd += xd[i]

# print(xu)
# print(xd)

for i in range(n):
    cnt = 1
    if x[i] == "0":
        tar = (s_xu+xu[i])%(xc+1)
        #print(tar)
        while tar != 0:
            b_tar = list(bin(tar)[2:])
            tar %= b_tar.count("1")
            cnt += 1
        print(cnt)
    else:
        if flag:
            print(0)
        elif s_xd-xd[i] == 0:
            print(1)
        else:
            tar = (s_xd-xd[i])%(xc-1)
            #print(tar)
            while tar != 0:
                b_tar = list(bin(tar)[2:])
                tar %= b_tar.count("1")
                cnt += 1
            print(cnt)







### FIXED CODE ###

# import sys
# input = sys.stdin.readline

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

n = int(input())
x = list(input())
xc = x.count("1")
xu = []
xd = []
if xc == 0:
    for i in range(n):
        print(1)
        exit()
t = 1
for i in range(n):
    mod = xc+1
    xu.append(t%mod)
    t *= 2
    t %= mod
t = 1
flag = False
for i in range(n):
    mod = xc-1
    if mod == 0:
        xd.append(0)
        flag = True
    else:
        xd.append(t%mod)
        t *= 2
        t %= mod
xu.reverse()
xd.reverse()
s_xu = 0
s_xd = 0
for i in range(n):
    if x[i] == "1":
        s_xu += xu[i]
        s_xd += xd[i]

# print(xu)
# print(xd)

for i in range(n):
    cnt = 1
    if x[i] == "0":
        tar = (s_xu+xu[i])%(xc+1)
        #print(tar)
        while tar != 0:
            b_tar = bin(tar)
            tar %= b_tar.count("1")
            cnt += 1
        print(cnt)
    else:
        if flag:
            print(0)
        else:
            tar = (s_xd-xd[i])%(xc-1)
            #print(tar)
            while tar != 0:
                b_tar = bin(tar)
                tar %= b_tar.count("1")
                cnt += 1
            print(cnt)
### BUGGY CODE ###

n,c = map(int,input().split())

cp = [0]*n
cp_rev = [0]*n
d = [0]*n

for i in range(n):
    x,v = map(int,input().split())
    d[i] = x
    cp[i] = v
    cp_rev[n-1-i] = v

sm = [0]*n
sm_rev = [0]*n

sm[0] = cp[0] - d[0]
sm_rev[0] = cp_rev[0] - (c - d[n-1])

for i in range(1,n):
    sm[i] = sm[i-1] + cp[i] - d[i] + d[i-1]
    sm_rev[i] = sm_rev[i-1] + cp_rev[i] - (c - d[n-1-i]) + c - d[n-i]

ret_ind = sm.index(max(sm))
ret_ind_rev = sm_rev.index(max(sm_rev)) 

ans = 0

for i in range(ret_ind + 1):
    ans = max(ans, sm[i])
    if n-i-2 >= 0:
        ans = max(ans, sm[i] - d[i] + max(sm_rev[:n-i-1]))

for i in range(ret_ind_rev + 1):
    ans = max(ans, sm_rev[i])
    if n-i-2 >= 0:
        ans = max(ans,sm_rev[i] - (c - d[n-1-i]) + max(sm[:n-i-1]))

print(ans)

### FIXED CODE ###

n,c = map(int,input().split())

cp = [0]*n
cp_rev = [0]*n
d = [0]*n

for i in range(n):
    x,v = map(int,input().split())
    d[i] = x
    cp[i] = v
    cp_rev[n-1-i] = v

sm = [0]*n
sm_rev = [0]*n
max_sm = [0]*n
max_sm_rev = [0]*n

sm[0] = cp[0] - d[0]
sm_rev[0] = cp_rev[0] - (c - d[n-1])
max_sm[0] = sm[0]
max_sm_rev[0] = sm_rev[0]

for i in range(1,n):
    sm[i] = sm[i-1] + cp[i] - d[i] + d[i-1]
    sm_rev[i] = sm_rev[i-1] + cp_rev[i] - (c - d[n-1-i]) + c - d[n-i]
    max_sm[i] = max(max_sm[i-1],sm[i])
    max_sm_rev[i] = max(max_sm_rev[i-1],sm_rev[i])

ret_ind = sm.index(max(sm))
ret_ind_rev = sm_rev.index(max(sm_rev)) 

ans = 0

for i in range(ret_ind + 1):
    ans = max(ans, sm[i])
    if n-i-2 >= 0:
        ans = max(ans, sm[i] - d[i] + max_sm_rev[n-i-2])

for i in range(ret_ind_rev + 1):
    ans = max(ans, sm_rev[i])
    if n-i-2 >= 0:
        ans = max(ans,sm_rev[i] - (c - d[n-1-i]) + max_sm[n-i-2])

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

N,M=map(int,input().split())
L=list(map(int,input().split()))
R=[0]
sums=0
for i in L:
  sums+=i
  R.append(sums)
ans=0
for i in range(N):
  for j in range(i,N):
    if (R[j]-R[i-1])%M==0:
      ans+=1
print(ans)

### FIXED CODE ###

import collections
N,M=map(int,input().split())
L=list(map(int,input().split()))
R=[0]
sums=0
for i in L:
  sums+=i
  sums=sums%M
  R.append(sums)
c = collections.Counter(R)
A=list(c.values())
A=[i*(i-1)//2 for i in A]
print(sum(A))
### BUGGY CODE ###

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

#output
dp = [0] * N
dp[1] = abs(h[1]-h[0])

for i in range(2, N):
    temp = abs(h[i]-h[i-1]) + dp[i-1]
    for j in range(2, K+1):
        if 0<= i-j <= N-1:
            temp = min(temp, dp[i-j]+abs(h[i]-h[i-j]))
    dp[i] = temp

print(dp[N-1])

### FIXED CODE ###

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

#output
dp = [0] * N
dp[1] = abs(h[1]-h[0])

for i in range(2, N):
    temp = abs(h[i]-h[i-1]) + dp[i-1]
    for j in range(2, K+1):
        if 0<= i-j <= N-1:
            temp = min(temp, dp[i-j]+abs(h[i]-h[i-j]))
    dp[i] = temp

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

n,x,y = map(int,input().split())
ans = [0 for i in range(n)]
for i in range(n):
    for j in range(i,n):
        p = min(abs(i-j),(abs(i-(x-1))+1+abs(y-1-j)),(abs(i-(x-1))+1+abs(y-1-j)))
        if p != 0:
            ans[p] += 1
for i in range(1,n):
    print(ans[i])


### FIXED CODE ###

n,x,y = map(int,input().split())
ans = [0]*n
for i in range(n):
    for j in range(i,n):
        ans[min(j-i,(abs(i-(x-1))+1+abs(y-1-j)),(abs(i-(x-1))+1+abs(y-1-j)))] += 1
for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###

L, R = (int(a) for a in input().split())
mi = 2019
for i in range(L,R):
    for j in range(i+1,R+1):
        mi = min(mi, i*j%2019)
print(mi)

### FIXED CODE ###

l, r = map(int, input().split())
x = []
for i in range(l, r):
    for j in range(i + 1, r + 1):
        mod = i * j % 2019
        x.append(mod)
        if mod == 0:
            print(0)
            exit()
print(min(x))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 1000000007
res = 0
a_sum = sum(a)

for i in range(n - 1):
    main = a.pop(0)
    a_sum = a_sum - main
    res =  (res + main * a_sum % mod) % mod
print(res)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 1000000007
res = 0
a_sum = sum(a)

for i in range(n - 1):
    main = a[i]
    a_sum = a_sum - main
    res =  (res + main * a_sum % mod) % mod
print(res)
### BUGGY CODE ###

import math

ans = []
while True:
	try:
		n = int(raw_input())
		if n < 2:
			ans.append(0)
			continue
		prime_list = range(2, n + 1)
		head = prime_list[0]
		i = 0
		while head < math.sqrt(n):
			for j in range(len(prime_list) - 1, 0, -1):
				if (prime_list[j] % head == 0) & (prime_list[j] != head):
					del prime_list[j]
			i += 1
			head = prime_list[i]
		ans.append(len(prime_list))
	except EOFError:
		break
for num in ans:
	print num

### FIXED CODE ###

MAX = 1000000
prime = [1] * MAX
prime[0], prime[1] = 0, 0
i = 2
while i * i < MAX:
    j = 2
    while i * j < MAX:
        prime[i * j] = 0
        j += 1
    i += 1
for k in range(1, len(prime)):
    prime[k] += prime[k-1]

while True:
    try:
        n = int(raw_input())
        print prime[n]
    except EOFError:
        break
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
aset = set(a)

cnt = 0
for i in aset:
    tmp = a.count(i) + a.count(i + 1) + a.count(i - 1)
    if cnt <= tmp:
        cnt = tmp

print(cnt)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
d = defaultdict(int)

for key in a:
    d[key] += 1

cnt = 0
for i in d:
    d1 = 0
    d2 = 0
    if (i - 1) in d:
        d1 = d[i - 1]
    if (i + 1) in d:
        d2 = d[i + 1]

    cnt = max(cnt, d[i] + d1 + d2)

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

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction

# 10進数表記でnのk進数を求めてlength分0埋め
def ternary (n, k, length):
    if n == 0:
        nums = ['0' for i in range(length)]
        nums = ''.join(nums)
        return nums
    nums = ''
    while n:
        n, r = divmod(n, k)
        nums += str(r)
    nums = nums[::-1]
    nums = nums.zfill(length)
    return nums


def main():
    num = int(input())
    data = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    max_length = len(bin(max(data))) - 2
    bit_count = [0 for i in range(max_length)]

    for i in range(num):
        now_bin = ternary(data[i], 2, max_length)
        data[i] = now_bin
        for j in range(max_length):
            if now_bin[j] == "1":
                bit_count[j] += 1

    flg_data = [0 for i in range(max_length)]

    for i in range(num):
        now_bin = data[i]
        for j in range(max_length):
            if now_bin[j] == "1":
                bit_count[j] -= 1
                flg_data[j] += (num - i - 1 - bit_count[j])
            else:
                flg_data[j] += bit_count[j]

    ans = 0
    for j in range(max_length):
        pow_num = max_length - 1 - j
        bbb = pow(2, pow_num, mod)

        ans += bbb * flg_data[j]
        ans %= mod

    print(ans)




if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction

# 10進数表記でnのk進数を求めてlength分0埋め
def ternary (n, k, length):
    if n == 0:
        nums = ['0' for i in range(length)]
        nums = ''.join(nums)
        return nums
    nums = ''
    while n:
        n, r = divmod(n, k)
        nums += str(r)
    nums = nums[::-1]
    nums = nums.zfill(length)
    return nums


def main():
    num = int(input())
    data = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    max_length = len(bin(max(data))) - 2
    bit_count = [0 for i in range(max_length)]

    for i in range(num):
        now_bin = bin(data[i])[2:]
        now_bin = now_bin.zfill(max_length)
        for j in range(max_length):
            if now_bin[j] == "1":
                bit_count[j] += 1

    flg_data = [0 for i in range(max_length)]


    for i in range(max_length):
        flg_data[i] += bit_count[i] * (num - bit_count[i])

    ans = 0
    for j in range(max_length):
        pow_num = max_length - 1 - j
        bbb = pow(2, pow_num, mod)

        ans += bbb * flg_data[j]
        ans %= mod

    print(ans)




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

S = list(input())
P = 0
for i in range(len(S)-3):
    for j in range(i+4,len(S)+1):
        M = ''.join(S[i:j])
        N = int(M)
        if N%2019 == 0:
            P += 1
print(P)


### FIXED CODE ###

def main():
  n, d, mods = 0, 1, [1]+[0]*2019
  for i in reversed(input()):
    n = (n+int(i)*d)%2019
    d = d*10%2019
    mods[n] += 1
  print(sum([i*(i-1)//2 for i in mods]))
main()