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

def comb2(n, r):
    if r<0 or r>n:
        return 0
    r=min(r, n-r)
    res=1
    for i in range(r):
        res*=(n-i)%MOD*pow(i+1, MOD-2, MOD)%MOD
    return res

MOD=10**9+7

N, A, B=map(int, input().split())
ans=pow(2, N, MOD)-comb2(N, A)-comb2(N, B)-1
print(ans%MOD)

### FIXED CODE ###

def comb2(n, r):
    if r<0 or r>n:
        return 0
    r=min(r, n-r)
    res=1
    for i in range(r):
        res=res*(n-i)%MOD*pow(i+1, MOD-2, MOD)%MOD
    return res

MOD=10**9+7

N, A, B=map(int, input().split())
ans=pow(2, N, MOD)-comb2(N, A)-comb2(N, B)-1
print(ans%MOD)
### BUGGY CODE ###

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

li = [0] * N
for i in range(N):
  for j in range(1, p[i] + 1):
    li[i] += j / p[i]

ans, total = sum(li[:K]), sum(li[:K])
if N != K:
  for i in range(1, N - K + 1):
    total = total - li[i-1] + li[i-1+K]
    ans = max(ans, total)
  print(ans)
else:
  print(ans)

### FIXED CODE ###

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

li = [0] * N
for i in range(N): li[i] = sum(range(1, p[i]+1)) / p[i]

ans, total = sum(li[:K]), sum(li[:K])
if N != K:
  for i in range(1, N - K + 1):
    total = total - li[i-1] + li[i-1+K]
    ans = max(ans, total)
  print(ans)
else: print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
ans = []
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            res = s[i]+s[j]+s[k]
            if not res in ans:
                ans.append(res)
print(len(ans))

### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
    num = str(i).zfill(3)
    x = s.find(num[0])
    y = s.find(num[1], x+1)
    z = s.find(num[2], y+1)
    if x != -1 and y != -1 and z != -1:
            ans += 1
print(ans)
### BUGGY CODE ###

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

dp = [float('inf')] * n
#後者が前者よりも小さい時に更新→DPテーブルをinfに初期化(先頭は0)
def chmin(a,b):
    if(a > b):
        return b
    else:
        return a

dp[0]=0
for i in range(1,n):
    for j in range(1,k+1):
        if j <= i:
            dp[i] = chmin(dp[i], dp[i-j]+abs(h[i]-h[i-j]))

print(dp[n-1])

### FIXED CODE ###

# coding:utf-8
import numpy as np
n,k = map(int, input().split())
h = list(map(int, input().split()))
dp = np.zeros(n, dtype=int)
h = np.array(h)

def main():
    #今判明しているtable
    for i in range(1,n):
        start = max(0, i-k)
        dp[i] = min(dp[start: i] + np.abs(h[i] - h[start:i]))
    
    print(dp[n-1])

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

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict

n, t = li()
ab = [tuple(li()) for _ in range(n)]
ans = 0

for i in range(n):

    dic = defaultdict(int)
    dic[0] = 0
    for ai, bi in ab[:i] + ab[i+1:]:
        newdic = defaultdict(int)
        keys = dic.keys()
        for time, value in dic.items():
            if time + ai < t and time + ai in keys:
                newdic[time + ai] = max(dic[time + ai], value + bi)
            elif time + ai < t:
                newdic[time + ai] = value + bi
            newdic[time] = max(newdic[time], value)
        dic = newdic

    ans = max(ans, max(dic.values()) + ab[i][1])

print(ans)


### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict

n, t = li()
ab = [tuple(li()) for _ in range(n)]
ans = 0

# dp
dp = [[0]*t for _ in range(n+1)]

for i, (ai, bi) in enumerate(ab):
    for ti in range(t):
        if ti + ai < t:
            dp[i+1][ti + ai] = max(dp[i][ti + ai], dp[i][ti] + bi)
        dp[i+1][ti] = max(dp[i+1][ti], dp[i][ti])

# 経路復元
chose = set()
maxtime = dp[n].index(max(dp[n]))

for idx in range(n, 0, -1):
    if dp[idx][maxtime] != dp[idx-1][maxtime]:
        chose.add(idx-1)
        maxtime -= ab[idx-1][0]

allitem = set(range(n))
notchose = allitem - chose

notchosemax = 0
if notchose:
    for i in notchose:
        notchosemax = max(notchosemax, ab[i][1])

print(max(dp[n]) + notchosemax)
### BUGGY CODE ###


S = input()
n = len(S)
mod = (10**9 + 7)

