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

# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(n, k, ai):
    mod = int(1e9 + 7)
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in ai:
        # csum: Cumulative sum
        # dp[j] = dp[0] + dp[1] + ... + dp[j]
        dp = list(accum(dp, lambda x, y: (x + y) % mod))
        # j = 0 ～ a[i] までは累積和の結果そのままで a[i] + 1 以降は
        # dp[j] -= dp[j] - dp[j - a[i] - 1]
        dp[a + 1:] = [x - y for x, y in zip(dp[a + 1:], dp)]
    return(dp[k])

n, k = map(int, input().split()) # 1 <= n <= 100, 0 <= k <= 10^5
a = list(map(int, input().split()))
print(f(n, k, a))


### FIXED CODE ###

# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(n, k, ai):
    mod = int(1e9 + 7)
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in ai:
        # csum: Cumulative sum
        # dp[j] = dp[0] + dp[1] + ... + dp[j]
        # dp = list(accum(dp, lambda x, y: (x + y) % mod))
        dp = list(accum(dp))
        # j = 0 ～ a[i] までは累積和の結果そのままで a[i] + 1 以降は
        # dp[j] -= dp[j] - dp[j - a[i] - 1]
        dp[a + 1:] = [x - y for x, y in zip(dp[a + 1:], dp)]
        dp = [x % mod for x in dp]
    return(dp[k])

n, k = map(int, input().split()) # 1 <= n <= 100, 0 <= k <= 10^5
a = list(map(int, input().split()))
print(f(n, k, a))
### BUGGY CODE ###

# temp
n,w = map(int,input().split())
wv = [tuple(map(int,input().split())) for i in range(n)]

dp = [0] + [float("inf")]*(10**5)
for i in range(n):
    for j in range(10**5,wv[i][1]-1,-1):
        dp[j] = min(dp[j],dp[j-wv[i][1]]+wv[i][0])

res = 0
for v,e in enumerate(dp):
    if e <= w:
        res = v
print(res)

### FIXED CODE ###

# temp
n,w = map(int,input().split())
wv = [tuple(map(int,input().split())) for i in range(n)]

dp = [0] + [float("inf")]*(10**5)
for i in range(n):
    for j in range(10**5,wv[i][1]-1,-1):
        dp[j] = min(dp[j],dp[j-wv[i][1]]+wv[i][0])

res = 0
for v,e in enumerate(dp):
    if e <= w:
        res = v
print(res)
### BUGGY 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()))

a.sort(key=lambda x: -x)
b.sort(key=lambda x: -x)
c.sort(key=lambda x: -x)

xyz = []

for ia in range(len(a)):
    for ib in range(len(b)):
        for ic in range(len(c)):
            if (ia*ib*ic) <= k:
                xyz.append(a[ia]+b[ib]+c[ic])
            else:
                break

xyz.sort(key=lambda x: -x)
for l in xyz[:k]:
    print(l)


### 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()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

xyz = []

for ia in range(len(a)):
    for ib in range(len(b)):
        for ic in range(len(c)):
            if (ia+1)*(ib+1)*(ic+1) <= k:
                xyz.append(a[ia]+b[ib]+c[ic])
            else:
                break

xyz.sort(reverse=True)
for l in xyz[:k]:
    print(l)
### BUGGY CODE ###

from itertools import groupby
N = int(input())
A = list(map(int, input().split(' ')))

p = [v - (i + 1) for i, v in enumerate(A)]
s_p = list(groupby(sorted(p)))

res = float('INF')
for k, g in s_p:
    res = min(res, sum([abs(i - k) for i in p]))
    
print(res)

### FIXED CODE ###

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

p = sorted([v - (i + 1) for i, v in enumerate(A)])

