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

n,a,b=map(int,input().split())
mod=10**9+7

def pow2(n,base):
    if n==1:return base
    if n%2==0:return pow2(n//2,base)**2%mod
    else:return base*pow2(n//2,base)**2%mod

def fac(n,a):
    ans=1
    for i in range(n,n-a,-1):
        ans*=i
        ans%=mod
    return ans

def inv_fac(n):
    ans=1
    for i in range(1,n+1):
        ans*=pow2(mod-2,i)
        ans%=mod
    return ans



ans=pow2(n,2)-fac(n,a)*inv_fac(a)-fac(n,b)*inv_fac(b)
print(ans%mod-1)

### FIXED CODE ###

n,a,b=map(int,input().split())
mod=10**9+7


def fac(n,a):
    ans=1
    for i in range(n,n-a,-1):
        ans*=i
        ans%=mod
    return ans%mod

def inv_fac(n):
    ans=pow(fac(n,n-1),mod-2,mod)
    return ans%mod



ans=pow(2,n,mod)-fac(n,a)*inv_fac(a)-fac(n,b)*inv_fac(b)
print(ans%mod-1)
### BUGGY CODE ###

import math
from functools import reduce

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

k = int(input())
ans = 0
a = [i + 1 for i in range(k)]
b = [i + 1 for i in range(k)]
c = [i + 1 for i in range(k)]

for x in a:
    for y in b:
        for z in c:
            ans += gcd(x, y, z)

print(ans)

### FIXED CODE ###

import math
from functools import reduce

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

k = int(input())
ans = 0
a = [i + 1 for i in range(k)]
b = [i + 1 for i in range(k)]
c = [i + 1 for i in range(k)]

for x in a:
    for y in b:
        for z in c:
            ans += gcd(x, y, z)

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

import numpy as np

H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(map(int, list(input()))))
S = np.array(S)

if S.sum() <= K:
    print(0)
    exit(0)

def satisfy(left, right, S2):
    global K
    top = 0
    for row in S2:
        if row[left:(right + 1)].sum() > K:
            return False
    return True

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(horizons):
    global W, S
    answer = sum(horizons)
    left = 0
    right = 0
    # greedyに縦線を引いていく
    # TODO: 横線で分けた後のそれぞれのブロックで集計
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0))
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0))
    S2 = np.array(S2)
    # print(S2)
    # print('hoge')
    while right <= W - 1:
        if not satisfy(left, right, S2):
            # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
            if left == right:
                return -1
            left = right
            answer += 1
        else:
            right += 1
    return answer

answer = (H - 1) * (W - 1)

# result = greedy([0, 1, 0])

for i in range(0, 2 ** (H - 1)):
    horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
    result = greedy(horizons)
    if result > 0 and result < answer:
        answer = result

print(answer)


### FIXED CODE ###

import numpy as np

def main():
    H, W, K = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    if S.sum() <= K:
        print(0)
        exit(0)
    answer = float('INF')
    for i in range(0, 2 ** (H - 1)):
        horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
        result = greedy(W, S, K, horizons, answer)
        answer = min(answer, result)
    print(answer)

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(W, S, K, horizons, current_answer):
    answer = sum(horizons)
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0).tolist())
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0).tolist())
    # ブロック毎の累積和を計算する
    h = len(S2)
    partial_sums = [0] * h
    for right in range(W):
        current = [0] * h
        for idx in range(h):
            current[idx] = S2[idx][right]
            partial_sums[idx] += S2[idx][right]
        # 1列に含むホワイトチョコの数がkより多い場合
        if max(current) > K:
            return float('INF')
        # 無理な(ブロックの中のホワイトチョコの数をk以下にできない)場合
        if max(partial_sums) > K:
            answer += 1
            if answer >= current_answer:
                return float('INF')
            partial_sums = current
    return answer

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

K = int(input())
import math
b_list=[]
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            a=math.gcd(i,j)
            b=math.gcd(a,k)
            b_list.append(b)
print(sum(b_list))