A = [0] * len(S)
C = [0] * len(S)
Q = [0] * len(S)
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

def acc(l):
    for i in range(1, len(l)):
        l[i] += l[i - 1]
acc(A)
acc(C)
acc(Q)

def pow(x, n, mod):
    if n == 0: return 1
    d, m = divmod(n, 2)
    p = pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * (3 ** qa)) % mod
    if qa > 0:
        a += (pow(3, qa - 1, mod) * qa) % mod

    ci = C[b]
    qc = Q[b]
    lc = C[n - 1] - ci
    lqc = Q[n - 1] - qc
    c = (lc * (3 ** lqc)) % mod
    if lqc > 0:
        c += (pow(3, lqc - 1, mod) * lqc) % mod
    
    ans += (a * c) % mod

print(ans % mod)

### FIXED CODE ###

S = input()
n = len(S)
mod = (10**9 + 7)

dp = [[0] * 4 for _ in range(n + 1)]

dp[n] = [0, 0, 0, 1]
for i in range(n-1, -1, -1):
    if S[i] == '?':
        dp[i][3] =  dp[i+1][3] * 3 % mod
        dp[i][2] = (dp[i+1][2] * 3 + dp[i+1][3]) % mod
        dp[i][1] = (dp[i+1][1] * 3 + dp[i+1][2]) % mod
        dp[i][0] = (dp[i+1][0] * 3 + dp[i+1][1]) % mod
    elif S[i] == 'C':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] = (dp[i+1][2] + dp[i+1][3]) % mod
        dp[i][1] =  dp[i+1][1] % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'B':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] =  dp[i+1][2] % mod
        dp[i][1] = (dp[i+1][1] + dp[i+1][2]) % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'A':
        dp[i][3] =  dp[i+1][3]
        dp[i][2] =  dp[i+1][2]
        dp[i][1] =  dp[i+1][1]
        dp[i][0] = (dp[i+1][0] + dp[i+1][1]) % mod
print(dp[0][0])
### BUGGY CODE ###

from collections import deque

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

tree=[[] for i in range(n)]
for i in range(n-1):
 i,j=map(int,input().split())
 tree[i-1].append(j-1)
 tree[j-1].append(i-1)

t_cnt=[0 for i in range(n)]
for i in range(q):
 p,x=map(int,input().split())
 t_cnt[p-1]+=x

cnt=[-1]*n
cnt[0]=t_cnt[0]

seen=([0])

dq=deque()
dq.append(0)

while dq:
 x=dq.popleft()
 for i in tree[x]:
#  if cnt[i]==-1:
#  if i in seen:
#   continue
#  else:
   if i not in seen:
    seen.append(i)
    dq.append(i)
    cnt[i]=cnt[x]+t_cnt[i]

print(*cnt)

### FIXED CODE ###

from collections import deque

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

tree=[[] for i in range(n)]
for i in range(n-1):
 i,j=map(int,input().split())
 tree[i-1].append(j-1)
 tree[j-1].append(i-1)

t_cnt=[0 for i in range(n)]
for i in range(q):
 p,x=map(int,input().split())
 t_cnt[p-1]+=x

cnt=[-1]*n
cnt[0]=t_cnt[0]

seen=set([0])

dq=deque()
dq.append(0)

while dq:
 x=dq.popleft()
 for i in tree[x]:
#  if cnt[i]==-1:
   if i in seen:
    continue
   else:
    seen.add(i)
    dq.append(i)
    cnt[i]=cnt[x]+t_cnt[i]

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

A, B, C, D = map(int,input().split())

d={}
d[(A,B)]=1
for i in range(A+1,C+1):
  d[(i,B)] = B*d[(i-1,B)] % 998244353
for j in range(B+1,D+1):
  d[(A,j)] = A*d[(A,j-1)] % 998244353
 
for i in range(A+1,C+1):
  for j in range(B+1,D+1):
    d[(i,j)]=(j*d[(i-1,j)]+i*d[(i,j-1)]-(i-1)*(j-1)*d[(i-1,j-1)]) % 998244353
    
print(d[(C,D)] % 998244353)

### FIXED CODE ###

import sys
import numpy as np
#from functools import lru_cache
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
MOD = 998_244_353
 
def main(A, B, C, D):
	d = np.zeros((C + 1, D + 1), np.int64)
	d[A,B]=1
	for i in range(A+1,C+1):
  		d[i,B] = B*d[i-1,B] % MOD
	for j in range(B+1,D+1):
		d[A,j] = A*d[A,j-1] % MOD
 
	for i in range(A+1,C+1):
		for j in range(B+1,D+1):
			d[i,j]=((((j*d[i-1,j]) % MOD + i*d[i,j-1] % MOD) % MOD) -((i-1)*((j-1)*d[i-1,j-1] % MOD)% MOD)% MOD)
    
	return d[C,D] % MOD
          
