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

n,m=map(int,input().split())
A=list(map(int,input().split()))
B=[];C=[];Q=[]
A.sort()
for i in range(m):
    b,c=map(int,input().split())
    Q.append([b,c])

import bisect as bi
Q=sorted(Q, key=lambda x:x[1], reverse=1)

for l in Q:
    b,c=l
    a=bi.bisect_left(A,c)
    if A[0]>=c:
        break
    if a< b:
        A=[c]*a + A[a:]
        break
    
    A= A[b:a]+ [c]*b + A[a:]
    #print(A)
print(sum(A))

### FIXED CODE ###

n,m=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
Q=[]
for i in range(m):
    b,c=map(int,input().split())
    Q.append([b,c])

Q=sorted(Q, key=lambda x:x[1], reverse=1)
kae=0

d=[-1]*(n)
now=0
for l in Q:
    b,c=l
    if n-now<b:
        d[now:]=[c]*(n-now)
        break
    d[now:now+b]=[c]*b
    now+=b

#print(d)
ans=sum(A)
now=ans
for kae in range(1,n+1):
    now+=d[kae-1]
    now-=A[kae-1]
    ans=max(ans,now)
print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(n-2) :
  for j in range(i+1,n-1) :
    for k in range(j+1,n) :
      if l[i] < l[j]+l[k] and l[j] < l[i]+l[k] and l[k] < l[j]+l[i] :
        ans += 1

print(ans)

### FIXED CODE ###

import bisect

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

ans = 0
for i in range(n-2) :
  for j in range(i+1,n-1) :
    index = bisect.bisect_left(l,l[i]+l[j])
    ans += index-1-j

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

s = input().split()
N = int(s[0])
K = int(s[1])
Q = int(s[2])

point = [K for i in range(N)]


for i in range(Q):
    k = int(input())
    for j in range(N):
        if j == k-1:
            continue
        else:
            point[j] -= 1

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


### FIXED CODE ###

s = input().split()
N = int(s[0])
K = int(s[1])
Q = int(s[2])

point = [K-Q for i in range(N)]


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

for i in range(N):
    if point[i] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import bisect
n,m = map(int,input().split())
data = [tuple(map(int,input().split())) for i in range(n)]
data.sort(key = lambda tup:tup[0])
salary =[]
ans=0
prev=0
memo=0
for day in range(m):
	for i in range(memo,n):
		if data[memo][0]<=(day+1):
			bisect.insort(salary,data[memo][1])
			# salary.append(data[memo][1])
			memo+=1
		else:
			break

	# ans+=salary.pop(max)
	if len(salary)!=0:
		ans+=salary.pop()
print(ans)	

### FIXED CODE ###

import heapq
n,m = map(int,input().split())
AB =[tuple(map(int,input().split())) for i in range(n)]
ans,memo=0,0
hq=[]
AB.sort(key=lambda tup:tup[0])
for day in range(m):
	for i in range(memo,n):
		if AB[i][0]<=(day+1):
			heapq.heappush(hq,-AB[i][1])
			memo+=1
		else:
			break
	if len(hq):	
		ans += -heapq.heappop(hq)
print(ans)
### BUGGY CODE ###

# input
n = int(input())

edge = [[0, 0, 0] for i in range(n-1)]
for i in range(n-1):
    edge[i][0] ,edge[i][1] = map(int, list(input().split()))

# process
def findcolor(p):
    if p == 1: 
        return 0
    else: 
        for e in edge:
            if e[1] == p:
                return e[2]

for i in range(n):
    i += 1
    color = 0
    pcolor = findcolor(i)
    for j in range(n-1):
        if edge[j][0] == i:
            color += 1
            if color == pcolor: color += 1
            edge[j][2] = color

k = 0
for e in edge:
    if e[2] > k: k = e[2]

# output
print(k)
for e in edge:
    print(e[2])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

# input
n = int(input())

edges = [[] for i in range(n)]
for i in range(n-1):
    a ,b = map(int, list(input().split()))
    edges[a-1].append((b-1, i))

# process
ans = [0]*(n-1)

def f(a, c):
    color = 1
    for b, i in edges[a]:
        if color == c: color += 1
        ans[i] = color 
        f(b, color)
        color += 1

