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

def popcnt(n):
    c = (n & 0x5555) + ((n>>1) & 0x5555)
    c = (c & 0x3333) + ((c>>2) & 0x3333)
    c = (c & 0x0f0f) + ((c>>4) & 0x0f0f)
    c = (c & 0x00ff) + ((c>>8) & 0x00ff)
    return c

N = int(input())
X = []
Y = []
P = []
for _ in range(N):
    x, y, p = map(int, input().split())
    X.append(x)
    Y.append(y)
    P.append(p)

DX = [[0] * (1 << N) for _ in range(N)]
DY = [[0] * (1 << N) for _ in range(N)]

for i, x in enumerate(X):
    for k in range(1 << N):
        d = abs(x)
        for j, xx in enumerate(X):
            if k & (1 << j):
                d = min(d, abs(xx - x))
        DX[i][k] = d * P[i]
for i, y in enumerate(Y):
    for k in range(1 << N):
        d = abs(y)
        for j, yy in enumerate(Y):
            if k & (1 << j):
                d = min(d, abs(yy - y))
        DY[i][k] = d * P[i]

ANS = [1 << 100] * (N + 1)

for i in range(1 << N):
    m = i ^ ((1 << N) - 1)
    j = m
    pci = popcnt(i)
    while 1:
        ans = 0
        for k in range(N):
            ans += min(DX[k][i], DY[k][j])
        
        pc = pci + popcnt(j)
        ANS[pc] = min(ANS[pc], ans)
        
        if not j:
            break
        j = m & (j - 1)

print(*ANS, sep = "\n")


### FIXED CODE ###

N = int(input())
X = []
Y = []
P = []
for _ in range(N):
    x, y, p = map(int, input().split())
    X.append(x)
    Y.append(y)
    P.append(p)

DX = [[0] * (1 << N) for _ in range(N)]
DY = [[0] * (1 << N) for _ in range(N)]

for i, x in enumerate(X):
    for k in range(1 << N):
        d = abs(x)
        for j, xx in enumerate(X):
            if k & (1 << j):
                d = min(d, abs(xx - x))
        DX[i][k] = d * P[i]
for i, y in enumerate(Y):
    for k in range(1 << N):
        d = abs(y)
        for j, yy in enumerate(Y):
            if k & (1 << j):
                d = min(d, abs(yy - y))
        DY[i][k] = d * P[i]

ANS = [1 << 100] * (N + 1)
PC = [0] * (1 << N)
for i in range(1, 1 << N):
    j = i ^ (i & (-i))
    PC[i] = PC[j] + 1

RA = []
for i in range(1 << N):
    t = []
    for j in range(N):
        if i & (1 << j):
            t.append(j)
    RA.append(tuple(t))


mm = (1 << N) - 1
for i in range(1 << N):
    m = i ^ mm
    j = m
    while 1:
        ans = 0
        for k in RA[i^j^mm]:
            ans += min(DX[k][i], DY[k][j])
        
        pc = PC[i] + PC[j]
        ANS[pc] = min(ANS[pc], ans)
        
        if not j:
            break
        j = m & (j - 1)

print(*ANS, sep = "\n")
### BUGGY CODE ###

H, N = map(int, input().split())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