"""    
    print(d[C][D] % MOD)
    dp = np.zeros((C + 1, D + 1), np.int64)
    dp[C, D] = 1
    for d in range(D, 0, -1):
        dp[C, d - 1] = dp[C, d] * C % MOD
    for c in range(C - 1, -1, -1):
        x = 0
        for d in range(D, -1, -1):
            dp[c, d] = (d * dp[c + 1, d] + x) % MOD
            x += dp[c + 1, d]
            x *= c
            x %= MOD
    return dp[A, B]
"""

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.from_dtype(np.int64)
    signature = (i8, i8, i8, i8)
 
    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()
 
from my_module import main
 
A, B, C, D = map(int, read().split())
print(main(A, B, C, D))
### BUGGY CODE ###

while True:
    A = []
    s = 0
    a = input().split()
    X, Y = list(map(int,list(a)))
    if X > Y or Y > 10**18 or X < 1:
        continue
    A.append(X)
    for i in range(2*X,Y+1):
        if i == A[len(A)-1]*2:
            A.append(i)
    s = len(A)
    if A[len(A)-1] > Y:
        s = len(A) -1
    print(s)
    break

### FIXED CODE ###

while True:
    A = []
    s = 0
    a = input().split()
    X, Y = list(map(int,list(a)))
    if X > Y or Y > 10**18 or X < 1:
        continue
    A.append(X)
    while True:
        A.append(A[len(A)-1]*2)
        if A[len(A)-1] > Y:
            break
    s = len(A) - 1
    print(s)
    break
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
c_s = list(map(int, input().split()))
b_s = list(map(int, input().split()))
a_s = list(map(int, input().split()))
a_s.sort(reverse=True)
b_s.sort(reverse=True)
c_s.sort(reverse=True)

d = {}
abcs = [0]
j = -1

for a in a_s:
    for b in b_s:
        for c in c_s:
            abc = a + b + c
            if j >= k and abcs[k-1] >= abc:
                break
            if abcs[0] == 0:
                abcs[0] = abc
            else:
                for i in reversed(range(len(abcs))):
                    if abcs[i] >= abc:
                        abcs.insert(i+1, abc)
                        break
                if j >= k:
                    abcs.pop(-1)
            j += 1
for i in range(k):
    print(abcs[i])


### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = []
for ai in a:
  for bi in b:
    ab.append(ai + bi)
ab.sort(reverse = True)

abc = []

for abi in ab[:k]:
  for ci in c:
    abc.append(abi + ci)
abc.sort(reverse = True)

for abci in abc[:k]:
  print(abci)
### BUGGY CODE ###

from collections import deque

def deletefirst():
    q.popleft()

def deletelast():
    q.pop()

def insert():
    q.appendleft(cmd[1])

def delete():
    try:
        q.remove(cmd[1])
    except:
        pass

run = {
    'insert': insert,
    'delete': delete,
    'deleteFirst': deletefirst,
    'deleteLast': deletelast,
}
n = int(input())

q = deque()
for i in range(n):
    cmd = input().strip().split()
    run[cmd[0]]()

print(' '.join(q))

### FIXED CODE ###

import sys
from collections import deque

n = int(sys.stdin.readline())
q = deque()
for i in range(n):
    cmd = sys.stdin.readline()[:-1]
    if cmd[0] == 'i':
        q.appendleft(cmd[7:])
    elif cmd[6] == ' ':
        try:
            q.remove(cmd[7:])
        except:
            pass
    elif cmd[6] == 'F':
        q.popleft()
    else:
        q.pop()

print(' '.join(q))
### BUGGY CODE ###

s = input()
alphabet = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m"\
        , "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]

ans = 0
i = 1
while i * 2 < len(s):
  if s[:i] == s[i:2 * i]: ans = i
print(ans)


### FIXED CODE ###

s = input()
alphabet = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m"\
        , "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]

ans = 0
i = 1
while i * 2 < len(s):
  if s[:i] == s[i:2 * i]: ans = i * 2
  i += 1
print(ans)
### BUGGY CODE ###

num = int(input())
line = input().split()

x = 1
for i in range(num):
  x = x * int(line[i])
  
if x > 10 ** 18:
    print("-1")
else:
  print(x)

### FIXED CODE ###

num = int(input())
line = input().split()

