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

import math
def calc_factors(n):
    factors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            j = n // i
            if j != i: factors.append(j)
            factors.append(i)
    return factors

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

ans = 0
done = [0] * (10 ** 6 + 1)

for i in range(n):
    num = a[i]
    if i < n-1 and a[i] == a[i+1]:
        done[num] = 1
        continue

    factors = calc_factors(num)
    for f in factors:
        if done[f]:
            break
    else:
        ans += 1
        done[num] = 1

print(ans)


### FIXED CODE ###

import math
def sieve(n, done):
    for i in range(n, 10**6+1, n):
        done[i] = 1

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

ans = 0
done = [0] * (10 ** 6 + 1)

for i in range(n):
    num = a[i]
    if i < n-1 and a[i] == a[i+1]:
        if i > 0 and a[i] == a[i-1]:
            continue
        sieve(num, done)
        continue
    
    if not done[num]:
        sieve(num, done)
        ans += 1

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

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

cost = [1001001001] * n
cost[0] = 0

for i in range(n):
    if i < n-k:
        for j in range(i+1, i+k+1):
            cost[j] = min(cost[j], cost[i] + abs(h[i] - h[j]))
    else:
        for j in range(i, n):
            cost[j] = min(cost[j], cost[i] + abs(h[i] - h[j]))

print(cost[-1])




### FIXED CODE ###

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

cost = [1001001001] * n
cost[0] = 0

for i in range(n):
    if i < n-k:
        for j in range(i+1, i+k+1):
            cost[j] = min(cost[j], cost[i] + abs(h[i] - h[j]))
    else:
        for j in range(i, n):
            cost[j] = min(cost[j], cost[i] + abs(h[i] - h[j]))

print(cost[-1])
### BUGGY CODE ###

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

ans = [A.index(i)+1 for i in range(1,N+1)]


print(' '.join(map(str, ans)))


### FIXED CODE ###

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

ans = [0]*N
# ans = [A.index(i)+1 for i in range(1,N+1)]
for i in range(N):
    ans[A[i]-1] = i+1

print(' '.join(map(str, ans)))
### BUGGY CODE ###

from math import sqrt
from itertools import product

import numpy as np

def helper(N,D):
  banned = list()
  for x in range(0, int(sqrt(D/2))+2):
    if D > x*x:
      y = sqrt(D-x*x)
      if y == int(y):
        y = int(y)

        for a,b in {(x,y),(y,x)}:
          for s,t in product((1,-1), repeat=2):
            banned.append((s*a,t*b))

  M = N*2

  grid = np.zeros((M,M), dtype=int)

  p0 = (0,0)
  while p0:
    stack = [p0]
    grid[stack[0]] = 1
    while stack:
      x,y = stack.pop()
      t = grid[x,y]
      for dx,dy in banned:
        xx,yy = x+dx,y+dy
        if 0 <= xx < M and 0 <= yy < M and grid[xx,yy] == 0:
          grid[xx,yy] = -t

    l = np.transpose(np.nonzero(grid==0))
    if l.size > 0:
      p0 = tuple(l[0])
    else:
      p0 = None


  return grid

N,D1,D2 = map(int,input().split())
M = N*2
g1 = helper(N,D1)
g2 = helper(N,D2)

if np.count_nonzero(g1==1)*2 > M*M:
  g1 = g1==1
else:
  g1 = g1==-1

if np.sum(g1*g2) > 0:
  ans = g1&(g2==1)
else:
  ans = g1&(g2==-1)


for x,y in np.transpose(np.nonzero(ans))[:N*N]:
  print(x,y)


### FIXED CODE ###

from math import sqrt
from itertools import product

import numpy as np

def helper(N,D):
  if D%2 == 1:
    grid = np.zeros((N,N),dtype=bool)
    grid[::2,:] = True
    grid[:,1::2] = ~grid[:,1::2]
  elif D%4 == 2:
    grid = np.zeros((N,N),dtype=bool)
    grid[::2,:] = True
  else:
    M = (N-1)//2+1
    D //= 4
    g = helper(M, D)
    grid = np.zeros((2*M,2*M),dtype=bool)
    grid[::2,::2] = g
    grid[1::2,::2] = g
    grid[::2,1::2] = g
    grid[1::2,1::2] = g
    grid = grid[:N,:N]
  return grid


N,D1,D2 = map(int,input().split())
M = N*2
g1 = helper(N*2,D1)
g2 = helper(N*2,D2)
ans = g1&g2


for x,y in np.transpose(np.nonzero(ans))[:N*N]:
  print(x,y)
### BUGGY CODE ###