# 個数制限なしナップサック
# i番目までの魔法を使ったときにHダメージを実現できるときの最小の魔力
dp = [[float('inf')]*(H+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H+1):
        # i番目の魔法を使わない時
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        # i番目の魔法を使う時
        dp[i+1][min(H, j+A[i])] = min(dp[i][j]+B[i], dp[i+1][j]+B[i], dp[i+1][min(j+A[i], H)])

print(dp[N][H])


### FIXED CODE ###

H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]
# i番目までの魔法を使った時にjを削るために必要な最小のコスト
dp = [[10**10]*(H+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H+1):
        # 使わない場合
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        # 使う場合
        dp[i+1][min(j+magic[i][0], H)] = min(dp[i+1][min(j+magic[i][0], H)], dp[i+1][j] + magic[i][1])
print(dp[N][H])
### BUGGY CODE ###

N, C, K = map(int, input().split())

T = []
for _ in range(N):
    T.append(int(input()))
T.sort()

buss = []
x, *T = T
bus = [x]
while T:
    while T:
        t, *T = T
        if t <= x + K and len(bus) < C:
            bus.append(t)
        else:
            x = t
            buss.append(bus)
            bus = [x]
            break
buss.append(bus)
print(len(buss))

### FIXED CODE ###

N, C, K = map(int, input().split())

T = sorted([int(input()) for _ in range(N)])

x = T[0]
p = 1
b = 1
for i in range(1, N):
    if T[i] <= x + K and p < C:
        p += 1
    else:
        x = T[i]
        b += 1
        p = 1
print(b)
### BUGGY CODE ###

import sys
from collections import Counter


def factorial(N: int, mod: int) -> int:
    res = 1
    for i in range(1, N+1):
        res *= i
        res %= mod
    return res


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

if S[0] == 'W' or S[-1] == 'W':
    print(0)
    sys.exit()

op = [0]*(2*N)
op[0] = False
ct_L = 1
ans = 1
for i in range(1, 2*N):
    if S[i] == S[i-1]:
        if op[i-1] is False:
            op[i] = True
            ans *= ct_L
            ct_L -= 1
        else:
            op[i] = False
            ct_L += 1
    else:
        if op[i-1] is False:
            op[i] = False
            ct_L += 1
        else:
            op[i] = True
            ans *= ct_L
            ct_L -= 1

ct_L, ct_R = Counter(op).values()
if ct_L != ct_R:
    print(0)
    sys.exit()

mod = 10**9+7
print(factorial(N, mod) * ans % mod)


### FIXED CODE ###

import sys
from math import factorial

N = int(input())
S = input()
mod = 10**9+7

if S[0] == 'W' or S[-1] == 'W':
    print(0)
    sys.exit()

op = "L"
for i in range(1, 2*N):
    if S[i] == S[i-1]:
        op += 'R' if op[i-1] == 'L' else 'L'
    else:
        op += 'R' if op[i-1] == 'R' else 'L'

if op.count('L') != N:
    print(0)
    sys.exit()

ct_L, ans = 0, 1

for i in op:
    if i == 'L':
        ct_L += 1
    else:
        ans *= ct_L
        ct_L -= 1
    ans %= mod


print(factorial(N) * ans % mod)
### BUGGY CODE ###

import numpy as np

n = int(input())
s = [int(i=='#') for i in input()]

idx = [i for i, x in enumerate(s)
       if x==1]

if len(idx)==0 or len(idx)==n:
  print(0)
  
else:  
  s = np.array(s)

  ans = []

  for i in idx:
    s_ = np.array([0]*(i) + [1]*(n-i))
    ans.append((s!=s_).sum())

  print(np.min(ans))

### FIXED CODE ###

import numpy as np

n = int(input())
s = [int(i=='#') for i in input()]

blacks = 0
whites = np.sum(np.array(s)==0)
ans = [blacks+whites]

for x in s:
  if x==1:
    blacks += 1
  else:
    whites -= 1

  ans.append(blacks + whites)

print(np.min(ans))
### BUGGY CODE ###

n = int(input())

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

def myindex(l, x, default=-1):
    if x in l:
        return l.index(x)
    else:
        return default

cnt = 0
c = 0

for i in range(1, n+1):
  b = myindex(a, i, default=-1)
  c = b
  if b == -1:
    break
  else:
    cnt += 1
    del a[:b+1]

if cnt == 0:
  print('-1')

else:
  print(n - cnt)

### FIXED CODE ###

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

card = 1
cnt = 0

for i in a:
  if i == card:
    card += 1
  else:
    cnt += 1

if cnt == n:
  print('-1')

else:
  print(cnt)
### BUGGY CODE ###

from copy import deepcopy
h,w,n = (int(i) for i in input().split())
c1,ans = [[] for i in range(w)],0
for i in range(h):
	s = input()
	for j in range(w): c1[j].append(int(s[j]))
if n<4:
	for i in range(1,h):
		for j in range(w):
			c,m,a = deepcopy(c1),0,0
			del c[j][i]
			c[j] = [0]+c[j]
			while 1:
				d = []
				for k in range(i-h,-h,-1):
					k2 = 0
					while k2<w-n+1:
						if c[k2][k] and all(c[k2][k]==c[k2+k3][k] for k3 in range(1,n)):
							b = n
							for k3 in range(k2+n,w):
								if c[k2][k]==c[k3][k]: b+=1
								else: break
							d.append((h+k,k2,b))
							k2+=b
						else: k2+=1
				if d:
					for k,k2,k3 in d:
						a+=(2**m)*c[k2][k]*k3
						for k4 in range(k2,k2+k3): del c[k4][k]
					for k,k2,k3 in d:
						for k4 in range(k2,k2+k3): c[k4] = [0]+c[k4]
				else: break
				m+=1
			ans = max(ans,a)
print(ans)

### FIXED CODE ###

from copy import deepcopy
h,w,n = (int(i) for i in input().split())
c1,ans = [[] for i in range(w)],0
for i in range(h):
	s = input()
	for j in range(w): c1[j].append(int(s[j]))
if n<4:
	if h==30: z = 25
	else: z = h//2
	for i in range(z,h):
		for j in range(w):
			c,m,a = deepcopy(c1),0,0
			del c[j][i]
			c[j].insert(0,0)
			while 1:
				d = []
				for k in range(i-h,-h,-1):
					k2 = 0
					while k2<w-n+1:
						if c[k2][k] and all(c[k2][k]==c[k2+k3][k] for k3 in range(1,n)):
							b = n
							for k3 in range(k2+n,w):
								if c[k2][k]==c[k3][k]: b+=1
								else: break
							d.append((h+k,k2,b))
							k2+=b
						else: k2+=1
				if d:
					for k,k2,k3 in d:
						a+=(2**m)*c[k2][k]*k3
						for k4 in range(k2,k2+k3): del c[k4][k]
					for k,k2,k3 in d:
						for k4 in range(k2,k2+k3): c[k4].insert(0,0)
				else: break
				m+=1
			ans = max(ans,a)
print(ans)
### BUGGY CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)

    def add(self, i, x=1):
        i += 1
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get_sum(self, i):
        i += 1
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i & -i
        return x

    # Return sum for [l, r)
    def get_sum_range(self, l, r):
        return self.get_sum(r - 1) - self.get_sum(l - 1)


def main():
    N = int(readline())
    S = readline().strip()
    Q = int(readline())
    query = [readline().split() for _ in range(Q)]

    bit = [BIT(N) for _ in range(26)]
    for i, c in enumerate(S):
        bit[ord(c) - ord('a')].add(i)

    S = list(S)
    ans = []

    for q in query:
        if q[0] == '1':
            i = int(q[1]) - 1
            c = q[2]
            bit[ord(S[i]) - ord('a')].add(i, -1)
            bit[ord(c) - ord('a')].add(i, 1)
            S[i] = c
        else:
            res = 0
            l, r = int(q[1]) - 1, int(q[2]) - 1
            for i in range(26):
                if bit[i].get_sum_range(l, r + 1):
                    res += 1
            ans.append(res)

    print(*ans, sep='\n')

    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)

    def add(self, i, x=1):
        i += 1
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get_sum(self, i):
        i += 1
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i & -i
        return x

    # Return sum for [l, r)
    def get_sum_range(self, l, r):
        return self.get_sum(r - 1) - self.get_sum(l - 1)


