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

import numpy as np
N, W = map(int, input().split(' '))
pair = [tuple(map(int, input().split(' '))) for _ in range(N)]
dp = np.zeros((N+1, W+1), dtype=int)
for i in range(N):
    for sum_w in range(W+1):
        if sum_w >= pair[i][0]:
            dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w-pair[i][0]] + pair[i][1])
        else:
            dp[i+1][sum_w] = dp[i][sum_w]
print(dp[-1][-1])

### FIXED CODE ###

N, W = map(int, input().split(' '))
pair = [tuple(map(int, input().split(' '))) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
    for sum_w in range(W+1):
        if sum_w >= pair[i][0]:
            dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w-pair[i][0]] + pair[i][1])
        else:
            dp[i+1][sum_w] = dp[i][sum_w]
print(dp[-1][-1])
### BUGGY CODE ###

import collections

N,K=map(int,input().split())
P=list(map(int,input().split()))
cnt=0
tmp=0
ans=0
count=0
for i in range(N-K+1):
	#print(P[i:i+K])
	if cnt<sum(P[i:i+K]):
		cnt=sum(P[i:i+K])
		tmp=i
	else:
		cnt=cnt
	#print(cnt)
Q=P[tmp:tmp+K]
count=collections.Counter(Q)
C_K=list(count.keys())
C_V=list(count.values())
R=len(count)
for i in range(R):
	ans+=(C_K[i]*(C_K[i]+1)/(2*C_K[i])*C_V[i])
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
E=[0]*N

for i in range (N):
	E[i]=((P[i]+1)/2)

L=[0]*(N+1)
L[0]=0

for i in range (N):
	L[i+1]=L[i]+E[i]

ans=0

for i in range (K,N+1):
	ans=max(ans,L[i]-L[i-K])

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

n,m=map(int,input().split())
L=[]
for i in range(m):
    L.append(tuple(map(int,input().split())))
T=sorted(L)
p=1
count=1
for i in range(m):
    if p!=T[i][0]:
        count=1
    ind=L.index(T[i])
    L[ind]=(T[i][0],count)
    p=T[i][0]
    count += 1
for i in L:
    num=i[0]*(10**6)+i[1]
    print(str(num).zfill(12))

### FIXED CODE ###

from collections import defaultdict
from bisect import bisect
n,m=map(int,input().split())
l=[tuple(map(int,input().split())) for _ in range(m)]
a=defaultdict(list)
for x,y in sorted(l):
    a[x]+=[y]

for x,y in l:
    z=bisect(a[x],y)
    print('%06d%06d'%(x,z))
### BUGGY CODE ###

def solve(N):
    if N <= 20:
        for i in range(N):
            print(i, flush=True)
            s = input()
            if s == 'Vacant':
                return

    print(0, flush=True)
    low_sex = input()
    if low_sex == 'Vacant':
        return
    print(N - 1, flush=True)
    high_sex = input()
    if high_sex == 'Vacant':
        return
    high, low = N - 1, 0
    while high - low > 1:
        mid = (high + low) // 2
        print(mid, flush=True)
        mid_sex = input()
        if mid_sex == 'Vacant':
            return

        if (mid - low + 1) % 2 == 1 and low_sex == mid_sex:
            high = mid
            high_sex = mid_sex
        elif (mid - low + 1) % 2 == 0 and low_sex != mid_sex:
            high = mid
            high_sex = mid_sex
        elif (high - mid + 1) % 2 == 0 and high_sex != mid_sex:
            low = mid
            low_sex = mid_sex
        else:
            low = mid
            low_sex = mid_sex


if __name__ == '__main__':
    solve(int(input()))
	return 0

### FIXED CODE ###

def get_sex(i):
    print(i, flush=True)
    return input()


def solve(N):
    if N <= 19:
        for i in range(N):
            print(i, flush=True)
            s = input()
            if s == 'Vacant':
                exit()

    low_sex = get_sex(0)
    if low_sex == 'Vacant':
        exit()
    high_sex = get_sex(N - 1)
    if high_sex == 'Vacant':
        exit()

    high, low = N - 1, 0
    while high > low:
        mid = (high + low) // 2
        mid_sex = get_sex(mid)
        if mid_sex == 'Vacant':
            exit()

        if (mid - low) % 2 == 1:
            if mid_sex != low_sex:
                low = mid
                low_sex = mid_sex
            else:
                high = mid
                high_sex = mid_sex
        else:
            if mid_sex != low_sex:
                high = mid
                high_sex = mid_sex
            else:
                low = mid
                low_sex = mid_sex