n,k=map(int,input().split())
s=str(input())

import numpy as np
line = np.zeros([2*n,],dtype=np.int)
counter1 = 0
counter0 = 0
ind = 0
for i in range(n):
    c = int(s[i])
    if ind%2 ==0:
        if c == 1:
            counter1 += 1
        else:
            counter0 += 1
            line[ind] = counter1
            counter1 = 0
            ind+=1
    elif ind%2 ==1:
        if c == 0:
            counter0 += 1
        else:
            counter1 += 1
            line[ind] = counter0
            counter0 = 0
            ind+=1

if ind%2 ==0:
        line[ind] = counter1
        ind+=1
elif ind%2 ==1:
        line[ind] = counter0
        ind+=1
        
if ind%2 ==0:
        line[ind] = 0
        ind+=1
line = line[:ind]    
#print(line)

if (len(line)//2)<=k:
    print(n)
else:
    new = line.copy()
    for i in range(1,2*k+1):
        new = new+np.roll(line, i)
    new = new[2*k:]
    new = new[0::2]
    #print(new)
    print(new.max())

### FIXED CODE ###

#4
n,k=map(int,input().split())
s=str(input())

import numpy as np
line = np.zeros([2*n,],dtype=np.int)
counter1 = 0
counter0 = 0
ind = 0
for i in range(n):
    c = int(s[i])
    if ind%2 ==0:
        if c == 1:
            counter1 += 1
        else:
            counter0 += 1
            if ind == 0:
                line[ind] = counter1
            else:
                line[ind] = line[ind-1]+counter1
            counter1 = 0
            ind+=1
    elif ind%2 ==1:
        if c == 0:
            counter0 += 1
        else:
            counter1 += 1
            line[ind] = line[ind-1] + counter0
            counter0 = 0
            ind+=1

if ind%2 ==0:
        if ind == 0:
                line[ind] = counter1
        else:
                line[ind] = line[ind-1]+counter1
        ind+=1
elif ind%2 ==1:
        line[ind] = line[ind-1] + counter0
        ind+=1
        
if ind%2 ==0:
        line[ind] = line[ind-1]
        ind+=1
        
line[1:ind+1]  = line[:ind]   
line[0] = 0 
line = line[:ind+1]
#print(line)

if (len(line)//2)<=k:
    print(n)
else:
    maxchain = 0
    for i in range(0,len(line)-2*k,2):
        chain = line[i+2*k+1]-line[i]
        #print(chain)
        if chain>maxchain:
            maxchain=chain
    print(maxchain)
### BUGGY CODE ###

x = int(input())
done=False
for a in range(-9500,9501):
  for b in range(-9500,9501):
    if(not done and a**5-b**5==x):
      print(a,b)
      done=True

### FIXED CODE ###


x = int(input())
for a in range(-300,301):
  if(a<0):
    for b in range(-300,a):
      if(a**5-b**5==x):
        print(a,b)
        break
    else: continue
    break
  else:
    for b in range(-300,a):
      if(a**5-b**5==x):
        print(a,b)
        break
    else: continue
    break
### BUGGY CODE ###

def main():
    M = 1000000007
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    bit_size = len(bin(a[-1])[2:])
    for i in range(n):
        a[i] = bin(a[i])[2:].zfill(bit_size)

    sum = 0
    for i in range(bit_size):
        one = 0
        zero = 0
        for j in range(n):
            if a[j][i] == '1':
                one += 1
            else: 
                zero += 1
        sum += (2**(bit_size - i - 1) % M) * (one % M) * (zero % M)
        sum %= M
    print(sum)

if __name__ == '__main__':
    main()

### FIXED CODE ###

M = 1000000007
def pow(k):
    ans = 1
    for _ in range(k):
        ans *= 2
        ans %= M
    return ans

def main():
    n = int(input())
    a = list(map(int, input().split()))
    bit_size = len(bin(max(a))[2:])
    for i in range(n):
        a[i] = bin(a[i])[2:].zfill(bit_size)

    sum = 0
    for i in range(bit_size):
        one = 0
        zero = 0
        for j in range(n):
            if a[j][i] == '1':
                one += 1
            else: 
                zero += 1
        sum += pow(bit_size - i - 1) * (one % M) * (zero % M)
        sum %= M
    print(sum)

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(M):
    ma = max(A)
    mai = A.index(ma)
    A[mai] = ma//2
print(sum(A))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [-a for a in A]
A = sorted(A)
heapq.heapify(A)
for _ in range(M):
    ma = heapq.heappop(A)
    ma = -((-ma)//2)
    heapq.heappush(A, ma)
    # print(A, ma)
print(-sum(A))
### BUGGY CODE ###

from collections import deque
import numpy as np

H, W = list(map(int, input().split()))
field = [input() for _ in range(H)]
dist = [[5000] * W for _ in range(H)]

def bfs(sy, sx):
  q = deque()
  q.append((sy, sx))
  dist[sy][sx] = 0
  while len(q) > 0:
    y, x = q.popleft()
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
      ny, nx = y + dy, x + dx
      if ny < 0 or ny >= H or nx < 0 or nx >= W:
        continue
      if field[ny][nx] == '#':
        continue
      if dist[ny][nx] < dist[y][x] + 1:
        continue
      dist[ny][nx] = dist[y][x] + 1
      q.append((ny, nx))
      
for y in range(H):
  for x in range(W):
    if field[y][x] == '#':
      bfs(y, x)
print(np.max(np.asarray(dist).flatten()))

### FIXED CODE ###

from collections import deque
import copy

def main():
  H, W = map(int, input().split())
  maps = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if maps[i][j]])
  count = 0
  while True:
    nq = deque()
    while q:
      x, y = q.popleft()
      if x > 0 and not maps[x-1][y]:
        maps[x-1][y] = True
        nq.append((x-1,y))
      if y > 0 and not maps[x][y-1]:
        maps[x][y-1] = True
        nq.append((x,y-1))
      if x < H-1 and not maps[x+1][y]:
        maps[x+1][y] = True
        nq.append((x+1,y))
      if y < W-1 and not maps[x][y+1]:
        maps[x][y+1] = True
        nq.append((x,y+1))
    if nq:
      q = copy.copy(nq)
    else:
        break
    count += 1
  print(count)

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

import math

K = int(input().strip())

ans = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans += math.gcd(a, math.gcd(b,c))

print(ans)

### FIXED CODE ###

import math

K = int(input().strip())

ans = 0
for a in range(1,K+1):
    tmp = 0
    for b in range(1,K+1):
        for c in range(b + 1,K+1):
            tmp += math.gcd(a, math.gcd(b,c))
    tmp *= 2
    for b in range(1, K + 1):
        tmp += math.gcd(a, b)
    ans += tmp

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

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

N = int(input())

ans = 0
for c in range(1, N-1): 
   ans += len(make_divisors(N - c))

print(ans + 1)

### FIXED CODE ###

n = int(input())
ans = 0
for a in range(1, n):
  ans += (n - 1) // a
print(ans)
### BUGGY CODE ###

n, d, a = map(int, input().split())
xh = []
for _ in range(n):
    x, h = map(int, input().split())
    xh.append([x, h])

xh.sort(key=lambda x:x[0])
ind = 0
ans = 0
while ind<n:
    end = xh[ind][0]+2*d
    cnt = (xh[ind][1]+a-1)//a
    ans += cnt
    i = ind
    while i<n and xh[i][0]<=end:
        xh[i][1] = max(xh[i][1]-a*cnt, 0)
        i += 1
    while ind<n and xh[ind][1]==0:
        ind += 1
print(ans)

### FIXED CODE ###

n, d, a = map(int, input().split())
xh = []
for _ in range(n):
    x, h = map(int, input().split())
    h = (h+a-1)//a
    xh.append([x, h])

xh.sort(key=lambda x:x[0])

def bisect(x):
    i_min=0
    i_max=n
    while i_min<i_max:
        i = (i_min+i_max)//2
        if xh[i][0]<=x:
            i_min = i+1
        else:
            i_max = i
    return i_min

ans = 0
accu = 0
out = [0]*(n+1)
for i, (x, h) in enumerate(xh):
    accu -= out[i]
    hp = h-accu
    if hp<=0:
        continue
    accu += hp
    ans += hp
    out[bisect(x+2*d)] += hp 
print(ans)
### BUGGY CODE ###

N,K= map(int,input().split())
x=[0]*N
y=[0]*N
z=[0]*N
for i in range(N):
    x[i],y[i] = map(int,input().split())
    z[i] = (x[i],y[i])
    
ans=float("inf")
for s in x:
    for t in x:
        for u in y:
            for v in y:
                cnt=0
                for zz in z:
                    if s<= zz[0]<=t and u<=zz[1]<=v:
                        cnt +=1
                if cnt >=K:
                    tmp = (t-s)*(v-u)
                    ans = min(ans,tmp)
print(ans)

### FIXED CODE ###

N,K= map(int,input().split())
x=[0]*N
y=[0]*N
z=[0]*N
for i in range(N):
    x[i],y[i] = map(int,input().split())
    z[i] = (x[i],y[i])
    
ans=float("inf")
for s in x:
    for t in x:
        for u in y:
            for v in y:
                cnt=0
                for zz in z:
                    if s<= zz[0]<=t and u<=zz[1]<=v:
                        cnt +=1
                if cnt >=K:
                    tmp = (t-s)*(v-u)
                    ans = min(ans,tmp)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = input()
dp = [[0]*(n+1) for y in range(n+1)]
ans = 0
for i in reversed(range(n)):
    for j in reversed(range(n)):
        if s[i] == s[j] and i > j:
            dp[i][j] = min(dp[i+1][j+1] + 1, i-j)
            ans = max(ans, dp[i][j])
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = input()
dp = [[0]*(n+1) for y in range(n+1)]
ans = 0

for i in range(n):
    a = n-1-i
    for j in range(n):
        b = n-1-j
        if s[a] == s[b]:
            dp[a][b] = dp[a+1][b+1] + 1
for i in range(n):
    for j in range(n):
        now = min(dp[i][j], j-i)
        ans = max(ans, now)
print(ans)
### BUGGY CODE ###

import sys, heapq, bisect, math, fractions
from collections import deque
from collections import Counter
from collections import OrderedDict

N = int(input())

left = 0
right = N - 1
mid = 0
ll = True
rr = True

for _ in range(20):
    if ll:
        print(left, flush=True)
        l = input()
        ll = not ll
    if rr:
        print(right, flush=True)
        r = input()
        rr = not rr

    if l == "Vacant" or r == "Vacant":
        exit()

    mid = (r + l) // 2
    print(mid, flush=True)
    m = input()
    if m == "Vacant":
        exit()

    if (mid - left) % 2 == 0 and l != m:
        right = mid - 1
        rr = True
    elif (right - mid) % 2 == 1 and m == r:
        left = mid + 1
        ll = True


### FIXED CODE ###

import sys, heapq, bisect, math, fractions
from collections import deque
from collections import Counter
from collections import OrderedDict

N = int(input())

left = 0
right = N - 1
mid = 0

print(left, flush=True)
l = input()
if l == "Vacant":
    exit()
    
print(right, flush=True)
r = input()
if r == "Vacant":
    exit()

while left + 1 != right:
    mid = (right + left) // 2
    print(mid, flush=True)
    m = input()
    if m == "Vacant":
        exit()
        
    if ((mid - left) % 2 == 0 and l != m) or ((mid - left) % 2 == 1 and l == m):
        right = mid
        r = m
    else:
        left = mid
        l = m
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import numpy as np

def main():
    #1:初期化
    N,W = map(int,input().split())
    wv = []
    for _ in range(N):
        wv.append(list(map(int,input().split())))
    dp = np.zeros((N+1,W+1), dtype=int)
    #dp2 = [[0]*(W+1) for i in range(N+1)]

    #print(dp1)
    #print(dp2)
    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(1,N+1):
        for j in range(1,W+1):
            if wv[i-1][0] <= j:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
            else:
                dp[i][j] = dp[i-1][j]
            #print(i,j)
            #print(*dp,sep="\n")

    #4:出力
    print(dp[N][W])

if __name__ == '__main__':
    main()

### FIXED CODE ###

"""memo
    numpyでやるときは配列を一気に更新するが(numpy使いたくないのでやらない)，
    このやり方は後ろの方から更新することで後の更新に影響を与えない(考え方すごい)．
    (参考#9889377)
"""

import sys
input = sys.stdin.readline

def main():
    #1:初期化
    N,W = map(int,input().split())
    dp = [0]*(W+1)

    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(N):
        w, v = map(int,input().split())
        for i in range(W, w-1, -1):
            tmp = dp[i-w] + v
            if dp[i] < tmp:
                dp[i] = tmp
        #print(dp,sep="\n")

    #4:出力
    print(max(dp))

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

N,M = map(int,input().split())
L = [0] * N

X,Y,Z = map(int,input().split())
L[X-1] = 1
L[Y-1] = 1 
b = 1

if M == 1:
    print(N-1)
else:
    for i in range(M-1):
        X,Y,Z = map(int,input().split())
        if L[X-1] != 0 and L[Y-1] != 0:
            if L[X-1] != L[Y-1]:
                a = min(L[X-1],L[Y-1])
                for c in L:
                    if c == max(L[X-1],L[Y-1]):
                        c = a
        elif L[X-1] != 0 and L[Y-1] == 0:
            L[Y-1] = L[X-1]
        elif L[X-1] == 0 and L[Y-1] != 0:
            L[X-1] = L[Y-1]
        else:
            b += 1
            L[X-1] = b
            L[Y-1] = b

    L = list(set(L))
    l = len(L)

    print(l)
        

### FIXED CODE ###

class UnionFind:
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n+1)
        self.cnt = 0

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def groupsize(self):
        self.cnt = 0
        for i, x in enumerate(self.par):
            if x == i:
                self.cnt += 1
        return self.cnt
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int,input().split())
A = [list(map(int,input().split())) for i in range(M)]
uf = UnionFind(N)

