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

n,m = map(int,input().split())
g = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
from collections import deque
d = deque([[0,0]]) # 左は今考えてる部屋、右は前の部屋
ans = [-1 for i in range(n)]
while d:
    u,v = d.popleft()
    if ans[u] == -1:
        ans[u] = v
    for j in g[u]:
        if ans[j] == -1:
            d.append([j,u])
        else:
            continue
print('Yes')
for i in range(1,n):
    print(ans[i]+1)

### FIXED CODE ###

n,m = map(int,input().split())
g = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
from collections import deque
d = deque([[0,0]]) # 左は今考えてる部屋、右は前の部屋
ans = [-1 for i in range(n)]
kak = [-100 for i in range(n)]
while d:
    u,v = d.popleft()
    if ans[u] == -1:
        ans[u] = v
    for j in g[u]:
        if ans[j] == -1 and kak[j] == -100:
            kak[j] = 0
            d.append([j,u])
        else:
            continue
print('Yes')
for i in range(1,n):
    print(ans[i]+1)
### BUGGY CODE ###

import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

n = I()
a = LI()

ret = a[0]
for i in range(1,n):
    ret = ret * a[i]

if(ret > 1000000000000000000):
    ret = -1


print(ret)

### FIXED CODE ###

import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

n = I()
a = LI()

if (0 in a):
    ret = 0
else:
    ret = a[0]
    for i in range(1,n):
        ret = ret * a[i]
        if(ret > 1000000000000000000):
            ret = -1
            break

print(ret)
### BUGGY CODE ###

n = int(input())
ss = []
mylist =[]
for i in range(n):
    temp = input()
    if temp in ss:
        next
    else:
        ss.append(temp)
        
print(len(ss))
    

    

### FIXED CODE ###

n = int(input())
ss = set()
for i in range(n):
    temp = input()
    if temp in ss:
        next
    else:
        ss.add(temp)
        
print(len(ss))
### BUGGY CODE ###

import itertools

inf = float("inf")
n,m,r = map(int,raw_input().split())
arr = map(int,raw_input().split())
d = [[inf for i in range(n)] for j in range(n)]

for i in range(n):
	d[i][i] = 0

for i in range(m):
	f,t,c = map(int,raw_input().split())
	d[f-1][t-1] = c
	d[t-1][f-1] = c

for i in range(n):
	for j in range(n):
		for k in range(n):
			d[i][j] = min(d[i][j], d[i][k] + d[k][j])


per = list(itertools.permutations(range(r)))

ans = inf
for i in per:
	distance = 0
	for j in range(1,r):
		distance += d[arr[i[j-1]]-1][arr[i[j]]-1]

	ans = min(ans,distance)

print ans

### FIXED CODE ###

from itertools import permutations
import sys

def main():
    
    N, M, R = map(int, sys.stdin.readline().split())
    r = [i - 1 for i in map(int, sys.stdin.readline().split())]
    
    d = [[float('inf')] * N for _ in range(N)]
    
    for i in range(N):
        d[i][i] = 0
        
    for i in range(M):
        a, b, c = map(int,sys.stdin.readline().split())
        d[a-1][b-1] = c
        d[b-1][a-1] = c
        
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    
    ans = 10**12
    
    for each in permutations(r):
        t_dis = 0
        for i in range(R-1):
            t_dis += d[each[i]][each[i+1]]  
        
        ans = min(ans, t_dis)
    
    print(ans)

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

a,b,c,d = map(int,input().split())
u = b - a + 1
n_c = b//c - (a-1)//c
n_d = b//d - (a-1)//d
for i in range(1, c*d+1):
    if i % c == 0 and i % d == 0:
        cd = i
        break
n_cd = b//(cd) - (a-1)//(cd)
print(u - n_c - n_d + n_cd)

### FIXED CODE ###

a,b,c,d = map(int,input().split())
u = b - a + 1
from fractions import gcd
cd = c*d//gcd(c,d)
n_c = b//c - (a-1)//c
n_d = b//d - (a-1)//d
n_cd =b//cd - (a-1)//cd
print(int(u - n_c - n_d + n_cd))
### BUGGY CODE ###

R, G, B ,N = list(map(int, input().split(' ')))