if __name__ == '__main__':
    solve(int(input()))
### BUGGY CODE ###

from itertools import accumulate as ac
n=int(input())+2
t=[0]+list(map(int,input().split()))+[0]
v=[0]+list(map(int,input().split()))+[0]
s=[0]+list(ac(t))
def f(i,x):
    if s[i]<=x<=s[i+1]:return v[i]
    elif x<s[i]:return v[i]+s[i]-x
    else:return v[i]+x-s[i+1]
c=float("INF")
for i in range(n):
    c=min(c,f(i,0))
e=0
for i in range(1,2*s[-1]+1):
    i=i/2
    d=float("INF")
    for j in range(n):
        d=min(d,f(j,i))
    e+=0.25*(c+d)
    c=d
print(e)

### FIXED CODE ###

from itertools import accumulate as ac
n=int(input())+2
t=[0]+list(map(int,input().split()))+[0]
v=[0]+list(map(int,input().split()))+[0]
s=[0]+list(ac(t))
def f(i,x):
    if s[i]<=x<=s[i+1]:return v[i]
    elif x<s[i]:return v[i]+s[i]-x
    else:return v[i]+x-s[i+1]
c=float("INF")
for i in range(n):
    c=min(c,f(i,0))
e=0
for i in range(1,2*s[-1]+1):
    i=i/2
    d=float("INF")
    for j in range(n):
        d=min(d,f(j,i))
    e+=0.25*(c+d)
    c=d
print(e)
### BUGGY CODE ###

n=int(input())
L=list(sorted(map(int,input().split())))
ans=0

for i in range(n-2):
    a=L[i]
    for j in range(i+1,n-1):
        b=L[j]
        high=n-1
        low=j+1
        if L[high]<a+b:
            ans+=n-j-1
            continue
        if L[low]>=a+b:
            continue
        while high-low>1:
            now=(high+low)//2
            c=L[now]
            if c<a+b:
                low=now
            else:
                high=now
        ans+=low-j
print(ans)

### FIXED CODE ###

n=int(input())
L=list(sorted(map(int,input().split())))
ans=0

for i in range(n-2):
    a=L[i]
    for j in range(i+1,n-1):
        b=L[j]
        high=n-1
        low=j+1
        if L[high]<a+b:
            ans+=n-j-1
            continue
        if L[low]>=a+b:
            continue
        while high-low>1:
            now=(high+low)//2
            c=L[now]
            if c<a+b:
                low=now
            else:
                high=now
        ans+=low-j
print(ans)
### BUGGY CODE ###

#dpp
import sys
sys.setrecursionlimit(10**7)
MOD = 10**9+7
n = int(input())
dp = [[1 for _ in range(2)] for _ in range(n)]
edges = [[] for _ in range(n)]
for _ in range(n-1):
	x, y = map(int, input().split())
	edges[x-1].append(y-1)
	edges[y-1].append(x-1)

def dfs(le, ro):
	for ed in edges[le]:
		if ed == ro:
			continue
		dfs(ed, le)
		dp[le][0] = (dp[le][0] * (dp[ed][0] + dp[ed][1])) % MOD
		dp[le][1] = (dp[le][1] * dp[ed][0]) % MOD
	return

dfs(0, -1)
print((dp[0][0] + dp[0][1]) % MOD)

### FIXED CODE ###

#dpp
import sys
sys.setrecursionlimit(10**7)
MOD = 10**9+7
n = int(input())
dp = [[1 for _ in range(2)] for _ in range(n)]
edges = [[] for _ in range(n)]
for _ in range(n-1):
	x, y = map(int, input().split())
	edges[x-1].append(y-1)
	edges[y-1].append(x-1)

def dfs(le, ro):
	for ed in edges[le]:
		if ed == ro:
			continue
		dfs(ed, le)
		dp[le][0] = (dp[le][0] * (dp[ed][0] + dp[ed][1])) % MOD
		dp[le][1] = (dp[le][1] * dp[ed][0]) % MOD
	return

dfs(0, -1)
print((dp[0][0] + dp[0][1]) % MOD)
### BUGGY CODE ###

n=int(input())
comb=[]
ans=[]