if "0" in line:
  x = 0
else:
  x = 1
  for i in range(num):
    x = x * int(line[i])
    
    if x > 10 ** 18:
      x = -1
      break
  
print(x)
### BUGGY CODE ###

import math

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

ans = 0
while(len(A) > 0):
    a = A[0]
    A.pop(0)
    for i in range(len(A)):
        if math.log2(A[i] + a).is_integer():
            ans += 1
            A.pop(i)
            break

print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
c = Counter(A)

ans = 0
for a in A:
    b = (1 << a.bit_length()) - a
    if a == b and c[a] > 1:
        c[a] -= 2
        ans += 1
    elif a != b and c[a] > 0 and c[b] > 0:
        c[a] -= 1
        c[b] -= 1
        ans += 1

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

a,b=map(int, input().split())
c=list(map(int, input().split())) 
 
l = [1]
tmp = 1
s = 0
for i in range(b):
    l.append(c[tmp-1])
    tmp = c[tmp-1]
    if c[tmp-1] in l:
        s = c[tmp-1]
        t = len(l)+1
        break
    

#print(l)
if a > b:
    print(l[b])
    exit()

h = l.index(s) + 1

#print(s,h,t)
l2 = l[h-1:t-1]
#print(l2)
if s == 1:
    id = b % (t - 1)
    print(l2[id])
else:
    id = (b - h + 1) % (t - h)
    print(l2[id])

### FIXED CODE ###

a,b=map(int, input().split())
c=list(map(int, input().split())) 
 
l = [1]
f = [0]*a
f[0] += 1
tmp = 1
s = 0
for i in range(b):
    l.append(c[tmp-1])
    tmp = c[tmp-1]
    if f[tmp-1] != 0:
        s = c[tmp-1]
        t = len(l)+1
        break
    f[tmp-1] += 1

#print(l)
if a > b:
    print(l[b])
    exit()

h = l.index(s) + 1

#print(s,h,t)
l2 = l[h-1:t-1]
#print(l2)
if s == 1:
    id = b % (t - 1)
    print(l2[id])
else:
    id = (b - h + 1) % (t - h)
    print(l2[id])
### BUGGY CODE ###

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

if 1 not in A:
    print(-1)
    exit()


for i in range(N-1):
    if A[i] in l:
        continue
    if l[c]+1 != A[i]:
        continue
    for j in range(i+1,N):
        if A[i]>A[j]:
            if A[j] not in l:
                continue
        else:
            if A[i] not in l:
                l.append(A[i])
                c+=1
if l[-1]+1 == A[-1]:
    l.append(A[-1])

print(N+1-len(l))


### FIXED CODE ###

N=int(input())
A=[int(x) for x in input().split()]
ne=1
c=0

if 1 not in A:
    print(-1)
    exit()


for i in range(N-1):
    if A[i]==ne:
        c+=1
        ne+=1
if A[-1]==ne:
    c+=1
print(N-c)
### BUGGY CODE ###

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


class Dice:
    def __init__(self, n):
        self.upper    = n[0]
        self.backward = n[1]
        self.right    = n[2]
        self.left     = n[3]
        self.ahead    = n[4]
        self.bottom   = n[5]

    def roll_north(self):
        self.upper, self.ahead, self.bottom, self.backward = self.backward, self.upper, self.ahead, self.bottom

    def roll_south(self):
        self.upper, self.ahead, self.bottom, self.backward = self.ahead, self.bottom, self.backward, self.upper

    def roll_east(self):
        self.upper, self.right, self.bottom, self.left = self.left, self.upper, self.right, self.bottom

    def roll_west(self):
        self.upper, self.right, self.bottom, self.left = self.right, self.bottom, self.left, self.upper

    def roll_side(self):
        self.ahead, self.right, self.backward, self.left = self.left, self.ahead, self.right, self.backward


dice_info = Dice(list(map(int, input().split())))
q = int(input())
upper, ahead = map(int, input().split())

for i in range(q):
    while upper != dice_info.upper or ahead != dice_info.ahead:
        dice_info.roll_north()

    while upper != dice_info.upper:
        dice_info.roll_east()

    while ahead != dice_info.ahead:
        dice_info.roll_side()

    print(dice_info.right)


### FIXED CODE ###

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