cnt = 0

_R = N//R
_G = N//G
_B = N//B

for i in range(_R+1):
    for j in range(_G+1):
        for k in range(_B+1):
            if i*R + j*G + k*B == N:
                cnt += 1
print(cnt)
    

### FIXED CODE ###

R, G, B ,N = list(map(int, input().split(' ')))

cnt = 0

li = [R, G, B]
li = sorted(li)

_i = N//li[2]
for i in range(_i+1):
    _j = (N - li[2]*i )//li[1]
    for j in range(_j + 1):
        if (N - i*li[2] -  j*li[1])%li[0] == 0:
            cnt += 1

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

import fractions
n=int(input())
t = list(map(int, input().split()))
l=[]
ans = t[0]
for i in range(1, n):
    ans = ans * t[i] // fractions.gcd(ans, t[i])
for j in range(n):
    l.append(ans//t[j])
print(sum(l)%(10**9+7))

### FIXED CODE ###

import fractions
n=int(input())
t = list(map(int, input().split()))
x=0
ans = t[0]
for i in range(1, n):
    ans = ans * t[i] // fractions.gcd(ans, t[i])
for j in range(n):
    x+=ans//t[j]
print(x%(10**9+7))
### BUGGY CODE ###

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


for q in range(Q):
  l,r = map(int, input().split())
  s_q = s[l-1:r]
  cnt = 0
  
  for i in range(len(s_q)-1):
    if s_q[i:i+2] == 'AC':
      cnt += 1
  
  print(cnt)
  




### FIXED CODE ###

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

cnt = 0
n = [0]
for i in range(N-1):
    if s[i]+s[i+1] == 'AC':
        cnt += 1
    n.append(cnt)


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

n, q = list(map(int, input().split(" ")))
s = input()
l = q*[0]
r = q*[0]
for i in range(q):
    l[i], r[i] = list(map(int, input().split(" ")))


AC = (n-1)*[0]
for i in range(len(s)-1):
    if(s[i:i+2] == "AC"): AC[i] = 1

for i in range(q):
    print(sum(AC[l[i]-1:r[i]-1]))

### FIXED CODE ###

n, q = list(map(int, input().split(" ")))
s = input()
l = q*[0]
r = q*[0]
for i in range(q):
    l[i], r[i] = list(map(int, input().split(" ")))


AC = (n)*[0]
for i in range(len(s)-1):
    if(s[i:i+2] == "AC"): AC[i+1] += AC[i] + 1
    else: AC[i+1] = AC[i]

for i in range(q):
    print(AC[r[i]-1]-AC[l[i]-1])
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
a.sort()
b.sort(reverse=True)
#print(a)
#print(b)
c = []
for i in range(n):
  c.append([-a[i]*b[i],b[i]])
#print(c)
import heapq
heapq.heapify(c)
cnt = 0
while True:
  now = heapq.heappop(c)
  if now[0] == 0:
    heapq.heappush(c,now)
    break
  red = (c[0][0] - now[0]) // now[1]
  #print(red)
  if red > k - cnt:
    heapq.heappush(c, [now[0]+(k-cnt)*now[1],now[1]] )
    break
  elif red == 0:
    heapq.heappush(c, [now[0]+now[1],now[1]] )
    cnt += 1
  else:
    heapq.heappush(c, [now[0]+red*now[1],now[1]] )
    cnt += red
  if k == cnt:
    break
  #print(cnt,c)
#print(c)
ans = 0
for i in range(n):
  if ans > c[i][0]:
    ans = c[i][0]
print(-1*ans)

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
a.sort()
b.sort(reverse=True)
#print(a)
#print(b)
big = 44
stand = 2 ** big
width = 2 ** (big-1)
if sum(a) <= k:
  print(0)
else:
  while True:
    tmp = []
    for i in range(n):
       tmp.append(max(0,a[i]-stand//b[i]))
    if width == 0:
      if sum(tmp) <= k:
        print(stand)
      else:
        print(stand+1)
      break
    if sum(tmp) <= k:
      stand -= width
      width //= 2
    else:
      stand += width
      width //= 2
    #print(stand,tmp)
### BUGGY CODE ###

N = int(input())
#put a_i into list
list_a_i = list(sorted(map(int, input().split())))
remove = 0
while len(list_a_i) >=1:
    x = 0
    #count number of list_a_i[1]
    for j in range(len(list_a_i)):
        if list_a_i[0] == list_a_i[j]:
            x += 1
    if x > list_a_i[0]:
        remove += x - list_a_i[0]
    elif x < list_a_i[0]:
        remove += x
    for i in range(x):
        list_a_i.remove(int(list_a_i[0]))
print(remove)


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
dic = {}
for elem in a:
    if elem not in dic:
        dic[elem] = 1
    else:
        dic[elem] += 1

ans = 0
for k in dic.keys():
    if dic[k] > k:
        ans += dic[k] - k
    elif dic[k] < k:
        ans += dic[k]

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

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

for i in range(n):
  for j in range(n):
    if a[j] == i + 1:
      b.append(str(j+1))
      break

print(' '.join(b))



### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0 for i in range(n)]

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

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

N, K = list(map(int, input().split()))
c = 0
for i in range(1, N + 1):
    a = 0
    if (i + i) % K == 0:
        for j in range(1, N + 1):
            if (i + j) % K == 0:
                a += 1
    c += a * a
print(c)


### FIXED CODE ###

N, K = list(map(int, input().split()))
c = N // K
d = 0
for i in range(1, N + 1):
    if K % 2 == 0 and i % K == K // 2:
        d += 1
print(c ** 3 + d ** 3)
### BUGGY CODE ###

import sys
from io import StringIO
import unittest

import math

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**9)
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 )

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        x = x%mod #
        n //= 2

    return K * x

def resolve():

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

    ptn = pow_k(2,n)
    ptn -= 1


    comba=cmb(n,a,mod)
    combb=cmb(n,b,mod)

    ptn -= (comba+combb)
    ptn = ptn%mod

    print(ptn)

    return 

resolve()


### FIXED CODE ###

import sys
from io import StringIO
import unittest
import math

mod = 10**9+7

def pow_mod(a, b, mod):
    x = 1
    while b > 0:
        if b & 1:
            x = (x*a)%mod
        a = (a**2)%mod
        b //= 2
 
    return x

def modinv(a, mod):
    return pow_mod(a, mod-2, mod)

def comb(n,r,mod):
    combsum=1
    for i in range(n-r+1,n+1):
        combsum = (combsum * i)%mod

    for i in range(1,r+1):
        combsum = (combsum * inv[i])%mod

    return combsum

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

a=min([a,n-a])
b=min([b,n-b])

maxab=max([a,b])

inv=[modinv(i,mod) for i in range(0,maxab+2)]

def resolve():

    ptn = pow_mod(2,n,mod)
    ptn -= 1

    comba=comb(n,a,mod)
    combb=comb(n,b,mod)

    ptn = (ptn-comba-combb)%mod

    print(ptn)

    return 

resolve()
### BUGGY CODE ###

n=int(input())
print(0)
A={}
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A.update(0=0)
else:
  A.update(0=1)
print(n-1)
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A.update(n-1=0)
else:
  A.update(n-1=1)
l=0
r=n-1
while r-l!=0:
  mid=(l+r)//2
  print(mid)
  S=input()
  if S=="Vacant":
    exit()
  elif S=="Male":
    A.update(mid=0)
  else:
    A.update(mid=1)
  if (mid-l)%2==(A[l]+A[mid])%2:
    r=mid
  else:
    l=mid

### FIXED CODE ###

n=int(input())
print(0)
A=[-1]*n
S=input()
if S=="Vacant":
  exit()
elif S=="Male":
  A[0]=0
else:
  A[0]=1
l=0
r=n
while r-l!=0:
  mid=(l+r)//2
  print(mid)
  S=input()
  if S=="Vacant":
    exit()
  elif S=="Male":
    A[mid]=0
  else:
    A[mid]=1
  if (mid-l)%2!=(A[l]+A[mid])%2:
    r=mid
  else:
    l=mid
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from numpy.linalg import solve

n = int(input())
a = list(map(int, input().split()))
a = [_a * 2 for _a in a]

x = [[0]*n for _ in range(n)]
for i in range(n-1):
    x[i][i] = 1
    x[i][i+1] = 1
x[n-1][n-1] = 1
x[n-1][0] = 1

print(" ".join(map(str, map(int, list(solve(x, a))))))


### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))

x = [0 for _ in range(n)]
_x = 0
for i, _a in enumerate(a):
    if i % 2 == 0:
        _x += _a
    else:
        _x -= _a

x[0] = _x

for i in range(1, n):
    x[i] = a[i-1] * 2 - x[i-1]

print(" ".join(map(str, x)))
### BUGGY CODE ###

# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N = read_a_int()
L = read_ints()
L.sort()
import numpy as np
L = np.array(L)

cnt = 0
for i in range(N):
    a = L[i]
    for j in range(i+1, N):
        b = L[j]
        L_tmp = L[j+1:]
        cnt += np.sum(L_tmp < b+a)

print(cnt)


### FIXED CODE ###

# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N = read_a_int()
L = read_ints()
L.sort()
# import numpy as np
# L = np.array(L)
from bisect import bisect_left

cnt = 0
for i in range(N):
    a = L[i]
    for j in range(i+1, N):
        b = L[j]
        # ここで二分探索するか
        cnt += bisect_left(L, a+b) - (j+1)
        # L_tmp = L[j+1:]
        # cnt += np.sum(L_tmp < b+a)

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

import sys
def solve(n,m,a):
    ans = ""
    b = [[] for i in range(n)]
    for s1,s2 in a:
        b[s1-1].append(s2)
    for i in range(len(b)):
        b[i].sort()
    for i in range(m):
        ans += str(a[i][0]).zfill(6) + str(b[a[i][0]-1].index(a[i][1])+1).zfill(6) + "\n"
    
    return ans 
def readQuestion():
    ws = sys.stdin.readline().strip().split()
    N = int(ws[0])
    M = int(ws[1])
    ls_PY = [list(map(int, sys.stdin.readline().strip().split())) for j in range(M)]
    return (N, M, ls_PY)

def main():
    N, M, ls_PY = readQuestion()
    answer = solve(N, M, ls_PY)
    print(answer)

if __name__ == '__main__':
    main()

### FIXED CODE ###

N,M=map(int,input().split())
PY=[list(map(int,input().split()))+[i] for i in range(M)] #定義終了
 
PY.sort(key= lambda x:x[1])
num=[0]*N
w=[""]*M
 
for p,y,i in PY:
	num[p-1]+=1
	w[i]=str(p).zfill(6)+str(num[p-1]).zfill(6)

for i in range(M):
  	print(w[i])
### BUGGY CODE ###

h,w,m=map(int,input().split())
a=[[] for i in range(m)]
g=[0 for i in range(h)]
r=[0 for i in range(w)]

for i in range(m):
    x,y=map(int,input().split())
    a[i].append(x)
    a[i].append(y)
    g[x-1]+=1
    r[y-1]+=1
G=[]
R=[]
d=max(g)
e=max(r)
for i in range(h):
    if g[i]==d:
        G.append(i+1)
for i in range(w):
    if r[i]==e:
        R.append(i+1)
f=0
for i in range(m):
    q=0
    p=0
    x=a[i][0]
    y=a[i][1]
    k=len(G)-1
    l=0
    j=(k+l)//2
    while k-l>1:
        j=(k+l)//2
        if G[j]>=x:
            k=j
        else:
            l=j
    if G[l]==x or G[k]==x:
        p=1

    k = len(R) - 1
    l = 0
    j = (k + l) // 2
    while k - l > 1:
        j = (k + l) // 2
        if R[j] >=y:
            k = j
        else:
            l = j
    if R[l] == y or R[k] == y:
        q = 1

    if p==q==1:
        f+=1
v=1
if f!=len(G)*len(R):
    v=0
ans=max(g)+max(r)
print(ans if v==0 else ans-1)


### FIXED CODE ###

h,w,m=map(int,input().split())
a=[[] for i in range(m)]
g=[0 for i in range(h)]
r=[0 for i in range(w)]

for i in range(m):
    x,y=map(int,input().split())
    a[i].append(x)
    a[i].append(y)
    g[x-1]+=1
    r[y-1]+=1
G=[]
R=[]
d=max(g)
e=max(r)
for i in range(h):
    if g[i]==d:
        G.append(i+1)
for i in range(w):
    if r[i]==e:
        R.append(i+1)
f=0
for i in range(m):
    q=0
    p=0
    x=a[i][0]
    y=a[i][1]
    k=len(G)-1
    l=0
    j=(k+l)//2
    while k-l>1:
        j=(k+l)//2
        if G[j]>=x:
            k=j
        else:
            l=j
    if G[l]==x or G[k]==x:
        p=1

    k = len(R) - 1
    l = 0
    j = (k + l) // 2
    while k - l > 1:
        j = (k + l) // 2
        if R[j] >=y:
            k = j
        else:
            l = j
    if R[l] == y or R[k] == y:
        q = 1

    if p==q==1:
        f+=1
v=1
if f!=len(G)*len(R):
    v=0
ans=max(g)+max(r)
print(ans if v==0 else ans-1)
### BUGGY CODE ###

base = int(input())

data = [[0 for i in range(2)] for j in range(base)]

for num in range(base):
    _num = input()
    _num = _num.split()
    data[num][0] = int(_num[0])
    data[num][1] = int(_num[1])


takahashi = 0
aoki = 0

data.sort()
data.reverse()
_num = 0
for num in range(base):
    if(_num == 0):
        takahashi += data[0][0]
        _num = 1
        data.pop(0)
        data.sort()
        data.reverse()

    elif(_num == 1):
        aoki += data[0][1]
        _num = 0
        data.pop(0)
        data.sort()
        data.reverse()

print(takahashi-aoki)

### FIXED CODE ###

base = int(input())

data = [[0 for i in range(3)] for j in range(base)]

for num in range(base):
    _num = input()
    _num = _num.split()
    data[num][0] = int(_num[0])+int(_num[1])
    data[num][1] = int(_num[0])
    data[num][2] = int(_num[1])

takahashi = 0
aoki = 0
data.sort()
data.reverse()

_num = 0
for num in range(base):
    if(_num == 0):
        takahashi += data[num][1]
        _num = 1

    elif(_num == 1):
        aoki += data[num][2]
        _num = 0

print(takahashi-aoki)
### BUGGY CODE ###

import fractions
from functools import reduce

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

gcds = []

for i in range(n):
    as2 = as_[:]
    del as2[i]
    gcds.append(reduce(fractions.gcd, as2))

print(max(gcds))


### FIXED CODE ###

from fractions import gcd

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

gcd_all = as_.pop()
set_ = {as_[0]}
for a in as_:
    set_ = set(gcd(s, a) for s in set_)
    set_.add(gcd_all)
    gcd_all = gcd(gcd_all, a)

print(max(set_))
### BUGGY CODE ###

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

for i in range(n-1):
    a[i+1] = a[i] + a[i+1]
a.insert(0, 0)
for i in range(m-1):
    b[i+1] = b[i] + b[i+1]
b.insert(0, 0)

x = 0
jmax = 0
for i in range(n+1):
    for j in range(jmax, m+1):
        if b[m-j] > k-a[i]:
            pass
        else:
            jmax = m-j
            if jmax + i > x:
                x = jmax + i
print(x)

### FIXED CODE ###

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

for i in range(n-1):
    a[i+1] = a[i] + a[i+1]
a.insert(0, 0)
for i in range(m-1):
    b[i+1] = b[i] + b[i+1]
b.insert(0, 0)

x = 0
jmax = m
for i in range(n+1):
    for j in range(jmax, -1, -1):
        if b[j] > k-a[i]:
            pass
        else:
            jmax = j
            if jmax + i > x:
                x = jmax + i
            break
print(x)
### BUGGY CODE ###

#!/usr/bin/env python3
import bisect

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

    B = []
    t = 0
    for a in A:
        t += a
        B.append(t)

    i2 = bisect.bisect_left(B, B[N - 1] / 2, lo = 1, hi = N - 2)
    i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
    i3 = bisect.bisect_left(B, (B[N - 1] + B[i2]) / 2, lo = i2 + 1)

    P = B[i1]
    Q = B[i2] - B[i1]
    R = B[i3] - B[i2]
    S = B[N - 1] - B[i3]

    min_d = max(P, Q, R, S) - min(P, Q, R, S)
    min_half = B[N - 1] / 2 - min_d
    max_half = B[N - 1] / 2 + min_d

    i2_lo = bisect.bisect_left(B, min_half, lo = 1, hi = N - 2)
    i2_hi = bisect.bisect_left(B, max_half, lo = i2_lo, hi = N - 2)

    for i2 in range(i2_lo, i2_hi + 1):
        if min_d * 2 < abs(B[N - 1] - 2 * B[i2]):
            continue

        i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
        i3 = bisect.bisect_left(B, (B[N - 1] + B[i2]) / 2, lo = i2 + 1)
        i1_lo = i1_hi = i1
        i3_lo = i3_hi = i3
        if B[i1] * 2 != B[i2] and 0 < i1:
            i1_lo -= 1
        if B[i3] * 2 != B[N - 1] + B[i2] and i2 + 1 < i3:
            i3_lo -= 1

        for i1 in range(i1_lo, i1_hi + 1):
            for i3 in range(i3_lo, i3_hi + 1):
                P = B[i1]
                Q = B[i2] - B[i1]
                R = B[i3] - B[i2]
                S = B[N - 1] - B[i3]
                d = max(P, Q, R, S) - min(P, Q, R, S)
                if d < min_d:
                    min_d = d


    print(min_d)


if __name__ == '__main__':
    main()



### FIXED CODE ###

#!/usr/bin/env python3
import bisect

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

    B = []
    t = 0
    for a in A:
        t += a
        B.append(t)

    T = B[N - 1]

    i2 = bisect.bisect_left(B, T / 2, lo = 1, hi = N - 2)
    i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
    i3 = bisect.bisect_left(B, (T + B[i2]) / 2, lo = i2 + 1)

    P = B[i1]
    Q = B[i2] - B[i1]
    R = B[i3] - B[i2]
    S = T - B[i3]

    min_d = max(P, Q, R, S) - min(P, Q, R, S)
    min_half = T / 2 - min_d
    max_half = T / 2 + min_d

    i2_lo = bisect.bisect_left(B, min_half, lo = 1, hi = N - 2)
    i2_hi = bisect.bisect_left(B, max_half, lo = i2_lo, hi = N - 2) + 1

    for i2 in range(i2_lo, i2_hi):
        if min_d * 2 < abs(T - 2 * B[i2]):
            continue

        i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
        i3 = bisect.bisect_left(B, (T + B[i2]) / 2, lo = i2 + 1)
        i1_lo, i1_hi = i1, i1 + 1
        i3_lo, i3_hi = i3, i3 + 1
        if B[i1] * 2 != B[i2] and 0 < i1:
            i1_lo -= 1
        if B[i3] * 2 != T + B[i2] and i2 + 1 < i3:
            i3_lo -= 1

        for i1 in range(i1_lo, i1_hi):
            P = B[i1]
            Q = B[i2] - B[i1]
            for i3 in range(i3_lo, i3_hi):
                R = B[i3] - B[i2]
                S = T - B[i3]
                d = max(P, Q, R, S) - min(P, Q, R, S)
                if d < min_d:
                    min_d = d


    print(min_d)


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

from scipy.misc import comb
n, a, b = map(int, input().split())
ans = 1
if n % 2 == 0:
    nn = n
else:
    nn = n + 1
for k in range(1, nn // 2):
    ans += 2 * comb(n, k, exact = True)
if n % 2 == 0:
    ans += comb(n, n // 2, exact = True)
ans -= comb(n, a, exact = True) + comb(n, b, exact = True)
print(ans % (10**9 + 7))

### FIXED CODE ###

MOD = pow(10, 9) + 7

def modinv(a, mod):
    return pow(a, mod - 2, mod) % mod

def comb(n, r, mod):
    r = min(r, n - r)
    res = 1
    for i in range(r):
        res = res * (n - i) % mod
        res = res * modinv(i + 1, mod) % mod
    return res

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

ans = (pow(2, n, MOD) - 1 - comb(n, a, MOD) - comb(n, b, MOD)) % MOD

print(ans)