for k in range(1, n+1):
    flag=False
    for x in range(1, k+1):
        for y in range(x, k+1):
            for z in range(y, k+1):
                if (x+y+z)**2 - x*y-y*z-z*x==k:
                    comb.append((x,y,z))
                    flag=True
                    break
    
    if flag:
        pass
    else:
        comb.append((0, 0, 0))


l=len(comb)

for s in range(l):
    if comb[s][0]==comb[s][1]==comb[s][2]==0:
        ans.append(0)
    elif comb[s][0]==comb[s][1]==comb[s][2]!=0:
        ans.append(1)
    elif comb[s][0]!=comb[s][1] and comb[s][1]!=comb[s][2] and comb[s][2]!=comb[s][0]:
        ans.append(6)
    else:
        ans.append(3)

for i in range(l):
    print(ans[i])

### FIXED CODE ###

n=int(input())
cnt=[0]*(n+1)

for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            tmp=x*x + y*y + z*z + x*y + y*z + z*x
            if tmp <=n:
                cnt[tmp]+=1


for i in range(1, n+1):
    print(cnt[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m=map(int, input().split(' '))
p = list(map(int, input().split(' ')))
ab = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
visited = [0]*(n+1)
conlist = [0]*(n+1)
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
stack = []
cnt = 0
for i in range(1,n+1):
    if visited[i] != 1:
        flg = True
        cnt += 1
        stack.append(i)
        connect = []
    while stack:     
        x = stack.pop()
        visited[x] = 1
        connect.append(x)
        for y in graph[x]:
            if visited[y] != 1:
                stack.append(y)
    if flg:
        for i in connect:
            conlist[i] = cnt
        flg = False
ans = 0
for i in range(1,n+1):
    if conlist[p[i-1]] == conlist[i]:
        ans+=1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m=map(int, input().split(' '))
p = list(map(int, input().split(' ')))
ab = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
visited = [0]*(n+1)
conlist = [0]*(n+1)
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
stack = []
cnt = 0
append = stack.append
pop = stack.pop
for i in range(1,n+1):
    if visited[i] != 1:
        cnt += 1
        append(i)
    while stack:
        x = pop()
        visited[x] = 1
        conlist[x] = cnt
        for y in graph[x]:
            if visited[y] != 1:
                append(y)
ans = 0
for i in range(1,n+1):
    if conlist[p[i-1]] == conlist[i]:
        ans+=1
print(ans)
### BUGGY CODE ###

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

b = 10 ** 18
ret = 1
for i in a:
  ret = ret * i
if ret > b:
  print('-1')
else:
  print(ret)

### FIXED CODE ###

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

if 0 in a:
  print(0)
  sys.exit()
  
b = 10 ** 18
ret = 1
for i in a:
  ret = ret * i
  if ret > b:
    print('-1')
    sys.exit()
else:
  print(ret)
### BUGGY CODE ###

from sys import exit

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

count = 0

for r in range(N // R + 1):
	for g in range(N // G + 1):
		if N - r * R - g * G < 0:
			break
		if (N - r * R - g * G) % B == 0:
			count += 1

print(count)


### FIXED CODE ###

from sys import exit

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

count = 0

for r in range(N // R + 1):
	for g in range((N - r * R) // G + 1):
		if (N - r * R - g * G) % B == 0:
			count += 1

print(count)
### BUGGY CODE ###

N = int(input())

g = [[] for _ in range(N+1)]
dist = [[-1]*(N+1) for _ in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
    dist[a][b] = c
    dist[b][a] = c
    
Q, K = map(int, input().split())

cost = [-1] * (N+1)
cost[K] = 0
temp = [[K, 0]]
while temp:
    p = temp.pop()
    gset = set(g[p[0]])
    gset.discard(p[1])
    for q in gset:
        cost[q] = cost[p[0]] + dist[p[0]][q]
        temp.append([q, p[0]])

for i in range(Q):
    x, y = map(int, input().split())
    print(cost[x] + cost[y])


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())

g = [[] for _ in range(N+1)]

for i in range(N-1):
    a, b, c = map(int, input().split())
    g[a].append([b, c])
    g[b].append([a, c])
    
Q, K = map(int, input().split())

cost = [-1] * (N+1)
cost[K] = 0
temp = [K]
while temp:
    p = temp.pop()
    for q in g[p]:
        if cost[q[0]] == -1:
            cost[q[0]] = cost[p] + q[1]
            temp.append(q[0])

for i in range(Q):
    x, y = map(int, input().split())
    print(cost[x] + cost[y])
### BUGGY CODE ###

import heapq
X, Y, Z, K = map(int, input().split())
A_array = list(map(int, input().split()))
B_array = list(map(int, input().split()))
C_array = list(map(int, input().split()))

A_array.sort()
B_array.sort()
C_array.sort()

use_array = [[[0] * Z for i in range(Y)] for i in range(X)]
sum_array = []

candidate = []
heapq.heapify(candidate)

max_sum = A_array[-1] + B_array[-1] + C_array[-1]

heapq.heappush(candidate, (0, X - 1, Y - 1, Z - 1))

for i in range(K):

    s, x, y, z = heapq.heappop(candidate)

    sum_array.append(s)
    if x != 0 and use_array[x - 1][y][z] == 0:
        use_array[x - 1][y][z] = 1
        diff = A_array[x] - A_array[x - 1]
        heapq.heappush(candidate, (s + diff, x - 1, y, z))

    if y != 0 and use_array[x][y - 1][z] == 0:
        use_array[x][y - 1][z] = 1
        diff = B_array[y] - B_array[y - 1]
        heapq.heappush(candidate, (s + diff, x, y - 1, z))

    if z != 0 and use_array[x][y][z - 1] == 0:
        use_array[x][y][z - 1] = 1
        diff = C_array[z] - C_array[z - 1]
        heapq.heappush(candidate, (s + diff, x, y, z - 1))

for ans in sum_array:
    print(max_sum - ans)

### FIXED CODE ###

import heapq
X, Y, Z, K = map(int, input().split())
A_array = list(map(int, input().split()))
B_array = list(map(int, input().split()))
C_array = list(map(int, input().split()))

A_array.sort()
B_array.sort()
C_array.sort()

use_array = []
sum_array = []

candidate = []
heapq.heapify(candidate)

max_sum = A_array[-1] + B_array[-1] + C_array[-1]

heapq.heappush(candidate, (0, X - 1, Y - 1, Z - 1))
use_array.append((X - 1, Y - 1, Z - 1))

for i in range(K):
    s, x, y, z = heapq.heappop(candidate)

    sum_array.append(s)
    if x != 0 and (x - 1, y, z) not in use_array:
        use_array.append((x - 1, y, z))
        diff = A_array[x] - A_array[x - 1]
        heapq.heappush(candidate, (s + diff, x - 1, y, z))

    if y != 0 and (x, y - 1, z) not in use_array:
        use_array.append((x, y - 1, z))
        diff = B_array[y] - B_array[y - 1]
        heapq.heappush(candidate, (s + diff, x, y - 1, z))

    if z != 0 and (x, y, z - 1) not in use_array:
        use_array.append((x, y, z - 1))
        diff = C_array[z] - C_array[z - 1]
        heapq.heappush(candidate, (s + diff, x, y, z - 1))

for ans in sum_array:
    print(max_sum - ans)
### BUGGY CODE ###

p=[1 for i in range(1001)]
p[0]=0
p[1]=0
for i in range(2,1001):
    if p[i]==1:
        for j in range(2,1001):
            if i*j<=1000:
                p[i*j]=0
#print(p[:25])
Prime=[]
for i in range(1001):
    if p[i]==1:
        Prime.append(i)
#print(Prime)
#print(len(Prime))
N=int(input())
L=list(map(int,input().split()))
D={}
for i in L:
    I=i
    for j in Prime:
        if I%j==0:
            if j not in D:
                D[j]=1
            else:
                D[j]+=1
            while I%j==0:
                I//=j
    if I!=1:
        if I not in D:
            D[I]=1
        else:
            D[I]+=1
#print(D)

ans=0
for k,v in D.items():
    if ans<v:
        ans=v
if ans==1:
    print("pairwise coprime")
elif ans==N:
    print("not coprime")
else:
    print("setwise coprime")

### FIXED CODE ###

import time
A=time.time()
p=[1 for i in range(1001)]
p[0]=0
p[1]=0
for i in range(2,1001):
    if p[i]==1:
        for j in range(2,1001):
            if i*j<=1000:
                p[i*j]=0
#print(p[:25])
Prime=[]
for i in range(1001):
    if p[i]==1:
        Prime.append(i)

#print(Prime)
#print(len(Prime))
N=int(input())
L=list(map(int,input().split()))

def gcd(a,b):
    if b>a:
        a,b=b,a
    while a%b!=0:
        a,b=b,a%b
    return b
    
X=L[0]
for i in range(1,N):
    X=gcd(X,L[i])
    if X==1:
        break
if X>1:
    print("not coprime")
    exit()
        
D={}

for I in L:
    B=time.time()
    if B-A>1.9:
        print("pairwise coprime")
        exit()
    for j in Prime:
        if I%j==0:
            if j not in D:
                D[j]=1
            else:
                print("setwise coprime")
                exit()
            while I%j==0:
                I//=j
    if I!=1:
        if I not in D:
            D[I]=1
        else:
            print("setwise coprime")
            exit()
#print(D)

print("pairwise coprime")
### BUGGY CODE ###

N = int(input())
answer = 0
for i in range(N):
    a = i+1
    if(N //a == N % a):
        answer = answer + a
print(answer)

### FIXED CODE ###

N = int(input())
answer = 0
divi=[]
for i in range(1, int(N**0.5)+1):
    if N % i == 0:
        divi.append(i)
        if i != N // i:
            divi.append(N//i)

divi.sort()
divi.pop(0)
for i in reversed(range(len(divi))):
    if N % (divi[i]-1) != N // (divi[i]-1):
        divi.pop(i)
        i = i-1



for i in  range(len(divi)):
    answer = answer + divi[i]-1
print(answer)
### BUGGY CODE ###

N = int(input())
S = []
c = input()
S.extend(c)
if "W" in S and "R" in S:
    for i in range(N):
        min_W = S.index("W")
        max_R = N - 1 - S[::-1].index("R")
        S[::-1]
        if min_W>max_R:
            print(i)
            break
        S[min_W],S[max_R] = S[max_R],S[min_W]
else:
    print(0)

### FIXED CODE ###

N = int(input())
S = []
c = input()
S.extend(c)

if "W" in S and "R" in S:
    t = S.count("R")
    S = S[:t]
    r = S.count("W")
    print(r)
else:
    print(0)
### BUGGY CODE ###

import numpy
h, w, a, b = map(int,input().split())
s = numpy.zeros([h,w],int)
for i in range(b):
    for j in range(a):
        s[i,j] = 1
for i in range(b, h):
    for j in range(a, w):
        s[i,j] = 1
for i in range(h):
    ans = []
    for j in range(w):
        ans.append(str(s[i,j]))
    print("".join(ans))




### FIXED CODE ###

import numpy
h, w, a, b = map(int,input().split())
s = numpy.zeros([h,w],int)
for i in range(h):
    ans = []
    for j in range(w):
        if i < b and j < a:
            ans.append("1")
        elif i < b and a <= j:
            ans.append("0")
        elif b <= i and j < a:
            ans.append("0")
        else:
            ans.append("1")
    print("".join(ans))
### BUGGY CODE ###

n = int(input())
s = input()

cnt = 0
for i in range(n):
    for j in range(i+1, n):
        if s[j] == s[i]: continue
        for k in range(j+1, n):
            if s[k] in [s[j], s[i]]: continue
            if j - i == k - j: continue
            cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()

colors = ['R', 'B', 'G']

cnt = 1
for c in colors:
    cnt *= s.count(c)

for i in range(n):
    w = 1
    while True:
        if i + 2*w >= n: break
        if s[i] != s[i+w] and s[i+w] != s[i+2*w] and s[i+2*w] != s[i]:
            cnt -= 1
        w += 1
print(cnt)
### BUGGY CODE ###

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


def calc(x):
    if A[x] >= K:
        return True
    dp = [False] * K
    dp[0] = True
    ma = 0
    for i in range(N):
        if i == x:
            continue
        for k in range(ma, -1, -1):
            if k + A[i] >= K:
                continue
            dp[k + A[i]] |= dp[k]
        ma = min(K - 1, ma + A[i])

    return sum(dp[K - A[x]:K])


l, r = 0, N - 1
if not calc(N - 1):
    print(N)
    exit()
if calc(0):
    print(0)
    exit()
while r - l > 1:
    mi = (l + r) // 2
    if calc(mi):
        r = mi
    else:
        l = mi

print(r)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)


def calc(x):
    if A[x] >= K:
        return True
    dp = [False] * K
    dp[0] = True
    ma = 0
    for i in range(N):
        if i == x:
            continue
        for k in range(ma, -1, -1):
            if k + A[i] >= K:
                continue
            dp[k + A[i]] |= dp[k]
        ma = min(K - 1, ma + A[i])

    return sum(dp[K - A[x]:K])


l, r = 0, N - 1
if not calc(N - 1):
    print(N)
    exit()
if calc(0):
    print(0)
    exit()
while r - l > 1:
    mi = (l + r) // 2
    if calc(mi):
        r = mi
    else:
        l = mi

print(r)
### BUGGY CODE ###

import sys
from collections import deque
readline = sys.stdin.readline
N = int(readline())

testimonies = [[[], []] for _ in range(N)]
for i in range(N):
    A = int(readline())
    for _ in range(A):
        x, y = map(int, readline().rstrip().split())
        testimonies[i][y].append(x-1)

def check(honest_persons):
    """矛盾がないか検証する"""
    honest_checked = set(honest_persons)  # 宛先を確認済みの正直者の人
    honest_stack = deque(honest_persons)  # 宛先を確認する正直者の人の待ち行列
    honest, liers = honest_persons[:], []  # 正直者の人, 不親切な人

    # 正直者の人の証言も元に、正直者の人/不親切な人を追加していく
    while len(honest_stack) > 0:
        honest_person = honest_stack.popleft()
        honest_checked.add(honest_person)
        next_honest_persons = testimonies[honest_person][1]

        # 検証済み以外の人をstackする
        for person in next_honest_persons:
            if person not in honest_checked:
                honest_stack.append(person)

        honest += testimonies[honest_person][1]
        liers += testimonies[honest_person][0]

    # 矛盾がなければOK
    if len(set(honest) & set(liers)) == 0:
        return True
    else:
        return False

def main():
    # bit全探索する
    ans = 0
    has_checked = []
    for i in range(1, 2**N):
        comb = bin(i)[2:].zfill(N)
        honest_persons = []
        for p, c in enumerate(comb):
            if c == '1':
                honest_persons.append(p)
        
        flag = False
        for checked in has_checked:
            if checked < set(honest_persons):
                flag = True
                break
        
        if flag:
            continue

        if check(honest_persons):
            ans = max(ans, sum(list(map(int, list(comb)))))
        else:
            has_checked.append(set(honest_persons))

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
N = int(sys.stdin.readline())

testimonies = [[-1 for _ in range(N)] for _ in range(N)]
for i in range(N):
    A = int(sys.stdin.readline())
    for _ in range(A):
        x, y = map(int, sys.stdin.readline().rstrip().split())
        testimonies[i][x-1] = y

def check(honest_persons):
    flag = True
    for i in range(N):
        if honest_persons[i]:
            for j in range(N):
                if testimonies[i][j] == -1:
                    continue
                if testimonies[i][j] != honest_persons[j]:
                    flag = False
                    break
    return flag

def main():
    ans = 0
    for i in range(1, 2**N):
        honest_persons = bin(i)[2:].zfill(N)
        honest_persons = list(map(int, list(honest_persons)))

        if check(honest_persons):
            ans = max(ans, sum(honest_persons))

    print(ans)

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

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

def iterative_square_method(N, P, M):

    if P == 0:
        return 1
    elif P%2 == 0:
        return (iterative_square_method(N, P//2, M) ** 2) % M
    else:
        return (N * iterative_square_method(N, P-1, M)) % M

def inv_felmat(a, p):
    return iterative_square_method(a, p-2, p)

all = iterative_square_method(2, n, 10**9 + 7) - 1 
tmp1 = 1
tmp2 = 1
for i in range(n-a+1, n+1):
    tmp1 *= i % (10**9 + 7)
for i in range(1, a+1):
    tmp2 *= i % (10**9 + 7)
tmp1 = (tmp1 * inv_felmat(tmp2, 10**9 + 7)) % (10**9 + 7)
tmp3 = 1
tmp4 = 1
for i in range(n-b+1, n+1):
    tmp3 *= i % (10**9 + 7)
for i in range(1, b+1):
    tmp4 *= i % (10**9 + 7)
tmp3 = (tmp3 * inv_felmat(tmp4, 10**9 + 7)) % (10**9 + 7)

result = all - tmp1 - tmp3
print(result%(10**9 + 7))

### FIXED CODE ###

n, a, b = [int(i) for i in input().split()]
mod = 10**9 + 7
 
total = pow(2, n, mod) - 1
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
 
at = combination(n,a)
bt = combination(n,b)
 
result = total - at - bt
result %= mod
if result < 0:
  result += mod
print(result)