def main():
    N = int(readline())
    S = readline().strip()
    Q = int(readline())

    S = list(S)

    tree = [BIT(N) for _ in range(26)]
    for i, c in enumerate(S):
        tree[ord(c) - ord('a')].add(i)

    ans = []
    for _ in range(Q):
        A = readline().split()
        if A[0] == '1':
            i, c = int(A[1]) - 1, A[2]
            if S[i] != c:
                tree[ord(S[i]) - ord('a')].add(i, -1)
                tree[ord(A[2]) - ord('a')].add(i, 1)
                S[i] = c
        else:
            l, r = int(A[1]) - 1, int(A[2]) - 1
            tmp = 0
            for i in range(26):
                if tree[i].get_sum_range(l, r + 1) > 0:
                    tmp += 1
            ans.append(tmp)

    print('\n'.join(map(str, ans)))
    return


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

n = int(input(''))

xs = []
for i in range(n):
    xs.append(int(input('')))

for i in range(n):
    print(max(xs[0:i] + xs[i+1:]))


### FIXED CODE ###

n = int(input(''))

xs = []
for i in range(n):
    xs.append(int(input('')))

n1 = max(xs)
n2 = sorted(xs)[-2]

for x in xs:
    if x == n1:
        print(n2)
    else:
        print(n1)