### FIXED CODE ###

K = int(input())
import math
b_list=[]
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            a=math.gcd(i,j)
            b=math.gcd(a,k)
            b_list.append(b)
print(sum(b_list))
### BUGGY CODE ###

def main():
    from collections import deque
    import sys
    input = sys.stdin.readline
    n = int(input())
    l = list(map(int,input().split()))
    check = [[1]*n for i in range(n)]
    d = [[float("INF")]*n for i in range(n)]

    for i in range((n+1)//2):
        for j in range(i,n-i):
            d[i][j] = i
            d[-1-i][j] = i
        for j in range(i,n-i):
            d[j][i] = i
            d[j][-1-i] = i
    def solve(l):
        ans = 0
        for t in l:
            t -=1
            x = t//n
            y = t%n
            check[x][y] = 0
            ans += d[x][y]
            q = deque([])
            q.append((x,y))
            while q:
                bx,by = q.popleft()

                if bx != 0:
                    if d[bx-1][by] > d[bx][by]+check[bx][by]:
                        d[bx-1][by] = d[bx][by]+check[bx][by]
                        q.append((bx-1,by))
                if bx != n-1:
                    if d[bx+1][by] > d[bx][by]+check[bx][by]:
                        d[bx+1][by] = d[bx][by]+check[bx][by]
                        q.append((bx+1,by))
                if by != 0:
                    if d[bx][by-1] > d[bx][by]+check[bx][by]:
                        d[bx][by-1] = d[bx][by]+check[bx][by]
                        q.append((bx,by-1))
                if by != n-1:
                    if d[bx][by+1] > d[bx][by]+check[bx][by]:
                        d[bx][by+1] = d[bx][by]+check[bx][by]
                        q.append((bx,by+1))  
        return ans

    
    print(solve(l))

if __name__ =="__main__":
    main()

### FIXED CODE ###

def main():
    from collections import deque
    import sys
    input = sys.stdin.readline
    n = int(input())
    l = list(map(int,input().split()))
    check = [[1]*n for i in range(n)]
    d = [[float("INF")]*n for i in range(n)]

    for i in range((n+1)//2):
        for j in range(i,n-i):
            d[i][j] = i
            d[-1-i][j] = i
        for j in range(i,n-i):
            d[j][i] = i
            d[j][-1-i] = i
    def solve(l):
        ans = 0
        for t in l:
            t -=1
            x = t//n
            y = t%n
            check[x][y] = 0
            ans += d[x][y]
            q = deque([])
            q.append((x,y,d[x][y]))
            while q:
                bx,by,z = q.popleft()

                if bx != 0:
                    if d[bx-1][by] > z:
                        d[bx-1][by] = z
                        q.append((bx-1,by,z+check[bx-1][by]))
                if bx != n-1:
                    if d[bx+1][by] > z:
                        d[bx+1][by] = z
                        q.append((bx+1,by,z+check[bx+1][by]))
                if by != 0:
                    if d[bx][by-1] > z:
                        d[bx][by-1] = z
                        q.append((bx,by-1,z+check[bx][by-1]))
                if by != n-1:
                    if d[bx][by+1] > z:
                        d[bx][by+1] = z
                        q.append((bx,by+1,z+check[bx][by+1]))  
        return ans

    
    print(solve(l))

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

N = int(input())
A = list(map(int,input().split()))
s =0
M = 10**9 +7
for i in range(N-1):
  s += (A[i] * sum(A[i+1:]))%M
print(s%M)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
s =0
M = 10**9 +7
As = sum(A)
for i in range(N-1):
  As = As - A[i]
  s += (A[i] * As)%M
print(s%M)
### BUGGY CODE ###

N = int(input())

nl = map(int,input().split())

ans=1
for i in nl:
  ans = ans * i

lim = 10**18

if ans > lim:
  print(-1)
else:
  print(ans)

### FIXED CODE ###


def main():
  N = int(input())
  nl = list(map(int,input().split()))

  if 0 in nl:
    print(0)
    return

  ans=1
  lim=10**18

  for i in nl:
    ans *= i
    if ans>lim:
      print(-1)
      return
    
  print(ans)
  
main()
### BUGGY CODE ###

import math
N = int(input())
A = list(map(int,input().split()))
b = [[0]*60 for i in range(2)]
#max_a = math.ceil(math.log(max(A),2))
max_a = 60
for i in range(N):
    x = A[i]
    j = 0
    for j in range(max_a):
        b[x % 2][j] += 1
        x //= 2

x = 0
for i in range(max_a):
    x += b[0][i] * b[1][i] * 2**i
    x %= 10 ** 9 + 7

print (x)

### FIXED CODE ###

import math
N = int(input())
A = list(map(int,input().split()))
b = [[0]*60 for i in range(2)]
#max_a = math.ceil(math.log(max(A),2))
max_a = 60
for i in range(N):
    x = A[i]
    j = 0
    for j in range(max_a):
        b[x % 2][j] += 1
        x //= 2

x = 0
for i in range(max_a):
    x += b[0][i] * b[1][i] * 2**i
    x %= 10 ** 9 + 7

print (x)
### BUGGY CODE ###

n = int(raw_input())

i, c = 0, 0

while(i<n):
    a = int(raw_input())

    if a==2:
        c+=1

    for x in xrange(2, a):
        if a%x==0:
            break

        if a-1==x and a%x!=0:
            c+=1

    i+=1
print c

### FIXED CODE ###

import math

n = int(raw_input())

def isPrime(a):
    if a==2 or a==3:
        return 1
    if a<2 or a%2==0:
        return 0
        
    i = int(math.sqrt(a))+1
    for x in xrange(3,i):
        if a%x==0:
            return 0
    return 1

cnt = 0
for _ in xrange(n):
    a = int(raw_input())
    cnt += isPrime(a)
print cnt
### BUGGY CODE ###

n = int(input())
ans=1
for i in range(1,n+1):
       ans=(ans*i)
ans=ans%1000000007
print(ans)

### FIXED CODE ###

x = int(raw_input())
a = 1L
for i in range(1, x+1):
 a = a * i
 a = a % 1000000007
print(a)
### BUGGY CODE ###

N, K = map(int, input().split())
d = []

for i in range(N):
    a, b = map(int, input().split())
    for j in range(b):
        d.append(a)
d.sort()

print(d[K-1])

### FIXED CODE ###

import bisect

N, K = map(int, input().split())
d = []


for i in range(N):
    a, b = map(int, input().split())
    d.append([a,b])

d.sort()

l = [0] * N
l[0] = d[0][1]

for i in range(1, N):
    l[i] = d[i][1]+ l[i-1]

pos = bisect.bisect_left(l, K)
print(d[pos][0])
### BUGGY CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = list(map(int, args[1].split()))

    cur = A
    for _ in range(k):
        prev = cur.copy()
        cur = [0]*n
        for x, p in enumerate(prev):
            cur[max(0, x-p)] += 1
            if x+p+1 < n:
                cur[x+p+1] -= 1

        satulated = True
        for i in range(1, n):
            cur[i] += cur[i-1]
            satulated &= cur[i] == n
        if satulated:
            break

    return ' '.join(map(str, cur))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    A = list(map(int, args[1].split()))

    cur = A
    for _ in range(k):
        prev = cur.copy()
        cur = [0]*n
        for x, p in enumerate(prev):
            cur[max(0, x-p)] += 1
            if x+p+1 < n:
                cur[x+p+1] -= 1

        satulated = True
        for i in range(1, n):
            cur[i] += cur[i-1]
            satulated &= cur[i] == n
        if satulated:
            break

    return ' '.join(map(str, cur))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

from collections import Counter

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

retval=0

Rs=[0]
Gs=[0]
Bs=[0]
for s in S[::-1]:
    if s=='R':
        Rs.append(Rs[-1]+1)
        Gs.append(Gs[-1])
        Bs.append(Bs[-1])
    elif s=='G':
        Rs.append(Rs[-1])
        Gs.append(Gs[-1]+1)
        Bs.append(Bs[-1])
    else:
        Rs.append(Rs[-1])
        Gs.append(Gs[-1])
        Bs.append(Bs[-1]+1)



for i in range(N):
    for j in range(i+1,N):
        if S[i]==S[j]:
            continue

        rest=list(set(['R','G','B'])-set([S[i],S[j]]))[0]

        if rest=='R':
            retval+=Rs[N-j]
        elif rest=='G':
            retval+=Gs[N-j]
        else:
            retval+=Bs[N-j]
        if 2*j-i<N and S[j+(j-i)]==rest:
            retval-=1

print(retval)


### FIXED CODE ###

from collections import Counter

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

dup=0
RGB=set(('R','G','B'))

for width in range(N//2+10):
    for i in range(N):
        try:
            if set((S[i],S[i+width],S[i+width*2]))==RGB:
                dup+=1
        except IndexError:
            break

c=Counter(S)
retval=c['R']*c['G']*c['B']-dup
print(retval)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 標準入力を取得
N, X, M = list(map(int, input().split()))

# 求解処理


def f(x: int, m: int) -> int:
    return x**2 % m


A = [X]
loop_start_index = 0
while True:
    A_next = f(A[-1], M)
    if A_next in A:
        loop_start_index = A.index(A_next)
        break
    else:
        A.append(A_next)

loop_length = len(A) - loop_start_index
loop_cnt = (N - loop_start_index) // loop_length
loop_res = (N - loop_start_index) % loop_length
ans = sum(A[:loop_start_index]) + loop_cnt * sum(A[loop_start_index:]
                                                 ) + sum(A[loop_start_index: loop_start_index + loop_res])

# 結果出力
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 標準入力を取得
N, X, M = list(map(int, input().split()))

# 求解処理
s = {X}
l = [X]
i = 0
while True:
    a = l[-1]**2 % M
    if a in s:
        i = l.index(a)
        break
    else:
        s.add(a)
        l.append(a)

loop_length = len(l) - i
loop_cnt = (N - i) // loop_length
loop_res = (N - i) % loop_length
ans = sum(l[:i]) + loop_cnt * sum(l[i:]) + sum(l[i: i + loop_res])

# 結果出力
print(ans)
### BUGGY CODE ###

# dp[i][j]=(区間[i,j]が残っているとき次の手番の得点-そうじゃない人の得点)
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
INF=-10**14
dp=[[-1]*n for i in range(n)]
def memo(i,j):
    if dp[i][j]>=0:
        return dp[i][j]
    if i==j:
        dp[i][j]=a[i]
    else:
        dp[i][j]=max(a[i]-memo(i+1,j),a[j]-memo(i,j-1))
    return dp[i][j]
print(memo(0,n-1))

### FIXED CODE ###

# dp[j][i]=(区間[i,j]が残っているとき次の手番の得点-そうじゃない人の得点)
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
INF=-10**14
dp=[[0]*(i+1) for i in range(n)]
for i in range(n):
    dp[i][i]=a[i]
for i in range(1,n):
    for j in range(i-1,-1,-1):
        dp[i][j]=max(a[i]-dp[i-1][j],a[j]-dp[i][j+1])
print(dp[-1][0])
### BUGGY CODE ###

def solve():
    N = int(input())
    Ss = input()
    Q = int(input())
    ks = list(map(int, input().split()))

    anss = []
    for k in ks:
        numD = numM = numDM = numDMC = 0
        for i in range(N):
            S = Ss[i]
            if S == 'D':
                numD += 1
            elif S == 'M':
                numM += 1
                numDM += numD
            elif S == 'C':
                numDMC += numDM

            if i >= k-1:
                S = Ss[i-k+1]
                if S == 'D':
                    numD -= 1
                    numDM -= numM
                elif S == 'M':
                    numM -= 1

        anss.append(numDMC)

    print('\n'.join(map(str, anss)))


solve()


### FIXED CODE ###

def solve():
    N = int(input())
    Ss = input()
    Q = int(input())
    ks = list(map(int, input().split()))

    anss = []
    for k in ks:
        numD = numM = numDM = numDMC = 0
        for i in range(N):
            S = Ss[i]
            if S == 'D':
                numD += 1
            elif S == 'M':
                numM += 1
                numDM += numD
            elif S == 'C':
                numDMC += numDM

            if i >= k-1:
                S = Ss[i-k+1]
                if S == 'D':
                    numD -= 1
                    numDM -= numM
                elif S == 'M':
                    numM -= 1

        anss.append(numDMC)

    print('\n'.join(map(str, anss)))


solve()
### BUGGY CODE ###

from collections import deque

n = int(input())
AA = [deque(list(map(int, input().split()))) for _ in range(n)]
max_n = n * (n - 1) // 2
cnt = 0
ans = -1
shuryo = False
for d in range(1, n * n):
    used = [False] * (n)
    for i in range(n):
        if used[i] is True:
            continue
        if not AA[i]:
            continue
        aite = AA[i][0] - 1
        if used[aite] is True:
            continue
        if not AA[aite]:
            continue
        if AA[aite][0] - 1 == i:
            AA[i].popleft()
            AA[aite].popleft()
            used[aite] = True
            used[i] = True
            cnt += 1

        if cnt == max_n:
            shuryo = True
            break

    if shuryo:
        break
if shuryo:
    ans = d
print(ans)


### FIXED CODE ###

from collections import deque

n = int(input())
AA = [deque(list(map(int, input().split()))) for _ in range(n)]

graph = [[] for _ in range(n * n)]


def calc(i, j):
    if j > i:
        i, j = j, i
    return i * n + j


to = [0] * (n * n)
for i in range(n):
    for j in range(n - 2):
        u = calc(i, AA[i][j] - 1)
        v = calc(i, AA[i][j + 1] - 1)
        graph[u].append(v)
        to[v] += 1
start = []
for i in range(n * n):
    if to[i] == 0:
        start.append(i)


def topological_sort(edge_num, graph, start, to):
    topo = []
    cnt = 0
    stack = deque(start)
    while stack:
        v = stack.popleft()
        topo.append(v)
        cnt += 1
        for u in graph[v]:
            to[u] -= 1
            if to[u] == 0:
                stack.append(u)
    return topo, cnt


topo, cnt = topological_sort(n * n, graph, start, to)
if cnt != n * n:
    print(-1)
    exit()
day = [1] * (n * n)
for i in topo:
    for j in graph[i]:
        day[j] = day[i] + 1
print(max(day))
### BUGGY CODE ###

import numpy as np

N, M, Q = map(int, input().split())
d = np.zeros([N+1, N+1], np.int32)

for _ in range(M):
	tl,tr = map(int, input().split())
	d[N-tl,tr] += 1

d = np.add.accumulate(d, axis = 1)
d = np.add.accumulate(d)

ans = []
for _ in range(Q):
	tp,tq = map(int, input().split())

	ans.append(d[N-tp,tq])

for a in ans:
	print(a)

### FIXED CODE ###

import numpy as np
import sys

N, M, Q = map(int, input().split())

I = sys.stdin.read().split()

L,R = np.array(I[:2*M], np.int32).reshape([2,-1], order='F')
p,q = np.array(I[2*M:], np.int32).reshape(2,-1, order='F')
d = np.zeros([N+1, N+1], np.int32)

d = np.zeros([1+N, 1+N], np.int32)
np.add.at(d, (N-L,R), 1)

d = np.add.accumulate(d, axis = 1)
d = np.add.accumulate(d)

ans = d[N-p,q]

for a in ans:
	print(a)
### BUGGY CODE ###

n = int(input())
l = input().split()

l = list(l)
for i in range(n):
	l[i] = int(l[i])
l.sort()
count = 0
#a<b+c, a>b-c, a>c-b
for a in range(n):
	for b in range(a+1,n):
		for c in range(b+1,n):
			if l[a]<l[b]+l[c]:
				if l[b]<l[c]+l[a]:
					if l[c]<l[a]+l[b]:
						count += 1
					else:
						break

print(count)

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int,input().split()))
l.sort()

ans = 0

#a<b+c, a>b-c, a>c-b
for a in range(n-2):
	for b in range(a+1,n-1):
		index = bisect.bisect_left(l,l[a]+l[b])
		ans += index - (b+1)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [i for i in range(1,N+1)]
C = zip(A, B)
C = sorted(C, reverse = True)
A, B = zip(*C)
dp = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(N):
    for j in range(i + 2):
        if j == 0:
            dp[0][i-j+1] = dp[0][i-j] + A[i] * (N - (i - j) - B[i])
        elif j == i+1:
            dp[j][0] = dp[j-1][0] + A[i] * (B[i] - j)
        else:
            dp[j][i-j+1] = max(dp[j][i-j] + A[i] * (N - (i - j) - B[i]), dp[j-1][i-j+1] + A[i] * (B[i] - j))
ans = 0
for i in range(N+1):
    ans = max(ans, dp[i][N-i])
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [i for i in range(1,N+1)]
C = zip(A, B)
C = sorted(C, reverse = True)
A, B = zip(*C)
dp = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(N):
    for j in range(i + 2):
        if j == 0:
            dp[0][i-j+1] = dp[0][i-j] + A[i] * (N - (i - j) - B[i])
        elif j == i+1:
            dp[j][0] = dp[j-1][0] + A[i] * (B[i] - j)
        else:
            dp[j][i-j+1] = max(dp[j][i-j] + A[i] * (N - (i - j) - B[i]), dp[j-1][i-j+1] + A[i] * (B[i] - j))
ans = 0
for i in range(N+1):
    ans = max(ans, dp[i][N-i])
print(ans)
### BUGGY CODE ###

a, b, c, k = map(int, input().split())

suma = 0

for i in range(k):
    if a > 0:
        a = a - 1
        suma += 1
    elif b > 0:
        b = b - 1
    elif c > 0:
        c = c - 1
        suma -= 1
print(suma)


### FIXED CODE ###

a, b, c, k = map(int, input().split())

suma = 0


if k > a:
    if k > a + b:
        if k == a + b + c:
            print(a - c)
        else:
            k = k - (a + b)
            print(a-k)
    else:
        print(a)
else:
    print(k)
### BUGGY CODE ###

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

minimum=1
count=0
while a:
   if(minimum<a[0]):
       if a[0]%minimum:
           count+= a[0]//minimum
           a[0]-= a[0]//minimum*minimum
       else :
           count+= (a[0]//minimum-1)
           a[0]= 1
   else:
       minimum=max(minimum,a[0]+1)
       a.pop(0)
print(count)


### FIXED CODE ###

N=int(input())
a=[0]*N
for i in range(N):
    a[i]=int(input())

minimum=2
count=a[0]-1
a.pop(0)
for i in  a:
   if(minimum<i):
       if i%minimum:
           count+= i//minimum
       else :
           count+= (i//minimum-1)
   else:
       minimum=max(minimum,i+1)
print(count)
### BUGGY CODE ###

s ="0"+ input()

nagasa=len(s)
ans=0

import itertools
for seq in itertools.combinations(range(1,nagasa+1),2):
    num=int(s[seq[0]:seq[1]])
    if num%2019==0:
        ans+=1

print(ans)

### FIXED CODE ###

s = input()

ans=0
s=s[::-1]
t=1
ketame=0
amari10=1
kosuu=[1]+[0]*2020
for i in s:
    ketame=(ketame+(int(i)*amari10)%2019)%2019
    amari10*=10
    amari10%=2019
    kosuu[ketame]+=1

for i in range(len(kosuu)):
    if kosuu[i]>0:
        ans+=kosuu[i]*(kosuu[i]-1)/2
    
print(int(ans))