f(0, 0)

# output
print(max(ans))
for i in ans:
    print(i)
### BUGGY CODE ###

N=int(input())

X=[]
for i in range(N):
  a=input().split()
  X.append([int(a[0]),int(a[1])])


def ceil(x):
  if int(x)==x:
    return int(x)
  else:
    return int(x//1+1)


a=X[0][0]
b=X[0][1]

for i in range(1,N):
  c=X[i][0]
  d=X[i][1]
  a1=a*d/c
  if a1<b:
    y=ceil(a/c)*d-b
  else:
    y=ceil(a/c)*d-b

  while y<0:
    y+=d


  x=c*(b+y)//d-a
 
  #print("i = "+str(i)+" a = "+str(a)+" b = "+str(b)+" c = "+str(c)+" d = "+str(d)+" x = "+str(x)+" y = "+str(y))
  a=a+x
  b=b+y
print(a+b)

### FIXED CODE ###

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

  x= (a + (c - 1)) // c
  y= (b + (d -1)) // d
  
  a1=1000000000000000000
  b1=1000000000000000000
  a2=1000000000000000000
  b2=1000000000000000000
  if d*x-b>=0:
    a1=c*x
    b1=d*x
 
  
  if c*y-a>=0:
    a2=c*y
    b2=d*y
  if (a1+b1)<(a2+b2):
    a=a1
    b=b1
  else:
    a=a2
    b=b2
 
  #print("i = "+str(i)+" a = "+str(a)+" b = "+str(b)+" a1 = "+str(a1)+" b1 = "+str(b1)+" a2 = "+str(a2)+" b2 = "+str(b2)+" c = "+str(c)+" d = "+str(d))
  
 
 
 
 
  
print(a+b)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(1, n+1):
    print(a.count(i))

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
d = defaultdict(int)
for i in a:
    d[i] += 1
for j in range(1, n+1):
    print(d.get(j, 0))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

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

def solve(N,M):
    if N > M:
        return solve(M,N).T
    H = np.array([[0]], np.int8)
    for i in range(M):
        H = np.tile(H, (2,2))
        H[1<<i:,1<<i:] ^= 1
    H = np.diff(H, axis=0)
    H = np.diff(H, axis=1)
    return (H % 2)[:(1<<N) - 1]

H = solve(N,M)
rows = (''.join(map(str, row)) for row in H)
print('\n'.join(rows))


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

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

def solve(N,M):
    if N > M:
        return solve(M,N).T
    H = np.array([[0]], np.int8)
    for i in range(M):
        H = np.tile(H, (2,2))
        H[1<<i:,1<<i:] ^= 1
    H = np.diff(H, axis=0)
    H = np.diff(H, axis=1)
    return (H % 2)[:(1<<N) - 1]

H = solve(N,M)
size = 0
for row in H:
    word = ''.join(row.astype(str))
    print(word)
### BUGGY CODE ###


S = input()

lis = [1,0,0,0]
nlis = [1,0,0,0]

for s in S:

    if s == "?":

        nlis[0] += lis[0] * 2
        nlis[1] += lis[1] * 2
        nlis[2] += lis[2] * 2
        nlis[3] += lis[3] * 2

    if s == "A" or s == "?":

        nlis[1] += lis[0]

    if s == "B" or s == "?":

        nlis[2] += lis[1]

    if s == "C" or s == "?":

        nlis[3] += lis[2]

    lis = nlis.copy()

print (lis[3]  % (10 ** 9 + 7))


### FIXED CODE ###


S = input()

lis = [1,0,0,0]
nlis = [1,0,0,0]

for s in S:

    if s == "?":

        nlis[0] += lis[0] * 2
        nlis[1] += lis[1] * 2
        nlis[2] += lis[2] * 2
        nlis[3] += lis[3] * 2

    if s == "A" or s == "?":

        nlis[1] += lis[0]

    if s == "B" or s == "?":

        nlis[2] += lis[1]

    if s == "C" or s == "?":

        nlis[3] += lis[2]

    lis = []
    for i in range(4):

        lis.append(nlis[i] % (10 ** 9 + 7))

print (lis[3]  % (10 ** 9 + 7))
### BUGGY CODE ###

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

if k < a:
    print(k)
    exit()

k -= (a+b)
if k <= 0:
    print(a)
    exit()
else:
    ans = a

for i in range(k):
    ans -= 1
print(ans)

### FIXED CODE ###

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

if k < a:
    print(k)
    exit()

k -= (a+b)
if k <= 0:
    print(a)
    exit()
else:
    ans = a

print(ans - k)
### BUGGY CODE ###

import math
Q = int(input())
num_ranges = [list(map(int, input().split())) for _ in range(Q)]

primes = [2]
likes_nums = []


def is_prime(num):
    # 今まででた素数で割っていくと、自身が素数かどうかわかる
    if num == 1:
        return False
    if primes[-1] <= math.ceil(math.sqrt(num)):
        for i in range(primes[-1], math.ceil(math.sqrt(num)) + 1):
            is_prime = True
            # 今まででた素数で割っていくと、自身が素数かどうかわかる
            for p in primes:
                if i % p == 0:
                    is_prime = False
            if is_prime:
                primes.append(i)
    for p in primes:
        # 全てprimesを見るのは時間が勿体無いので、自身よりも大きいもの・もしくは同じになったら抜ける.
        # もし素数でないのであれば、p<nの間にあるはず。ない状態で、同じ数値まで来た場合も素数
        if num <= p:
            return True

        if num % p == 0:
            return False
    return True


def check(num):
    if num in likes_nums:
        return True
    if is_prime(num) and is_prime((num + 1) / 2):
        likes_nums.append(num)
        return True
    else:
        return False


for start, end in num_ranges:
    count = 0
    for i in range(start, end + 1):
        if i % 2 == 0:
            continue
        if check(i):
            # print(i)
            count += 1
    print(count)


### FIXED CODE ###

from itertools import accumulate
INF = float('inf')


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    a = [2 * i + 1 for i in range(m) if p[i]]
    a[0] = 2
    return a


N = 10 ** 5
P = set(prime_numbers(N))
# これが素数
# print(P)
P = [n for n in P if (n + 1) // 2 in P]
# 自身 + 1 //2 も素数であるもののみに絞る
# print(P)
a = [0] * (N + 1)
for n in P:
    # likenumberは1にする
    a[n] = 1
# 累積和に変換
a = list(accumulate(a))


Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(a[r] - a[l - 1])
### BUGGY CODE ###

import itertools
if __name__ == '__main__':
    n=int(input())
    string=input()
    string=list(string)
    string_set=set(string)
    div=10**9+7
    count=0
    Dict={}
    for i,s in enumerate(string):
        if s not in Dict.keys():
            Dict[s]=1
        else:
            Dict[s] += 1
        count+=1

    if len(string_set)>1:
        for i in range(2,len(string_set)+1):
            for x in itertools.combinations(Dict.keys(),i):
                temp = 1
                for y in x:
                    temp*=Dict[y]
                count+=temp

    print(count%div)

### FIXED CODE ###

if __name__ == '__main__':
    n=int(input())
    string=input()
    string_set=set(string)
    div=10**9+7
    count=1
    for s in string_set:
        count*=string.count(s)+1
    count-=1
    print(count%div)
### BUGGY CODE ###

h,w,n=map(int,input().split())
H=[0]*h
W=[0]*w
L=[0]*n
for i in range(n):
    a,b=map(int,input().split())
    L[i]=(a,b)
    H[a-1]+=1
    W[b-1]+=1
h_max=max(H)
w_max=max(W)
H_max=[i+1 for i, x in enumerate(H) if x == max(H)]
W_max=[i+1 for i, x in enumerate(W) if x == max(W)]

ans=0
for hh in H_max:
    for ww in W_max:
        if (hh,ww) in L:
            ans=max(ans,h_max+w_max-1)
        else:
            ans=h_max+w_max
            break
    else:
        continue
    break
print(ans)

### FIXED CODE ###

h,w,n=map(int,input().split())
H=[0]*h
W=[0]*w
L=[(0,0)]*n
for i in range(n):
    a,b=map(int,input().split())
    L[i]=(a,b)
    H[a-1]+=1
    W[b-1]+=1
h_max=max(H)
w_max=max(W)
ans=h_max+w_max
cnt=0
for l in L:
    if H[l[0]-1]==h_max and W[l[1]-1]==w_max:
        cnt+=1
if H.count(h_max)*W.count(w_max)==cnt:
    ans-=1
print(ans)
### BUGGY CODE ###

def slove(n, m):
    while True:
        if (m - n*2) >= 0:
            break
        n -= 1

    if (m - n*2) >= 0:
        tmp = (m - n * 2) // 4 + n
    else:
        tmp = 0
    return tmp

if __name__ == "__main__":
    n, m = [int(i) for i in input().split()]
    print(slove(n, m))


### FIXED CODE ###

def slove(n, m):
    tmp = n if n < m // 2 else m // 2
    tmp2 = (m - tmp * 2) // 4
    return tmp + tmp2
    
if __name__ == "__main__":
    n, m = [int(i) for i in input().split()]
    print(slove(n, m))
### BUGGY CODE ###

s = list(input())
n = len(s)
ans = 0
i = 0
while i < n-2:  # 3文字なので
    if s[i:i+3] == ['A', 'B', 'C']:
        s[i:i+3] = ['B', 'C', 'A']
        ans += 1
        i = max(i-1, 0)   # 1つ前がAの場合をチェック
    else:
        i += 1

print(ans)


### FIXED CODE ###

s = input()
n = len(s)
ans = 0
numa = 0
i = 0
while i < n-1:  # 最後'BC'以外は、最後の文字は関係ないので s[n-1]は不要
    if s[i] == 'A':
        numa += 1   # Aが連続で続く場合は数える
    elif s[i:i+2] == 'BC':
        ans += numa # AAAA と BC を入れ替える回数。またBCが来たら加算する
        i += 1  # BCの場合は、2文字進めるので+1
    else:
        numa = 0
    i += 1
print(ans)
### BUGGY CODE ###

import math
S = int(input())
X1 = 0
Y1 = 0
X2 = 0
Y2 = 0
X3 = 0
Y3 = 0


for i in range(int(math.sqrt(S) + 1), -1, -1):
    if S%i == 0:
        X2 = i
        Y3 = S//i
        break


print (X1, Y1, X2, Y2, X3, Y3)

### FIXED CODE ###

import math
S = int(input())
X1 = 0
Y1 = 0
X2 = 0
Y2 = 0
X3 = 0
Y3 = 0
if  S <= 10 ** 9:
    X2 = S
    Y3 = 1
elif S == 1000000000000000000:
    X2 = int(math.sqrt(S))
    Y3 = X2
else:
    X2 = int(math.sqrt(S) + 1)
    Y3 = X2
    s = X2 ** 2  - S #残りの面積
    for i in range(1, int(math.sqrt(s) + 1)):
        if s%i == 0 and s//i <= 10 ** 9 and i <= 10 ** 9:
            X3 = i
            Y2 = s//i
            break

print (X1, Y1, X2, Y2, X3, Y3)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
n=int(input())
a=[]
for i in range(0,n):
  a.append(int(input()))
a.sort()

b = [a[0]]
a=a[1:]

f=True
#while len(a)>0:
for i in range(0,n-1):
  la=len(a)-1
  lb=len(b)-1
  ln = abs(b[0]-a[0])
  lx = abs(b[0]-a[la])
  rn = abs(b[lb]-a[0])
  rx = abs(b[lb]-a[la])

  x = max(ln, max(lx, max(rn, rx)))
  
  if x == ln:
    b.insert(0,a[0])
    a=a[1:]
  elif x == lx:
    b.insert(0,a.pop())
  elif x == rn:
    b.append(a[0])
    a=a[1:]
  else:
    b.append(a.pop())

res=0
for i in range(0,len(b)-1):
  res=res+abs(b[i]-b[i+1])
print(res)


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
n=int(input())
a=[]
for i in range(0,n):
  a.append(int(input()))
a.sort()

l = a[0]
r = a[0]

li=1
ri=len(a)-1

res = 0

while ri>=li:
  ln = abs(l-a[li])
  lx = abs(l-a[ri])
  rn = abs(r-a[li])
  rx = abs(r-a[ri])

  x = max(ln, max(lx, max(rn, rx)))
  
  if x == ln:
    res = res + ln
    l=a[li]
    li=li+1
  elif x == lx:
    res = res + lx
    l=a[ri]
    ri=ri-1
  elif x == rn:
    res = res + rn
    r=a[li]
    li=li+1
  else:
    res = res + rx
    r=a[ri]
    ri=ri-1

print(res)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Factoring by trial split
def getPrimeList(n):
  l=[]
  t=int(math.sqrt(n))+1
  
  for a in range(2,t):
    while n%a==0:
      n//=a
      l.append(a)
  
  if n!=1:
    l.append(n)
  
  return l

def main():
  n=I()
  a=getPrimeList(n)

  ans=inf
  b=len(a)
  for i in range(2**b//2):
    _a=_b=1
    for j,x in enumerate(a):
      if ((i>>j)&1):
        _a*=x
      else:
        _b*=x
    ans=min(ans,_a+_b-2)
  return ans

# main()
print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()

  ans=inf
  for x in range(1,int(math.sqrt(n))+1):
    if n%x==0:
      ans=min(ans,x+n//x-2)
  return ans

# main()
print(main())
### BUGGY CODE ###

import heapq
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)

for _ in range(m):
    maximum = a.index(max(a))
    a[maximum] = a[maximum] // 2

print(sum(a))


### FIXED CODE ###

from heapq import heappop,heappush,heapify
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
a_minus = [-x for x in a]
heapify(a_minus)

pop = lambda: -heappop(a_minus)
push = lambda x: heappush(a_minus,-x)

for _ in range(m):
    x = pop()
    push(x//2)

print(-sum(a_minus))
### BUGGY CODE ###

d = int(input())
s = input()
R, G, B = [], [], [] 

for i, c in enumerate(s):
    if c == "R":
        R.append(i)
    elif c == "G":
        G.append(i)
    else:
        B.append(i)

ans = 0
for r in R:
    for g in G:
        for b in B:
            x = sorted([r, g, b])
            if x[1] - x[0] != x[2] - x[1]:
                ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
cnt = s.count("R") * s.count("G") * s.count("B")
for i in range(n-2):
    for j in range(i+1, n-1):
        if s[i] == s[j]:
            continue
        k = j - i + j
        if k > n-1:
            continue
        if s[i] == s[k] or s[j] == s[k]:
                continue
        cnt -= 1
print(cnt)
### BUGGY CODE ###

import sys

N,K,Q = list(map(int,input().split()))
A = []
for i in range(Q):
  tmp = int(input())
  A.append(tmp)
  
if K > Q:
  for i in range(N):
    print('Yes')
  sys.exit()
K_Q = K-Q
A_set = set(A)
for i in range(N):
  if i + 1 in A_set:
    if K_Q + A.count(i+1) > 0:
      print('Yes')
    else:
      print('No')
  else:
    print('No')

### FIXED CODE ###

import sys
from collections import Counter

N,K,Q = list(map(int,input().split()))
A = []
for i in range(Q):
  tmp = int(input())
  A.append(tmp)
  
if K > Q:
  for i in range(N):
    print('Yes')
  sys.exit()
K_Q = K - Q
A_freq = Counter(A)
for i in range(1,N+1):
  if K_Q + A_freq[i] > 0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
if all(s[i][j]==s[0][0] for i in range(n) for j in range(n)): print(n**2)
else:
	for i in range(n): s[i] += s[i]
	s,ans = s+s,0
	for j in range(n):
		for k in range(n):
			flag = True
			for k2 in range(k,n+k):
				for j2 in range(j,n+j):
					if s[k2][j2]!=s[j2-j+k][k2-k+j]:
						flag = False
						break
				if not flag: break
			if flag: ans += 1
	print(ans)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
s,s2,ans = s+s,[],0
for i in range(n):
	x = ""
	for j in s: x+=j[i]
	s2.append(x)
for i in range(n):
	flag = True
	for j in range(i,i+n):
		if s[j][1:n]!=s2[j-i][1+i:n+i]:
			flag = False
			break
	if flag: ans += n
print(ans)
### BUGGY CODE ###

A,B,N = map(int,input().split())
ans = []
for x in range(N//2,N+1):
    tmp = (A * x // B) - A * (x//B)
    ans.append(tmp)
print(max(ans))

### FIXED CODE ###

A,B,N = map(int,input().split())
if N >= (B-1):
        x = B -1
else:
        x = N
print((A * x // B) - A * (x//B))
### BUGGY CODE ###

def pre_cmb(N, MOD):  # cmbの前準備
    FACT = [1, 1]  # 階乗
    INV = [0, 1]  # 各iの逆元
    FACTINV = [1, 1]  # 階乗の逆元

    for i in range(2, N + 1):
        FACT.append((FACT[-1] * i) % MOD)
        INV.append(pow(i, MOD-2, MOD))
        FACTINV.append((FACTINV[-1] * INV[-1]) % MOD)
    PRELIST = FACT, FACTINV
    return PRELIST


def cmb(N, R, MOD, PRELIST):  # nCr(mod p)
    FACT, FACTINV = PRELIST
    if (R < 0) or (N < R):
        return 0
    R = min(R, N - R)
    return FACT[N] * FACTINV[R] * FACTINV[N-R] % MOD



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


### FIXED CODE ###


def bigcmb(N, R, MOD):  # nCr(mod p) #n>=10**7 #前処理不要
    if (R < 0) or (N < R):
        return 0
    R = min(R, N - R)
    fact, inv = 1, 1
    for i in range(1, R + 1):
        fact = (fact * (N - i + 1)) % MOD
        inv = (inv * i) % MOD
    return fact * pow(inv, MOD - 2, MOD) % MOD


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

exc = bigcmb(n, a, mod) + bigcmb(n, b, mod)
print((pow(2, n, mod) - exc - 1) % mod)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = input()

R = []
G = []
B = []

for i in range(N):
    if S[i] == "R":
        R.append(i)
    elif S[i] == "G":
        G.append(i)
    else:
        B.append(i)

# print(R, G, B)

ans = len(R) * len(G) * len(B)

count = 0

for i in range(N):
    for j in range(N):
        if i < j:
            k = j + (j - i)
            if k < N:
                if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                    count += 1
print(ans - count)

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = input()

R = []
G = []
B = []

for i in range(N):
    if S[i] == "R":
        R.append(i)
    elif S[i] == "G":
        G.append(i)
    else:
        B.append(i)

# print(R, G, B)

ans = len(R) * len(G) * len(B)

count = 0

for i in range(N):
    for j in range(N):
        if i < j:
            k = j + (j - i)
            if k < N:
                if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                    count += 1
print(ans - count)
### BUGGY CODE ###

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

attend = [str(a.index(i) + 1) for i in range(1, n+1)]

print(" ".join(attend))

### FIXED CODE ###

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

ans = [""]*n

for i in range(n):
    x = a[i]
    b = ans[a[i] - 1]
    c = str(i+1)
    ans[a[i]-1] = str(i+1)

print(" ".join(ans))
### BUGGY CODE ###

import queue
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n):
    if i == 0:
        g[i] = [i+1]
    elif i == n-1:
        g[i] = [i-1]
    else:
        g[i] = [i-1,i+1]
g[x-1].append(y-1)
g[y-1].append(x-1)

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)
d = []
for i in range(n):
    start = i
    dist = [-1] * n
    dist[start] = 0
    que = queue.Queue()
    que.put(start)
    while not que.empty():
        v = que.get()
        for nv in g[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = dist[v]+1
            que.put(nv)
    d.append(dist)
d = np.array(d).flatten()
for i in range(1,n):
    print(int(np.count_nonzero(d==i)/2))

### FIXED CODE ###

def main():
    from collections import deque
    n,x,y=map(int,input().split())
    e=[[]for _ in range(n)]
    for i in range(n-1):
        e[i]+=i+1,
        e[i+1]+=i,
    e[x-1]+=y-1,
    e[y-1]+=x-1,
    a=[0]*n
    for s in range(n):
        d=[-1]*n
        d[s]=0
        q=deque([s])
        add,pop=q.append,q.popleft
        while q:
            v=pop()
            for w in e[v]:
                if d[w]<0:
                    d[w]=d[v]+1
                    add(w)
        for i in d:a[i]+=1
    print(' '.join(str(i//2)for i in a[1:]))
main()