if len(p) >= 3:
    res = min(sum(map(abs, [i - p[N//2] for i in p])), sum(map(abs, [i - p[N//2-1] for i in p])), sum(map(abs, [i - p[N//2+1] for i in p])))
elif len(p) >= 2:
    res = min(sum(map(abs, [i - p[0] for i in p])), sum(map(abs, [i - p[1] for i in p])))
else:
    res = 0
print(int(res))
### BUGGY CODE ###

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

B = []
for i in range(N):
    B.append(A.index(i+1) + 1)

print(' '.join(map(str, B)))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [0]*N
for i in range(N):
    B[A[i]-1] = i+1
print(' '.join(map(str, B)))
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K=int(input())

ans=K**2+(K-1)*K+(K-1)*(K-1)

for a in range(1,K):
    for b in range(1,K):
        for c in range(1,K):
            ans += gcd(a+1,b+1,c+1)

print(ans)

### FIXED CODE ###

import math


K=int(input())

ans=0

for a in range(K):
    for b in range(K):
        tmp=math.gcd(a+1,b+1)
        for c in range(K):
            ans += math.gcd(tmp,c+1)

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

n = int(input())
s = [''.join(sorted(input())) for i in range(n)]
cnt = 0
for i in range(len(s)-1):
  for j in range(i+1, len(s)):
    if s[i] == s[j]:
      cnt += 1
print(cnt)

### FIXED CODE ###

import collections
n=int(input())
s=[''.join(sorted(input())) for i in range(n)]
s_cnt=collections.Counter(s)
ans=sum(i*(i-1)//2 for i in s_cnt.values())
print(ans)
### BUGGY CODE ###

import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A, B, K = il()
    R = range(A, B + 1)
    for r in R:
        if A <= r <= A + K - 1 or B >= r >= B - K + 1:
            print(r)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A, B, K = il()
    ret = set()
    for n in range(A, min(A+K, B)):
        ret.add(n)
    for n in range(max(B-K+1, A), B+1):
        ret.add(n)
    print(*sorted(ret), sep="\n")


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

import sys
# import collections
# import math
# import string
# import bisect
# import re
# import itertools
# import statistics

def primeNums(n):
    from math import floor, sqrt
    sieve = set(range(2, n + 1))
    if 2 in sieve:
        not_prime = set(range(2 * 2, n + 1, 2))
        sieve -= not_prime
    for i in range(3, floor(sqrt(n)) + 1, 2):
        if i in sieve:
            not_prime = set(range(i * 2, n + 1, i))
            sieve -= not_prime
    return sieve

limit = 10 ** 5
prime_table = [0 for _ in range(limit + 1)]
for p in primeNums(limit):
    prime_table[p] = 1

def main():

    q = int(sys.stdin.readline().rstrip())
    lines = sys.stdin.readlines()
    
    for j in range(q):
        l, r = [int(x) for x in lines[j].split()]
        res = 0
        for i in range(l if l % 2 == 1 else l + 1, r + 1, 2):
            res += (prime_table[(i + 1) // 2] if prime_table[i] else 0)
        
        print(res)


if __name__ == "__main__":
    # execute only if run as a script
    main()


### FIXED CODE ###

import sys
# import collections
# import math
# import bisect
# import re
# import itertools


def primeNums(n):
    from math import floor, sqrt
    sieve = set(range(2, n + 1))
    if 2 in sieve:
        not_prime = set(range(2 * 2, n + 1, 2))
        sieve -= not_prime
    for i in range(3, floor(sqrt(n)) + 1, 2):
        if i in sieve:
            not_prime = set(range(i * 2, n + 1, i))
            sieve -= not_prime
    return sieve

limit = 10 ** 5
prime_table = [0 for _ in range(limit + 1)]
for p in primeNums(limit):
    prime_table[p] = 1

like_2017_table = [0 for _ in range(limit + 1)]
for i in range(3, limit + 1, 2):
    if prime_table[i] and prime_table[(i + 1) // 2]:
            like_2017_table[i] = 1

s = [0 for _ in range(limit + 1)]
for i in range(limit):
    s[i+1] = s[i] + like_2017_table[i+1]

def main():

    q = int(sys.stdin.readline().rstrip())
    m = map(int, sys.stdin.read().split())

    for l, r in zip(m, m):
        res = s[r] - s[l-1]
        print(res)


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

#dp[i]denotes who will win if i stones left
import sys
sys.setrecursionlimit(10**6)
def f(i):
	global xi
	if(i<m):
		return 2
	if(i in xi):
		return xi[i]
	done=0
	for j in hashi:
		if(j<=i):
			if(f(i-j)==2):
				xi[i]=1
				done=1
				return 1
	if(done==0):
		xi[i]=2
	return 2
l=input().split()
n=int(l[0])
k=int(l[1])
l=input().split()
li=[int(i) for i in l]
hashi=dict()
for i in li:
	hashi[i]=1
m=min(li)
xi=dict()
if(f(k)==1):
	print("First")
else:
	print("Second")

### FIXED CODE ###

#dp[i]denotes who will win if i stones left
l=input().split()
n=int(l[0])
k=int(l[1])
l=input().split()
li=[int(i) for i in l]
hashi=dict()
for i in li:
	hashi[i]=1
m=min(li)
dp=[0 for i in range(k+1)]
dp[0]=2
for i in range(1,k+1):
	if(i<m):
		dp[i]=2
	done=0
	for j in hashi:
		if(i>=j and dp[i-j]==2):
			done=1
			break
	dp[i]=2-done
if(dp[k]==1):
	print("First")
else:
	print("Second")
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, T = map(int, readline().split())

AB= list(map(int, read().split()))
A = AB[0::2]
B = AB[1::2]
ls = sorted(zip(A, B))
#ls = list(zip(A, B))
# 食べるのにかかる時間で昇順にソート
#ls.sort()
# 上の並び順において、ls[i:]の美味しさの最大値をdeli[i]とする
deli = [0]*N
deli[- 1] = ls[-1][- 1]
for i in range(N - 2, - 1, - 1):
    deli[i] = max(deli[i - 1], ls[i][- 1])

res = 0
dp = [0]*T
for i in range(N - 1):
    for j in range(T - 1, - 1, - 1):
        if ls[i][0] <= j:
            dp[j] = max(dp[j], dp[j - ls[i][0]] + ls[i][1])
    res = max(res, dp[- 1] + deli[i + 1])
print(res)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, T = map(int, readline().split())

AB= list(map(int, read().split()))
A = AB[0::2]
B = AB[1::2]
ls = list(zip(A, B))
# 食べるのにかかる時間で昇順にソート
ls.sort()
# 上の並び順において、ls[i:]の美味しさの最大値をdeli[i]とする
deli = [0]*N
deli[- 1] = ls[-1][- 1]
for i in range(N - 2, - 1, - 1):
    deli[i] = max(deli[i - 1], ls[i][- 1])

res = 0
dp = [0]*T
for i in range(N - 1):
    for j in range(T - 1, - 1, - 1):
        if ls[i][0] <= j:
            dp[j] = max(dp[j], dp[j - ls[i][0]] + ls[i][1])
    res = max(res, dp[- 1] + deli[i + 1])
print(res)
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = 0

for i in range(len(S)-2):
    char_1 = S[i]
    for j in range(i+1, len(S)-1):
        char_2 = S[j]
        if char_1 == char_2:
            continue
        one2twodist = j - i
        for k in range(j+1, len(S)):
            char_3 = S[k]
            if char_2 == char_3 or char_1 == char_3 or one2twodist == (k - j):
                continue
            ans += 1

print(ans)


### FIXED CODE ###

N = int(input())
S = list(input())
ans = 0
R, G, B = 0, 0, 0

for char in S:
    if char == "R":
        R += 1
    elif char == "G":
        G += 1
    else:
        B += 1

ans = R*G*B

for i in range(len(S)):
    for j in range(i+1, len(S)):
        if S[i] != S[j]:
            i2j = j - i
            try:
                if not S[j+i2j] in [S[i], S[j]]:
                    ans -= 1
            except:
                break

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

n,W = map(int,input().split())
w = []
v = []
for i in range(n):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)

dp = [[0]*(W+1) for j in range(n+1)]

for i in range(n-1,-1,-1):
    for j in range(W+1):
        if j < w[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])
print(dp[0][W])

### FIXED CODE ###

n,W = map(int,input().split())
w = []
v = []
for i in range(n):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)

dp = [[0]*(W+1) for j in range(n+1)]

for i in range(n-1,-1,-1):
    for j in range(W+1):
        if j < w[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])
print(dp[0][W])
### BUGGY CODE ###

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

J=[0]
j=0
while j<N:
    if j-A[j]>0:
        J.append(j-A[j])
    j+=1

ans=0
i=0
while i<N:
    ans+=J.count(i+A[i])
    i+=1

print(ans)

### FIXED CODE ###

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

J=[0]*N
j=0
while j<N:
    J[j]=j-A[j]
    j+=1

import collections
C = collections.Counter(J)

ans=0
i=0
while i<N:
    ans+=C[i+A[i]]
    i+=1

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

def main():
    n=int(input())
    d=[0]+[-10**18]*n
    for j,(a,i)in enumerate(sorted((-a,i)for i,a in enumerate(map(int,input().split())))):
        d=[max(t-a*abs(~i-j+k+n),d[k-1]-a*abs(~i+k))for k,t in enumerate(d)]
    print(max(d))
main()

### FIXED CODE ###

e=enumerate
n,*a=map(int,open(0).read().split())
dp=[0]
for j,(a,i)in e(sorted((a,i)for i,a in e(a))[::-1]):dp=[dp[0]+a*abs(n-j-i-1)]+[max(dp[k]+a*abs(n-j+k-i-1),dp[k-1]+a*abs(i-k+1))for k in range(1,j+1)]+[dp[j]+a*abs(i-j)]
print(max(dp))
### BUGGY CODE ###

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

for m in range(M):
  B,C = map(int,input().split())
  A+=B*[C]

A = sorted(A)[::-1]
print(sum(A[:N]))

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for m in range(M)]
BC = sorted(BC,key=lambda x:x[1])[::-1]

for b,c in BC:
  A.extend(b*[c])
  if 2*N<len(A):
    break

A = sorted(A)[::-1]
print(sum(A[:N]))
### BUGGY CODE ###

N = int(input())
S = list(input())
R = []

for i in range(N):
    R.append(S[:i].count('W') + S[i:].count('E'))

print(min(R))


### FIXED CODE ###

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

A = []

for n in range(N):
    if n == 0:
        L = 0
        R = sum([s == 'E' for s in S[n+1:]])
    else:
        L += 0 if S[n-1] == 'E' else 1
        R -= 0 if S[n]   != 'E' else 1
    A.append(L+R)

print(min(A))
### BUGGY CODE ###

def main():
  s = input()
  divisor = 10 ** 9 + 7
  lut = [i % 13 for i in range(133)]
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  list10 = list(range(10))
  list13 = list(range(13))
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      for j in list10:
        for k in list13:
          dpi1[lut[k * 10 + j]] += dpi[k]
    else:
      t = int(s[i])
      for k in list13:
        dpi1[lut[k * 10 + t]] += dpi[k]
    for k in range(13):
      dpi1[k] %= divisor
  print(dp[len(s)][5])
main()


### FIXED CODE ###

s = ''.join(reversed(input()))
multiplier = 1
divisor = 10 ** 9 + 7
p = [0 for i in range(13)]
if s[0] != '?':
  p[int(s[0])] = 1
else:
  for j in range(10):
    p[j] = 1
for i in range(1, len(s)):
  multiplier = (10 * multiplier) % 13
  np = [0 for j in range(13)]
  if s[i] != '?':
    r = int(s[i]) * multiplier
    for j in range(13):
      np[(j + r) % 13] = p[j]
  else:
    for j in range(10):
      r = j * multiplier
      for k in range(13):
        np[(k + r) % 13] += p[k]
  for j in range(13):
    p[j] = np[j] % divisor
print(p[5] % divisor)
### BUGGY CODE ###

l,r = map(int, input().split())

t = []

for i in range(l,r):
    for j in range(l+1,r+1):
        t.append((i*j)%2019)

print(min(t))

### FIXED CODE ###

l,r = map(int, input().split())

t = []

if r-l >= 2019:
    print(0)
else:
    for i in range(l,r):
        for j in range(l+1,r+1):
            t.append((i*j)%2019)
    print(min(t))
### BUGGY CODE ###

h,w,m=map(int,input().split())
HW=[list(map(int,input().split())) for _ in range(m)]

MAP=[["." for _ in range(w)] for _ in range(h)]
H,W=[0 for _ in range(h)],[0 for _ in range(w)]
for i,j in HW:
    i,j=i-1,j-1
    MAP[i][j]="#"
    H[i] +=1
    W[j] +=1

max_h,max_w=max(H),max(W)
X,Y=[],[]
for i in range(h):
    if H[i]==max_h:
        X.append(i)
for i in range(w):
    if W[i]==max_w:
        Y.append(i)

flag=0
for i in X:
    for j in Y:
        if MAP[i][j]==".":
            flag=1
ans=max_w+max_h
print(ans if flag else ans-1)

### FIXED CODE ###

h,w,m=map(int,input().split())
HW=[list(map(int,input().split())) for _ in range(m)]

H,W=[0 for _ in range(h)],[0 for _ in range(w)]
for i,j in HW:
    i,j=i-1,j-1
    H[i] +=1
    W[j] +=1

max_h,max_w=max(H),max(W)
ans=max_h+max_w
cnt=H.count(max_h)*W.count(max_w)
for i,j in HW:
    if H[i-1]==max_h and W[j-1]==max_w:
        cnt -=1
print(ans if cnt!=0 else ans-1)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    n, m, k = map(int, input().split())
    parent_f = list(range(n+1))
    rank_f = [0]*(n+1)
    parent_b = list(range(n+1))
    rank_b = [0]*(n+1)
    group_f = [set() for _ in range(n+1)]
    group_b = [set() for _ in range(n+1)]
    group_index_f = [None]*(n+1)
    group_index_b = [None]*(n+1)
    friends = [set() for i in range(n+1)]
    blocks = [set() for i in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        friends[a] |= {b}
        friends[b] |= {a}
        unite(a, b, parent_f, rank_f)
    for _ in range(k):
        c, d = map(int, input().split())
        blocks[c] |= {d}
        blocks[d] |= {c}
        unite(c, d, parent_b, rank_b)
    for i in range(1, n+1):
        rf = root(i, parent_f)
        rb = root(i, parent_b)
        group_f[rf] |= {i}
        group_b[rb] |= {i}
        group_index_f[i] = rf
        group_index_b[i] = rb
    for i in range(1, n+1):
        print(len(group_f[group_index_f[i]]-friends[i]-blocks[i]-{i}))
    
    

def root(x, parent):
    if parent[x] == x:
        return x
    parent[x] = root(parent[x], parent)
    return parent[x]

def unite(x, y, parent, rank):
    x = root(x, parent)
    y = root(y, parent)
    if x != y:
        if rank[x] > rank[y]:
            parent[y] = x
        elif rank[x] < rank[y]:
            parent[x] = y
        else:
            parent[y] = x
            rank[x] += 1

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

class UnionFind:
    __slots__ = ["data"]
    
    def __init__(self, n=0):
        self.data = [-1]*(n+1)
    
    def root(self, x):
        if self.data[x] < 0:
            return x
        self.data[x] = self.root(self.data[x])
        return self.data[x]
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.data[x] < self.data[y]:
                self.data[x] += self.data[y]
                self.data[y] = x
            else:
                self.data[y] += self.data[x]
                self.data[x] = y
    
    def same(self, x, y):
        return self.root(x) == self.root(y)
    
    def size(self, x):
        return -self.data[self.root(x)]
                


def main():
    n, m, k = map(int, input().split())
    friends = [set() for _ in range(n+1)]
    blocks = [set() for _ in range(n+1)]
    uf = UnionFind(n)
    for _ in range(m):
        a, b = map(int, input().split())
        friends[a] |= {b}
        friends[b] |= {a}
        uf.unite(a, b)
    for _ in range(k):
        c, d = map(int, input().split())
        blocks[c] |= {d}
        blocks[d] |= {c}
    for i in range(1, n+1):
        nf = len(friends[i])
        nb = sum([uf.same(i, b) for b in blocks[i]])
        ans = uf.size(i) - 1 - nf - nb
        print(ans)


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

s = input()[::-1]

n = len(s)
cnt = [0] * 2019
cnt[0] = 1
total = 0
ans = 0
x = 1

for i in range(n):
    total += int(s[i]) * x
    total %= 2019
    x *= 10 % 2019
    ans += cnt[total]
    cnt[total] += 1

print(ans)


### FIXED CODE ###

s = input()[::-1]

n = len(s)
cnt = [0] * 2019
cnt[0] = 1
total = 0
ans = 0
x = 1

for i in range(n):
    total += int(s[i]) * x
    total %= 2019
    x *= 10
    x %= 2019
    ans += cnt[total]
    cnt[total] += 1

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

N = int(input())
S = []
for i in range(N):
    S.append(input())

def check(A, B):
    for i in range(N):
        for j in range(i+1, N):
            if S[i][j+B-N] != S[j][i+B-N]:
                return 0
    return 1

cnt = 0
for i in range(N):
    cnt += check(0, i)
print(cnt * N)

### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(input())

def check(S, A, B):
    for i in range(N):
        for j in range(i+1, N):
            if S[i][j] != S[j][i]:
                return 0
    return 1

cnt = 0
for i in range(N):
    cnt += check(S[i:] + S[:i], 0, i)
print(cnt * N)
### BUGGY CODE ###

def inv(x):
    return pow(x, MOD-2, MOD)

def C(n, r):
    return fact[n]*inv(fact[r])*inv(fact[n-r])
    
def g(r, c):
    res = 0
    
    for i in range(1, r+2):
        res += C(i+c, c)
        res %= MOD
    
    return res

r1, c1, r2, c2 = map(int, input().split())
MOD = 10**9+7
fact = [1]

for i in range(1, 2*10**6+100):
    fact.append(fact[-1]*i%MOD)

print((g(r2, c2)-g(r2, c1-1)-g(r1-1, c2)+g(r1-1, c1-1))%MOD)

### FIXED CODE ###

def C(n, r):
    return fact[n]*inv_table[r]*inv_table[n-r]
    
def g(r, c):
    res = 0
    
    for i in range(1, r+2):
        res += C(i+c, c)
        res %= MOD
    
    return res

r1, c1, r2, c2 = map(int, input().split())
MOD = 10**9+7
fact = [1]

for i in range(1, 2*10**6+100):
    fact.append(fact[-1]*i%MOD)
    
inv_table = [pow(fact[-1], MOD-2, MOD)]

for i in range(1, 2*10**6+100)[::-1]:
    inv_table.append(inv_table[-1]*i%MOD)

inv_table.reverse()

print((g(r2, c2)-g(r2, c1-1)-g(r1-1, c2)+g(r1-1, c1-1))%MOD)
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [0] * (N+1)
dp[0] = 1
e = 1e9 + 7
for i in range(1, N+1):
    if i not in A:
        if i == 1:
            dp[i] = 1
            continue
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % e
print(int(dp[N]))

### FIXED CODE ###

n, m = map(int, input().split())
mod = 1e+9+7
dp = [0]*(n+1)
dp[0] = 1
isPass = [1]*(n+1)
for _ in range(m):
    a = int(input())
    isPass[a] = 0
for i in range(n):
    for j in range(i+1, min(n, i+2)+1):
        if isPass[j]:
            dp[j] += dp[i]
            dp[j] %= mod
print(int(dp[n]))
### BUGGY CODE ###

n,a,b = [int(x) for x in input().split()]
mod = 10**9 + 7
def comb(x,y):
    child = 1
    mother = 1
    for i in range(y):
        child *= (x-i)%mod
        mother *= (i+1)%mod
    return child * pow(mother,mod-2,mod) % mod
ans = pow(2,n,mod) - 1
ans -= comb(n,a)
ans %= mod
ans -= comb(n,b)
ans %= mod
print(ans)

### FIXED CODE ###

n,a,b = [int(x) for x in input().split()]
mod = 10**9 + 7
def comb(x,y):
    child = 1
    mother = 1
    for i in range(y):
        child = child * (x-i)%mod
        mother = mother * (i+1)%mod
    return child * pow(mother,mod-2,mod) % mod
ans = pow(2,n,mod) - 1
ans -= comb(n,a)
ans %= mod
ans -= comb(n,b)
ans %= mod
print(ans)