class Dice:
    def __init__(self, n):
        self.upper    = n[0]
        self.backward = n[1]
        self.right    = n[2]
        self.left     = n[3]
        self.ahead    = n[4]
        self.bottom   = n[5]

    def roll_north(self):
        self.upper, self.ahead, self.bottom, self.backward = self.backward, self.upper, self.ahead, self.bottom

    def roll_south(self):
        self.upper, self.ahead, self.bottom, self.backward = self.ahead, self.bottom, self.backward, self.upper

    def roll_east(self):
        self.upper, self.right, self.bottom, self.left = self.left, self.upper, self.right, self.bottom

    def roll_west(self):
        self.upper, self.right, self.bottom, self.left = self.right, self.bottom, self.left, self.upper

    def roll_side(self):
        self.ahead, self.right, self.backward, self.left = self.left, self.ahead, self.right, self.backward


dice_info = Dice(list(map(int, input().split())))
q = int(input())

for i in range(q):
    upper, ahead = map(int, input().split())

    if upper is dice_info.left:
        dice_info.roll_east()
        
    elif upper is dice_info.right:
        dice_info.roll_west()

    while not (upper == dice_info.upper or ahead == dice_info.ahead):
        dice_info.roll_north()

    while upper != dice_info.upper:
        dice_info.roll_east()

    while ahead != dice_info.ahead:
        dice_info.roll_side()

    print(dice_info.left)
### BUGGY CODE ###

import numpy as np

N,K,Q = map(int, input().split())
A = [K] * N

A_np = np.array(A)

for i in range(Q):
	a = int(input())
	A_np -= 1
	A_np[a-1] += 1
	#print(A_np)


for j in range(N):
	if A_np[j] > 0:
		print("Yes")
	else:
		print("No")

### FIXED CODE ###

N,K,Q = map(int, input().split())
#A = [K] * N

A = [0] * N

for i in range(Q):
	a = int(input())
	A[a-1] += 1

sm = sum(A)

for j in range(N):
	if K - (sm-A[j]) > 0:
		print("Yes")
	else:
		print("No")
### BUGGY CODE ###

k,s=map(int,input().split())
a=0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i+j+l==s:
                a+=1
print(a)

### FIXED CODE ###

k,s=map(int,input().split())
a=0
for i in range(k+1):
    for j in range(k+1):
        if 0<=s-i-j<k+1:
            a+=1
print(a)
### BUGGY CODE ###

"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
# import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""
from collections import deque, defaultdict, Counter
import math
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))
# WideIntPoint


def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  # SingleInt


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  # HeightString


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  # MatrixInt


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  # NumberGrid


def grid(n): return [s_list() for _ in range(n)]


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

# a/b の切り上げ


def round_up(a, b):
    """ a/b の切り上げ """
    c = (a + b - 1) / b
    return c


def lcm(a, b):
    """a,bの最小公倍数"""
    return a * b // gcd(a, b)


def main():
    s = input()[::-1]

    cnt = [0] * 2019
    # print(cnt)
    cnt[0] = 1
    ans = 0
    b = ''
    for c in s:
        b += c
        d = b[::-1]
        a = int(d)
        amari = a % 2019
        cnt[amari] += 1

    for i in range(2019):
        ans += cnt[i] * (cnt[i] - 1) // 2
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

s = input()[::-1]

sum_of_digits = 0

cnts = [0] * 2019

cnts[0] = 1

d = 1

for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    cnts[sum_of_digits] += 1

ans = 0

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

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

n=int(input())

ans=1

for i in range(1,n+1):
    ans*=i

print(ans%(10**9+7))

### FIXED CODE ###

n=int(input())

ans=1

for i in range(1,n+1):
    ans=(ans*i)%(10**9+7)

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

from itertools import permutations
n,m,r=map(int,input().split())
vis=list(map(int,input().split()))
INF=10**6
path=[[INF]*n for i in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  path[a-1][b-1]=c
  path[b-1][a-1]=c
for i in range(n):
  for j in range(n):
    for k in range(n):
      if i!=j and j!=k and k!=i:
        path[i][j]=min(path[i][j],path[i][k]+path[k][j])
        path[j][i]=path[i][j]
ans=10**9
for root in permutations(vis):
  cnt=0
  for j in range(1,r):
    cnt+=path[root[j-1]-1][root[j]-1]
  ans=min(ans,cnt)
print(ans)

### FIXED CODE ###

from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
n,m,r=map(int,input().split())
vis=list(map(int,input().split()))
INF=10**18
path=[[INF]*n for i in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  path[a-1][b-1]=c
  path[b-1][a-1]=c
path=floyd_warshall(path)
ans=10**18
for root in permutations(vis):
  cnt=0
  for j in range(1,r):
    cnt+=path[root[j-1]-1][root[j]-1]
  ans=min(ans,cnt)
print(int(ans))