for i in range(M):
    uf.union(A[i][0]-1, A[i][1]-1)

print(uf.groupsize())
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()

class LazyBit():
    """区間加算、区間取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_sum: 区間[l, r)の和を求める
    l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit0 = [0] * (n + 1)
        self.bit1 = [0] * (n + 1)
    def _add(self, bit, i, val):
        i = i + 1
        while i <= self.n:
            bit[i] += val
            i += i & -i
    def _get(self, bit, i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s
    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(self.bit0, l, -val * l)
        self._add(self.bit0, r,  val * r)
        self._add(self.bit1, l,  val)
        self._add(self.bit1, r, -val)
    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._get(self.bit0, r) + r * self._get(self.bit1, r) \
               - self._get(self.bit0, l) - l * self._get(self.bit1, l)

for _ in range(K):
	bit = LazyBit(N)
	for i, a in enumerate(A):
		bit.add(max(0, i-a), min(N, i+a+1), 1)
	for i in range(N):
		A[i] = bit.get_sum(i, i+1)
	if all(x==N for x in A):
		break

print(*A)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()
for cnt in range(K):
	tmp = [0]*(N+1)

	for i, a in enumerate(A):
		tmp[max(0, i-a)] += 1
		tmp[min(N, i+a+1)] -= 1
	tmp = list(accumulate(tmp))
	A = tmp[:-1]
	if all(x==N for x in A):
		break

print(*A)
### BUGGY CODE ###

import math

def comb_count(n,r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

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



countlist = []

for i in range(1,n+1):
    if i == a or i == b:
        pass
    else:
        countlist.append(i)

result = 0
for i in range(len(countlist)):
    result += comb_count(n,countlist[i])

print(result%(10**9+7))


### FIXED CODE ###

mod = 10**9+7
n,a,b = map(int,input().split())
ans = pow(2,n,mod)-1
comb1 = 1
for i in range(n-a+1,n+1):
    comb1 *= i
    comb1 %= mod
for i in range(1,a+1):
    comb1 *= pow(i,mod-2,mod)
    comb1 %= mod

comb2  = 1
for i in range(n-b+1, n+1):
    comb2 *= i
    comb2 %= mod
for i in range(1,b+1):
    comb2 *= pow(i,mod-2,mod)
    comb2 %= mod

ans -= (comb1+comb2)
ans %= mod
print(ans)
### BUGGY CODE ###

N=int(input())
lis=list(input() for _ in range(N))
se=set(lis)
ans=[]
high=0

for i in se:
  if lis.count(i)>=high:
    high=lis.count(i)
for  j in se:
  if lis.count(j)==high:
    ans.append(j)
ans.sort()

for k in ans:
  print(k)

### FIXED CODE ###

from collections import Counter
N=int(input())
lis=list(input() for _ in range(N))
ans=[]

counter=Counter(lis)
high=counter.most_common()[0][1]

for k,v in counter.most_common():
  if v==high:
    ans.append(k)
  else:
    break
ans.sort()
for i in ans:
  print(i)
### BUGGY CODE ###

import sys
from collections import Counter
from collections import deque
import math
import fractions
import bisect
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,m=mp()
l=[lmp() for i in range(n)]
l.append([10**6,10**6])
val=[]
ans=0
l=sorted(l,key=lambda x: x[0],reverse=True)
for i in range(1,m+1):
    while l[-1][0]==i:
        q=l.pop()
        val.append(q[1])
    val.sort()
    if len(val)>0:
        ans+=val.pop()
print(ans)

### FIXED CODE ###

import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,m=mp()
l=[lmp() for i in range(n)]
l.append([10**6,10**6])
val=[]
heapq.heapify(val)
ans=0
c=0
l=sorted(l,key=lambda x: x[0],reverse=True)
for i in range(1,m+1):
    while l[-1][0]==i:
        q=l.pop()
        heapq.heappush(val,(-1)*q[1])
        c+=1
    if c>0:
        ans-=heapq.heappop(val)
        c-=1
print(ans)