Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append([v-1,a,b])
    g[v-1].append([u-1,a,b])
  import heapq,math
  dp=[[math.inf]*(100*51)for _ in range(n)]
  kakutei=[[0]*(100*51)for _ in range(n)]
  dp[0][min(s,100*51-1)]=0
  todo=[[0,0,min(s,100*51-1)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[math.inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    if kakutei[v][i+a]==0:
      j=min(100*51-1,i+c)
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  max_s=50*50
  dp=[[inf]*(max_s+1)for _ in range(n)]
  kakutei=[[0]*(max_s+1)for _ in range(n)]
  dp[0][min(s,max_s)]=0
  todo=[[0,0,min(s,max_s)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(max_s,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()
n, x = map(int, input().split())
l = list(map(int, input().split()))

sum = 0
ans = 0

for i in range(n+1):
    if sum + l[ans] > x:
        break
    sum += l[ans]
    ans += 1

print(ans+1)

### FIXED CODE ###

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

sum = 0
ans = 0

for i in range(n):
    if sum + l[ans] > x:
        break
    sum += l[ans]
    ans += 1

print(ans+1)
N,M=map(int,input().split())

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

D=[]
for i in range(M):

    d=list(map(int,input().split()))

    D.append(d)

D.sort(key=lambda x:x[1])


k=0

for j in range(M):
    l=k
    for i in range(D[M-j-1][0]):

        if D[M-j-1][1] > a[k]:
            a[k]=D[M-j-1][1]
            k=k+1

    if l==k:
        break
print(sum(a))



### FIXED CODE ###

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

a=list(map(int,input().split()))
a=sorted(a)
a.append(0)
D=[]
for i in range(M):

    d=list(map(int,input().split()))

    D.append(d)

D.sort(key=lambda x:x[1])


k=0

for j in range(M):
    l=k
    for i in range(D[M-j-1][0]):
        q=max(M-j-1,0)
        if D[q][1] > a[k] and k!=N:
            a[k]=D[q][1]
            k=k+1
        else:
            k=k

        if l==k:
            break

    if l==k:
        break



print(sum(a)-a[N])
A,B = (input().split())
A = int(A)
B = int(B)
roads = []
for i in range(A):
    a, b = input().split()
    a = int(a)
    if t in range(1, B + 1):
        roads.append((int(a), b))

if len(roads) == 0:
    print("TLE")
else:
    roads.sort()
    print(roads[0][0])

### FIXED CODE ###

n, t = [int(x) for x in input().split()]
result = 1001
for i in range(n):
    a, b = [int(x) for x in input().split()]
    if b <= t and result >= a:
        result = a
if result < 1001:
    print(result)
else:
    print("TLE")
#!/usr/bin/env python
# -*- coding: utf-8 -*-

M, D = map(int, input().split())

count=0
for i in range(4, M+1):
    for j in range(22, D+1):
        str_j = str(j)
        if str_j[0] <= 1:
            continue
        if (int(str_j[0]) * int(str_j[1])) == i:
            count += 1
print(count)


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

M, D = map(int, input().split())

count=0
for i in range(4, M+1):
    for j in range(22, D+1):
        str_j = str(j)
        if int(str_j[1]) <= 1:
            continue
        if (int(str_j[0]) * int(str_j[1])) == i:
            count += 1
print(count)
n = int(input())
lst = []
for i in range(n):
  s, p = input().split()
  p = int(p)
  lst.append((s, p, i+1))
lst_sorted = sorted(lst, key:lambda x: (x[0], -x[1], x[2]))
for _, _, num in lst_sorted:
  print(num)


### FIXED CODE ###

n = int(input())
lst = []
for i in range(n):
  s, p = input().split()
  p = int(p)
  lst.append((s, p, i+1))
lst_sorted = sorted(lst, key=lambda x: (x[0], -x[1], x[2]))
for _, _, num in lst_sorted:
  print(num)
S = list(input())
r = S[0]
for i in range(4):
 S.remove(r)
if S[0] == S[1] and len(S) == 2:
 print('Yes')
else:
 print('NO')

### FIXED CODE ###

S = set(input())
print('Yes' if len(S) == 2 else 'No')
a = int(input())
op = input()
b = int(input())
print(a + b if op == "+" else a - b)

### FIXED CODE ###

a, op, b = map(str, input().split())
a = int(a)
b = int(b)
print(a + b if op == "+" else a - b)
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a, b = [0], [0]
for i in range(N):
a.append(a[i] + A[i])
for i in range(M):
b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
a[i] > K:
break
while b[j] > K - a[i]:
j -= 1
ans = max(ans, i + j)
print(ans)

### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
	a.append(a[i] + A[i])
for i in range(M):
	b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
	if a[i] > K:
		break
	while b[j] > K - a[i]:
		j -= 1
	ans = max(ans, i + j)
print(ans)
k = int(input())
#n, k = list(map(int, input().split()))
#a = list(map(int, input().split()))
q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
for i in range(k):
    x = q.popleft()
    a = 10*x+(x % 10)
    if x % 10 != 0:
        q.append(a-1)
    q.append(a)
    if x % 10 != 9:
        q.append(a+1)

print(x)

### FIXED CODE ###

from collections import deque
k = int(input())
q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
for i in range(k):
    x = q.popleft()
    a = 10*x+(x % 10)
    if x % 10 != 0:
        q.append(a-1)
    q.append(a)
    if x % 10 != 9:
        q.append(a+1)

print(x)
from decimal import *
getcontext().prec = ２8
a, b ,c = map(int, input().split())
if Decimal(a).sqrt() + Decimal(b).sqrt() < Decimal(c).sqrt():
    print('Yes')
else:
    print('No')

### FIXED CODE ###

from decimal import *
getcontext().prec = 50
a, b ,c = map(int, input().split())
if Decimal(a).sqrt() + Decimal(b).sqrt() < Decimal(c).sqrt():
    print('Yes')
else:
    print('No')
while True:
 a =int(input())
 op =raw_input()
 b =int(input())
 if(op=='+'):
  print a+b
 elif(op=='-'):
  print a-b
 elif(op=='*'):
  print a*b
 elif(op=='/'):
  print a/b
 else:
  break

### FIXED CODE ###

while True:
 a,op,b = map(str,raw_input().split())
 a=int(a)
 b=int(b)

 if(op=='?'):
  break
 if(op=='+'):
  print a+b
 elif(op=='-'):
  print a-b
 elif(op=='*'):
  print a*b
 elif(op=='/'):
  print a/b
inputs = input()

x = list(inputs)

flag = False
for i in range(len(x) - 1):
    if x[i] == 'A' and x[i+1] == 'C'
        flag = True

if flag:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

inputs = input()

x = list(inputs)

flag = False
for i in range(len(x) - 1):
    if x[i] == 'A' and x[i+1] == 'C':
        flag = True

if flag:
    print('Yes')
else:
    print('No')
a, b =  (int(x) for x in input.split())
 
if a > 9 or b > 9 :
  print('-1')
else :
  print(a*b)

### FIXED CODE ###

a, b =  (int(x) for x in input().split())
if a > 9 or b > 9 :
  print('-1')
else :
  print(a*b)
n,m = map(int,input().split())
sc = []
for i in range(m):
  sc.append(list(map(int,input().split())))

sc1 = []
sc2 = []
sc3 = []
for i in sc:
  if i[0]==1:
    sc1.append(i[1])
  elif i[0]==2:
    sc2.append(i[1])
  else:
    sc3.append(i[1])

if len(set(sc1)) > 1 or len(set(sc2)) > 1 or len(set(sc3)) > 1:
  print('-1')
  exit()
elif len(set(sc1)) <= 1 and list(set(sc1))[0] == 0:
  print('-1')
  exit()


c1 = list(set(sc1))
c2 = list(set(sc2))
c3 = list(set(sc3))

if c1:
  c1_ans = c1[0]
else:
  c1_ans = 1
if c2:
  c2_ans = c2[0]
else:
  c2_ans = 0
if c3:
  c3_ans = c3[0]
else:
  c3_ans = 0

print(100*c1_ans + 100*c2_ans + c3_ans)

### FIXED CODE ###

n,m = map(int,input().split())
c1 = []
c2 = []
c3 = []
for i in range(m):
  sc = list(map(int,input().split()))
  if sc[0] == 1:
    c1.append(sc[1])
  elif sc[0] == 2:
    c2.append(sc[1])
  else:
    c3.append(sc[1])

if len(set(c1)) <= 1 and len(set(c2)) <= 1 and len(set(c3)) <= 1:
  if 0 in list(set(c1)):
    if n == 1 and len(set(c1)) == 1 and len(set(c2)) == 0 and len(set(c3)) == 0:
      print('0')
      exit()
    else:
      print('-1')
      exit()
  elif not c1 and not c2 and not c3:
    if n == 1:
      print('0')
      exit()
    elif n == 2:
      print('10')
      exit()
    else:
      print('100')
      exit()
  else:
    if list(set(c1)):
      ans_c1 = list(set(c1))[0]
    else:
      ans_c1 = 1
    if list(set(c2)):
      ans_c2 = list(set(c2))[0]
    else:
      ans_c2 = 0
    if list(set(c3)):
      ans_c3 = list(set(c3))[0]
    else:
      ans_c3 = 0
else:
  print('-1')
  exit()

if n == 1:
  print(ans_c1)
elif n == 2:
  print(ans_c1*10 + ans_c2)
else:
  print(ans_c1*100 + ans_c2*10 + ans_c3)
N = int(input())
L = [0 for i in range(9)]
S = list(map(int, input().split()))
for i in range(N):
  L[S[i] // 400] += 1
Z, M, m = 0, 0, 0
for i in range(8):
  if L[i] == 0:
    Z += 1
  else:
    M += 1
    m += 1
M += min(Z, L[8])
print(m, M)

### FIXED CODE ###

N = int(input())
L = [0 for i in range(9)]
S = list(map(int, input().split()))
for i in range(N):
  p = S[i] // 400
  if p <= 7:
    L[p] += 1
  else:
    L[8] += 1
Z, M, m = 0, 0, 0
for i in range(8):
  if L[i] == 0:
    Z += 1
  else:
    M += 1
    m += 1
M += L[8]
if m == 0 and L[8] != 0:
  m = 1
print(m, M)
A1, A2, A3 = input().split(' ')
if A1 + A2 + A3 >= 22:
    return 'bust'
else:
    return 'win'

### FIXED CODE ###

A1, A2, A3 = [int(x) for x in input().split(' ')]
if A1 + A2 + A3 >= 22:
    print('bust')
else:
    print('win')
def solve(n, m, A, BC):
    A.sort()
    BC.sort(key=lambda bc: -bc[1])
    i = 0
    finished = False
    for b, c in BC:
        for j in range(b):
            if A[i + j] < c:
                A[i + j] = c
            else:
                finished = True
                break
        if finished:
            break
        i += b
    return sum(A)

_n, _m = map(int, input().split())
_A = list(map(int, input().split()))
_BC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _A, _BC))

### FIXED CODE ###

def solve(n, m, A, BC):
    # https://atcoder.jp/contests/abc127/tasks/abc127_d
    A.sort()
    BC.sort(key=lambda bc: -bc[1])
    i = 0
    finished = False
    for b, c in BC:
        for j in range(b):
            if i + j >= n:
                finished = True
                break
            if A[i + j] < c:
                A[i + j] = c
            else:
                finished = True
                break
        if finished:
            break
        i += b
    return sum(A)

_n, _m = map(int, input().split())
_A = list(map(int, input().split()))
_BC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _A, _BC))
# -*- coding: utf-8 -*-
from math import pi

r = float(input())
area = r**2*pi
circumference = r*pi*2
              
print("{:.6f} {.6f}".format(area, circumference))

### FIXED CODE ###

# -*- coding: utf-8 -*-
from math import pi

r = float(input())
area = r**2*pi
circumference = r*pi*2
              
print("{:.6f} {:.6f}".format(area, circumference))
t = int(input())

h = t//3600
m = (t%3600)//60
s = t - h*3600 - m*60

print(h+':'+m+':'+s)


### FIXED CODE ###

t = int(input())

h = t//3600
m = (t%3600)//60
s = t - h*3600 - m*60

print(str(h) + ':' + str(m) + ':' + str(s))
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10**9 + 7

N,K = map(int,readline().split())
AB = map(int,read().split())

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

fact,fact_inv = make_fact(K+10,MOD)

graph = [[] for _ in range(N+1)]
for a,b in zip(AB,AB):
    graph[a].append(b)
    graph[b].append(a)

# 次数1の頂点を根とする
deg = [len(x) for x in graph]
for i,x in enumerate(deg):
    if x == 1:
        break
root = i

parent = [0] * (N+1)
ts = [root]
stack = [root]
while stack:
    x = stack.pop()
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
        ts.append(y)

perm = np.zeros(N+K+10,np.int64)
perm[:K-1] = fact[K-2] * fact_inv[K-2::-1] % MOD

dp = [1] * (N+1)
for v in ts[::-1]:
    if v == root:
        break
    d = deg[v]
    dp[v] *= perm[d-1]; dp[v] %= MOD
    p = parent[v]
    dp[p] *= dp[v]; dp[p] %= MOD

x = dp[root]
x *= K*(K-1)
x %= MOD
print(x)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

edge = [[] for _ in range(N)]
for _ in range(N-1):
  a,b = map(lambda x: int(x) - 1,input().split())
  edge[a].append(b)
  edge[b].append(a)
deg = [len(E) for E in edge]
  
U = 10 ** 5 + 100
fact = [1] * (U+1)
fact_inv = [1] * (U+1)
for n in range(1,U+1):
  fact[n] = fact[n-1] * n % MOD
fact_inv[U] = pow(fact[U],MOD-2,MOD)
for n in range(U-1,0,-1):
  fact_inv[n] = fact_inv[n+1] * (n+1) % MOD

def perm(n,k):
  if k > n or k < 0:
    return 0
  return fact[n] * fact_inv[n-k] % MOD

def F(x,parent = None):
  if parent is None:
    c = perm(K, deg[x] + 1)
  else:
    c = perm(K-2, deg[x] - 1)
  for y in edge[x]:
    if y == parent:
      continue
    c *= F(y,x)
    c %= MOD
  return c

answer = F(0)
print(answer)
from collections import deque
N = int( input())
S = list( map( int, input().split()))

ans = 0
for c in range(1,N):
    now = 0
    k = 1
    for _ in range(1,N):
        if k*2 + 1 > N-2:
            break
        if k*c >= N-1:
            break
        if k*c >= N-1-k*c:
            break
        now += S[k*c] + S[N-1-k*c]
        H[k*c] = 1
        H[N-1-k*c] = 1
        if now > ans:
            ans = now
        k += 1
print(ans)


### FIXED CODE ###

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

ans = 0
for c in range(1,N):
    now = 0
    for t in range(c ,N, c):
        if ((N-1-t)%c == 0 and N-1-t <= t) or N-1-t - c <=0:
            break
        now += S[t] + S[N-1-t]
        if now > ans:
            ans = now
print(ans)
import numpy as np
N, M = [int(x) for x in input().split()]
H = [float(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(M)]

graph = np.zeros((N,N))
for A, B in AB:
  graph[A-1][B-1] = 1
  graph[B-1][A-1] = 1

ans = 0
for i in range(N):
  for j in range(N):
    h = 0
    if(graph[i][j]!=0):
      if(H[i]<=H[j]):
        h += 1
  if(h==0):
    ans += 1
print(ans)

### FIXED CODE ###

import numpy as np
N, M = [int(x) for x in input().split()]
H = [float(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(M)]

max_h = [0 for _ in range(N)]

for A, B in AB:
  max_h[A-1] = max(max_h[A-1], H[B-1])
  max_h[B-1] = max(max_h[B-1], H[A-1])

ans = 0
for i in range(N):
  if(H[i]>max_h[i]):
    ans += 1
print(ans)
a = int(input())
b = int(input())

print(a + b)
print(a - b)


### FIXED CODE ###

A, op, B = input().split()

if op =="+":
    print(int(A) + int(B))
elif op == "-":
    print(int(A) - int(B))
n=int(input())
import math
print(2*n//math.gcd(2,n))


### FIXED CODE ###

n=int(input())
print(2*n) if n%2 != 0 else print(n)
A,B,K = map(int, input().split())
X = []
L = B-A+1
if 2*K>=L:
    for i in range(L):
        print(A+i)
else:
    for j in range(K):
        print(A+i)
    for k in range(K):
        print(A-K+k)

### FIXED CODE ###

A,B,K = map(int, input().split())
X = []
L = B-A+1
if 2*K>=L:
    for i in range(L):
        print(A+i)
else:
    for j in range(K):
        print(A+j)
    for k in range(K):
        print(B-K+1+k)
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    import numpy as np
    N = int(input())
    A = np.array(list(map(int, input().split())))

    #output
    def make_divisors(n):
        lower_divisors , upper_divisors = [], []
        i = 1
        while i*i <= n:
            if n % i == 0:
                lower_divisors.append(i)
                if i != n // i:
                    upper_divisors.append(n//i)
            i += 1
        return lower_divisors + upper_divisors[::-1]

    answer = 0
    for i in range(N):
        temp_list = make_divisors(A[i])
        temp1 = temp_list[:-1]
        temp2 = temp_list[-1]
        if len(A[A == temp2]) > 1:
            answer += 1
        for t in temp1:
            if t in A:
                answer += 1
                break

    print(N - answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

### FIXED CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    from collections import Counter
    M = max(A) + 1
    B = [True] * (M+1)
    A = sorted(A)
    C = Counter(A)

    answer = 0
    for a in A:
        if B[a]:
            for j in range(a, M, a):
                B[j] = False
            if C[a] > 1:
                continue
            else:
                answer += 1

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()
import sys
input = sys.stdin.readline
s = 0
N = int(input())
for i in range(1, int(N**(1/2))):
    if N%i == 0 and i > s:
        s = i
print(s+(N//s)-2)

### FIXED CODE ###

import sys
input = sys.stdin.readline
s = 0
N = int(input())
for i in range(1, int(N**(1/2))+1):
    if N%i == 0 and i > s:
        s = i
print(s+(N//s)-2)
n = int(input())
array = mat(int, input().split)
def shift_only(array):
    tmp = []
    counter = 0
    while True:
        flag = True
        # 全て偶数かを確認
        for num in array:
            if num%2 != 0:
                flag = False
        if flag == False:
            break
        array = [i/2 for i in array]
        counter +=1
    print(counter)
shift_only(array)

### FIXED CODE ###

def shift_only(array):
    tmp = []
    counter = 0
    while True:
        flag = True
        # 全て偶数かを確認
        for num in array:
            if num%2 != 0:
                flag = False
        if flag == False:
            break
        array = [i/2 for i in array]
        counter +=1
    print(counter)
    
n = int(input())
a = list(map(int, input().split()))
shift_only(a)
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
for _ in range(4):
	N,K,X,Y=int(input())

	
print(N*X-(max((N-K),0)*(X-Y)))


### FIXED CODE ###

import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
N=int(input())
K=int(input())
X=int(input())
Y=int(input())

	
print(N*X-(max((N-K),0)*(X-Y)))
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

n,a,b=map(int,input().split())
ans=((2**n-1)%(10**9+7)-cmb(n,a,mod)-cmb(n,b,mod))
print(ans)

### FIXED CODE ###

mod=10**9+7
n,a,b=map(int,input().split())
ans=pow(2,n,mod)-1 #n種類の花を使って花束を作る総数は2^n-1通り
comb1=1 #nCaの計算
for i in range(n-a+1,n+1): #n*(n-1)*…*(n-a+1)を計算
 comb1*=i
 comb1%=mod
for i in range(1,a+1): #1/a!=1/(1*2*…*a)=1^(p-2)*2^(p-2)*…*a^(p-2) (p=10**9+7)を計算
 comb1*=pow(i,mod-2,mod)
 comb1%=mod
comb2=1
for i in range(n-b+1,n+1): #n*(n-1)*…*(n-b+1)を計算
 comb2*=i
 comb2%=mod
for i in range(1,b+1): #1/b!=1/(1*2*…*b)=1^(p-2)*2^(p-2)*…*b^(p-2) (p=10**9+7)を計算
 comb2*=pow(i,mod-2,mod)
 comb2%=mod
ans-=(comb1+comb2) #nCa、nCbを総数から引く
ans%=mod
print(ans)
a = int(input())
s = input()

if(a => 3200):
    print(s)
else:
    print('red')

### FIXED CODE ###

a = int(input())
s = input()

if(a >= 3200):
    print(s)
else:
    print('red')
N,M = map(int,input().split())
e = [[] for i in range(N)]
t = 0
for i in range(M):
    r,l,d = map(int,input().split())
    e[r-1].append([l-1,d])
    e[l-1].append([r-1,-d])
    t = r-1

col = [ -1 for i in range(N) ]
def dfs(i,c):

    for node in e[i]:
        if col[node[0]] == -1:
            col[node[0]] = c + node[1]
            dfs(node[0],c+node[1])
        elif col[node[0]] != c + node[1]:
            print("No")
            exit()

dfs(t,0)

print("Yes")


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

def main():
    N,M = map(int,input().split())
    e = [[] for i in range(N)]
    t = 0
    a = []
    for i in range(M):
        r,l,d = map(int,input().split())
        e[r-1].append([l-1,d])
        e[l-1].append([r-1,-d])
        a.append(r-1)
        a.append(l-1)
        t = r-1

    col = [ float("inf") for i in range(N) ]
    def dfs(i,c):

        for node in e[i]:
            if col[node[0]] == float("inf"):
                col[node[0]] = c + node[1]
                dfs(node[0],c+node[1])
            elif col[node[0]] != c + node[1]:
                print("No")
                exit()


    dfs(t,0)
    a = list(set(a))
    for i in a:
        if col[i] == float("inf"):
            dfs(i,0)


    print("Yes")


if __name__ == '__main__':
    main()
import collections
S = input()
cnt = 0

mod = [0]
reverse_S = S[::-1]
for i in range(len(reverse_S)):
  now = int(reverse_S[i]) * pow(10,i+1,2019)
  mod.append((now + mod[i]) % 2019)

c = collections.Counter(mod)
hindo = sorted(c.values(),reverse=True)
for i in range(hindo.index(1)):
  n = hindo[i]
  cnt += n*(n-1)//2

print(cnt)

### FIXED CODE ###

import collections
S = input()
cnt = 0

mod = [0]
reverse_S = S[::-1]
for i in range(len(reverse_S)):
  now = int(reverse_S[i]) * pow(10,i,2019)
  mod.append((now + mod[i]) % 2019)


c = collections.Counter(mod)
hindo = c.values()
for i in hindo:
  if i != 1:
    cnt += i*(i-1)//2


print(cnt)