### BUGGY CODE ###

import numpy as np


def count_lower(A, x):
    # Aの要素のうちxより小さいものの個数
    return np.searchsorted(A, x, side='left')


def count_higher(A, x):
    # Aの要素のうちxより大きいものの個数
    return len(A)-np.searchsorted(A, x, side='right')


def count_pair(A, x):
    # A内のペアで積がxより小さいものの個数
    N = len(A)
    cnt = 0
    for n in range(N - 1):
        if A[n] < 0:
            y = x // A[n]
            # n+1番以降でyより大きいものの個数
            cnt += count_higher(A[n+1:], y)
        elif A[n] > 0:
            y = -(-x // A[n])
            # n+1番以降でyより小さいものの個数
            cnt += count_lower(A[n+1:], y)
        else:
            if x > 0:
                cnt += N - n - 1
    return cnt


# count_pair(x)<Kをみたすxの最大値を求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A.sort()
inf = 10 ** 18 + 1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(A, c) < K:
        l = c
    else:
        r = c
print(l)


### FIXED CODE ###

import numpy as np


def count_pair(x):
    # A内のペアで積がxより小さいものの個数
    # まず(i,j)と(j,i)を重複して数える
    cnt = 0
    # A[i]<0なる各iに対してA[j]>x/A[i]なるjの個数
    cnt += (N-np.searchsorted(A, x//A_nega, side='right')).sum()
    if x > 0:
        # 各iに対してA[j]=0なるjの個数
        cnt += len(A_zero)*N
    # A[i]>0なる各iに対してA[j]<x/A[i]なるjの個数
    cnt += np.searchsorted(A, -(-x//A_posi), side='left').sum()
    # i=jを除いてから2で割る
    cnt = (cnt-(A**2 < x).sum())//2
    return cnt


# count_pair(x)<Kをみたすxの最大値を二分探索で求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A = np.array(A)
A = np.sort(A)
A_posi = A[A > 0]
A_zero = A[A == 0]
A_nega = A[A < 0]
inf = 10**18+1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(c) < K:
        l = c
    else:
        r = c
print(l)
### BUGGY CODE ###

n = int(input())
tris = list(map(int,input().split()))
tris.sort()
cnt = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        low = j
        high = n
        while high - low > 1:
            mid = low + (high - low) // 2
            if tris[i] < tris[j] + tris[mid] and tris[j] < tris[i] + tris[mid] and tris[mid] < tris[i] + tris[j]:
                low = mid
            else:
                high = mid
        cnt += low - j
print(cnt)


### FIXED CODE ###

import bisect
n = int(input())
tris = list(map(int,input().split()))
tris.sort()
cnt = 0
for i in range(n-2):
    a = tris[i]
    for j in range(i+1,n-1):
        b = tris[j]
        r = bisect.bisect_left(tris, a+b)
        cnt += r - j - 1
print(cnt)
### BUGGY CODE ###

from bisect import bisect_left,bisect_right

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

A.sort()

hi = 10**18+1
lo = -10**18-1

def solve(N,K,A,hi,lo):
    
    while hi-lo > 1:
        mid = (hi+lo)//2
        under_mid = 0
    
        for a in A:
            if a == 0:
                if mid > 0:
                    under_mid += N
            elif a > 0:
                under_mid += bisect_left(A,-(-mid//a))
            else:
                under_mid += N-bisect_right(A,mid//a)
            if a**2 < mid:
                under_mid -= 1
        under_mid //= 2
    
        if under_mid < K:
            lo = mid
        else:
            hi = mid
    return lo

print(solve(N,K,A,hi,lo))

### FIXED CODE ###

#!/usr/bin/env python3
#import sys; sys.stdin=open('input_file.txt')
#------------------------------------------
import numpy as np

N,K = map(int,input().split())
A = np.array(input().split(),dtype=np.int64)

A = np.sort(A)

pos = A[A>0]
neg = A[A<0]
zero = len(A[A==0])

hi = 10**18+1
lo = -10**18-1

while hi-lo > 1:
    mid = (hi+lo)//2
    under_mid = 0

    if mid > 0: under_mid += N*zero
    under_mid += np.searchsorted(A,-(-mid//pos),side='left').sum()
    under_mid += (N-np.searchsorted(A,mid//neg,side='right')).sum()
    under_mid -= np.count_nonzero(A*A < mid)
    under_mid //= 2

    if under_mid < K:
        lo = mid
    else:
        hi = mid

print(lo)
### BUGGY CODE ###

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

routes = [[False] * N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    routes[a-1][b-1] = True
    routes[b-1][a-1] = True

cnt_nice = 0
for i in range(len(H)):
    is_highest = True
    for j in range(len(H)):
        if routes[i][j] and H[j] >= H[i]:
            is_highest = False
            break
    if is_highest:
        cnt_nice = cnt_nice + 1
print(cnt_nice)

### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
highest = [True for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    if H[a] == H[b]:
        highest[a] = False
        highest[b] = False
    elif H[a] > H[b]:
        highest[b] = False
    else:
        highest[a] = False
print(len([h for h in highest if h]))
### BUGGY CODE ###

from collections import Counter

import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
ab_list = []
for _ in range(M):
    a, b = map(int, input().split())
    ab_list.append([a,b])    

nodes_color = {node:0 for node in range(1, N+1)}#set([a for ab in ab_list for a in ab])}
def func(v,c):
    if nodes_color[v] == 0:
        nodes_color[v] = c
    elif nodes_color[v] == -c:
        return False
    else:
        return True
    
    for ab in ab_list:
        if v in ab:
            for a in ab:
                if a==v:
                    continue
                if not func(a, -c):
                    return False
    return True

def bipartite_graph_check():
    for i in range(1,N+1):
        if nodes_color[i] == 0:
            if not func(i,1):
#                 print("Not Bipartite graph")
                return False
    return True

if bipartite_graph_check():
    b,w = Counter(nodes_color.values()).values()
    print(int(b*w-M))
else:
    print(int(N*(N-1)/2-M))


### FIXED CODE ###

from collections import Counter
import sys
sys.setrecursionlimit(1000000)
N,M = map(int, input().split())
 
# 隣接リスト
l = [[] for i in range(N+1)] 
for i in range(M):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

nodes_color = {node:0 for node in range(1, N+1)}#set([a for ab in ab_list for a in ab])}

nibu = True
stack = [1]

nodes_color[1] = 1

while stack:
    node = stack.pop()
    for next_node in l[node]:
        if nodes_color[next_node]==0:
            stack.append(next_node)
            nodes_color[next_node] = - nodes_color[node]
        else:
            if nodes_color[next_node]==nodes_color[node]:
                nibu = False
                break
    if not nibu:
        break

if nibu:
    b,w = Counter(nodes_color.values()).values()
    print(int(b*w-M))
else:
    print(int(N*(N-1)/2-M))
### BUGGY CODE ###

N = int(input())
X = list(map(int, input().split()))
for i in range(N):
    tmp = sorted(X[:i] + X[i+1:])[::-1]
    print(tmp[(N-1)//2])


### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
Y = sorted(X)
a, b = Y[N//2], Y[N//2-1]
for i in range(N):
    if X[i] < a:
        print(a)
    else:
        print(b)
### BUGGY CODE ###

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

s = 1
d = 1
last = 0
for i in range(n):
    s *= a[i]
    if i - k >= 0:
        d*=a[i-k]
    num = s // d

    #print(f'{num} {last}')
    if i-1 >= k-1:
        if last >= num:
            print('No')
        else:
            print('Yes')
    last = num

### FIXED CODE ###

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

for i in range(k, n):
    if a[i] <= a[i-k]:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

k,s = map(int, input().split())
cnt = 0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s :
                cnt += 1

print(cnt)


### FIXED CODE ###

k,s = map(int, input().split())
cnt = 0

for x in range(k+1):
    for y in range(k+1):
        if 0 <= s-(x+y) <= k:
            cnt += 1




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

def main():
    n = int(input())
    a = list(map(int, input().split()))
    tmp = []
    is_unique = True
    for i in range(n):
        for j in tmp:
            if j == a[i]:
                is_unique = False
                break
        if not is_unique:
            break
        tmp.append(a[i])
    
    if is_unique:
        print("YES")
    else:
        print("NO")


if __name__=="__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    tmp = {}
    is_unique = True
    for i in range(n):
        if a[i] in tmp:
            is_unique = False
            break
        tmp[a[i]] = a[i]
    
    if is_unique:
        print("YES")
    else:
        print("NO")


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

# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
a = [int(input()) for i in range(m)]

inf=float("inf")

fib_memo = [1]
if 1 in a:
    fib_memo.append(0)
else:
    fib_memo.append(1)

if 1 in [a[i] - a[i-1] for i in range(1,m)]:
    print(0)
    import sys
    sys.exit()
else:
    cur_fib_i = 2
    while cur_fib_i <= n:
        if cur_fib_i in a:
            fib_memo.append(0)
        else:
            fib_memo.append(fib_memo[cur_fib_i-1] + fib_memo[cur_fib_i-2])
        cur_fib_i += 1
print(fib_memo[n]%1000000007)
#print(fib_memo)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
a = [int(input()) for i in range(m)]

inf=float("inf")

fib_memo = [-inf for i in range(n+1)]
fib_memo[0] = 1
if 1 in a:
    fib_memo[1]=0
else:
    fib_memo[1]=1
for i in a:
    fib_memo[i]=0

if 1 in [a[i] - a[i-1] for i in range(1,m)]:
    print(0)
    import sys
    sys.exit()
else:
    cur_fib_i = 2
    while cur_fib_i <= n:
        if fib_memo[cur_fib_i]==0:
            pass
        else:
            fib_memo[cur_fib_i] = fib_memo[cur_fib_i-1] + fib_memo[cur_fib_i-2]
        cur_fib_i += 1
print(fib_memo[n]%1000000007)
#print(fib_memo)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import bisect
import numpy as np

n, k = map(int, input().split())
ls = np.array(list(map(int, input().split())))
inf = float("inf")
dp = [inf]*n
dp[0] = 0
dp[1] = abs(ls[1] - ls[0])

for i in range(2, n):
    start = max(0, i-k)
    dp[i] = np.min(dp[start:i] + abs(ls[start:i] - ls[i]))

print(int(dp[n-1]))


### FIXED CODE ###

n,k = map(int,input().split())
ls = list(map(int,input().split()))
dp = [10000000000] *n
dp[0] = 0
dp[1] = abs(ls[1]-ls[0])
p = 10000000000
for i in range(2,n):
    for j in range(i-k,i):
        if (dp[j] >= p) or (abs(ls[j] - ls[i]) >= p):
            pass
        else:
            a = dp[j] + abs(ls[j] - ls[i])
            if a < p:
                p = a
                a = 0
            else:
                a = 0
    dp[i] = p
    p = 10000000000
print(dp[n-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

outList = []
for line in sys.stdin.readlines():
    List = map(int, line.strip().split())

    [a, b] = List

    # LCM
    LCM = 1
    for i in xrange(2, max(a, b)):
        while(a % i == 0 and b % i == 0):
            LCM *= i
            a /= i
            b /= i

    # GCD
    GCD = List[0] * b

    print LCM, GCD

### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys

def isprime(n):
    for i in xrange(2, int(n ** 0.5)+1 ):
        if n % i == 0: return False
    return True


outList = []
for line in sys.stdin.readlines():
    List = map(int, line.strip().split())

    [a, b] = List

    # LCM
    LCM = 1
    i = 1
    while( i <= min(a, b) ):
        i += 1
        if not isprime(i): continue
        while(a % i == 0 and b % i == 0):
            LCM *= i
            a /= i
            b /= i

    # GCD
    GCD = List[0] * b

    print LCM, GCD
### BUGGY CODE ###

def main():
    n,a,b = map(int,input().split())
    MOD = 10**9 +7
    s = pow(2,n,MOD)-1
    P_ni = 1
    F_i = 1

    for i in range(1,b + 1):
        P_ni*=(n-i+1)%MOD
        F_i*= i % MOD
        if i == a or i == b:
            s-=P_ni*pow(F_i,MOD-2,MOD)
    print(s%MOD)

if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
    n,a,b = map(int,input().split())
    MOD = 10**9 +7
    s = pow(2,n,MOD)-1
    P_ni = 1
    F_i = 1


    for i in range(1,b + 1):
        P_ni=P_ni*(n-i+1)%MOD
        F_i=F_i* i % MOD
        if i == a or i == b:
            s-=P_ni*pow(F_i,MOD-2,MOD)



    print(s%MOD)

if __name__=='__main__':
    main()