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

import sys

def parent(i):
    return (i + 1) / 2 - 1

def left(i):
    return 2 * i + 1

def right(i):
    return 2 * i + 2

def sibling(i):
    if i % 2 == 0:
        return i - 1
    else:
        return i + 1

def insert(S, k):
    S.append(k)
    idx = len(S) - 1
    while True:
        p = parent(idx)
        if p < 0 or S[idx] <= S[p]:
            break
        else:
            S[idx], S[p] = S[p], S[idx]
            idx = p
    #print S

def extract(S):
    print S[0]
    S[0] = S[-1]
    S.pop()

    idx = 0
    while True:
        l, r = left(idx), right(idx)
        if l < len(S) and S[idx] < S[l] and (r < len(S) and S[r] <= S[l] or r >= len(S)):
            S[idx], S[l] = S[l], S[idx]
            idx = l
        elif r < len(S) and S[idx] < S[r]:
            S[idx], S[r] = S[r], S[idx]
            idx = r
        else:
            break
    #print S

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    lines.pop()

    S = []
    for line in lines:
        if line[0] == "i":
            insert(S, int(line[7:]))
        else:
            extract(S)

### FIXED CODE ###

import sys

def insert(k):
    global S, last
    S[last] = k
    idx = last
    while True:
        p = (idx + 1) / 2 - 1
        if S[idx] <= S[p]:
            break
        else:
            S[idx], S[p] = S[p], S[idx]
            idx = p
    last += 1

def maxHeapify(i):
    global S, last
    l = 2 * i + 1
    r = 2 * i + 2

    if l < last and S[l] > S[i]:
        largest = l
    else:
        largest = i

    if r < last and S[r] > S[largest]:
        largest = r

    if largest != i:
        S[i], S[largest] = S[largest], S[i]
        maxHeapify(largest)

def extract():
    global S, last
    print S[0]
    last -= 1
    S[0], S[last] = S[last], 0
    maxHeapify(0)

lines = sys.stdin.readlines()
lines.pop()

S = [0] * 2000001
S[2000000] = 2000000000
last = 0
for line in lines:
    if line[0] == "i":
        insert(int(line[7:]))
    else:
        extract()
### BUGGY CODE ###

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

dp = [-1 for _ in range(max_w + 1)]
dp[0] = 0

for i in range(n):
    w, v = map(int, input().split())
    queue = list()
    for i in range(max_w, w - 1, -1):
        dp[i] = max(dp[i], dp[i - w] + v)

print(max(dp))

### FIXED CODE ###

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

dp = [-1 for _ in range(max_w + 1)]
dp[0] = 0

for i in range(n):
    w, v = map(int, input().split())
    queue = list()
    for i in range(max_w, w - 1, -1):
        dp[i] = max(dp[i], dp[i - w] + v)

print(max(dp))
### BUGGY CODE ###

from collections import deque
import copy
def solve(maze, start):
  memo = [[False]*len(maze[0]) for _ in range(len(maze))]
  q = deque()
  q.append([start,0])
  ans = 0
  while q:
    cur, cnt = q.popleft()
    ans = max(ans, cnt)
    memo[cur[0]][cur[1]] = True
    for y, x in zip((0,0,1,-1),(1,-1,0,0)):
      if maze[cur[0]+y][cur[1]+x] == "." and not memo[cur[0]+y][cur[1]+x]:
        q.append([[cur[0]+y,cur[1]+x],cnt+1])
  return ans


H, W = map(int, input().split())
Maze = [["#"]*(W+2)]+[["#"]+list(input())+["#"] for _ in range(H)] + [["#"]*(W+2)]
Ans = 0
sy = 1
while sy <= H:
  sx = 1
  while sx <= W:
    if Maze[sy][sx] == ".":
      Ans = max(Ans, solve(Maze, [sy, sx]))
    sx += 1
  sy += 1
print(Ans)

### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]


def f(i, j):
    t = [[-1] * W for _ in range(H)]
    t[i][j] = 0
    q = [(i, j)]
    while q:
        y, x = q.pop(0)
        if y - 1 >= 0 and S[y - 1][x] != '#' and t[y - 1][x] == -1:
            t[y - 1][x] = t[y][x] + 1
            q.append((y - 1, x))
        if y + 1 < H and S[y + 1][x] != '#' and t[y + 1][x] == -1:
            t[y + 1][x] = t[y][x] + 1
            q.append((y + 1, x))
        if x - 1 >= 0 and S[y][x - 1] != '#' and t[y][x - 1] == -1:
            t[y][x - 1] = t[y][x] + 1
            q.append((y, x - 1))
        if x + 1 < W and S[y][x + 1] != '#' and t[y][x + 1] == -1:
            t[y][x + 1] = t[y][x] + 1
            q.append((y, x + 1))
    return max(max(tt) for tt in t)


result = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '#':
            result = max(result, f(i, j))
print(result)
### BUGGY CODE ###

n = int(input())
s = [str(input()) for _ in range(n)]
ans = 0
for i in range(n):
    s[i] = sorted(s[i])
 
 
for i in range(n):
    for j in range(i,):
        if s[i] == s[j]:
            ans += 1
 
print(ans)

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
for i in range(n):
  s[i] = ''.join(sorted(s[i]))
t = {}
for i in range(n):
  if s[i] in t:
    t[s[i]] += 1
  else:
    t[s[i]] = 1
print(sum(t[k] * (t[k] -1) // 2 for k in t))
### BUGGY CODE ###

n,t=map(int,input().split())
dp=[[[0,0] for i in range(t)] for j in range(n+1)]
food=[list(map(int,input().split())) for i in range(n)]
food.sort(key=lambda x:x[1],reverse=True)
food.sort(key=lambda x:x[0])
for i in range(n):
  for j in range(t):
    if j<food[i][0]:
      dp[i+1][j]=dp[i][j]
    else:
      dp[i+1][j][0]=max(dp[i][j][0],dp[i][j-food[i][0]][0]+food[i][1])
      if dp[i][j][0]>=dp[i][j-food[i][0]][0]+food[i][1]:
        dp[i+1][j][1]=dp[i][j][1]
      else:
        dp[i+1][j][1]=i
ans=0
for i in range(n+1):
  last=0
  for j in range(dp[i][t-1][1]+1,n):
    if food[j][1]>last:last=food[j][1]
  if ans<dp[i][t-1][0]+last:
    ans=dp[i][t-1][0]+last
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,t=map(int,input().split())
dp=[[0 for i in range(t)] for j in range(n+1)]
food=[list(map(int,input().split())) for i in range(n)]
foodmax=[0]*n
food.sort(key=lambda x:x[1],reverse=True)
food.sort(key=lambda x:x[0])
foodmax[-1]=food[-1][1]
for i in range(n-1)[::-1]:
  foodmax[i]=max(foodmax[i+1],food[i][1])
foodmax+=[0]
for i in range(n):
  for j in range(t):
    if j<food[i][0]:
      dp[i+1][j]=dp[i][j]
    else:
      dp[i+1][j]=max(dp[i][j],dp[i][j-food[i][0]]+food[i][1])
      
ans=0
for i in range(n):
  if ans<dp[i+1][t-1]+foodmax[i+1]:
    ans=dp[i+1][t-1]+foodmax[i+1]
print(ans)
### BUGGY CODE ###

import sys

s = input()
t = input()

def replacement(word, a, b):
    return word.replace(a, "0").replace(b, a).replace("0", b)

yet_list = []
for i in range(len(s)):
    if s[i] != t[i]:
        if s[i] in yet_list:
            print("No")
            sys.exit()
        if not s[i] in yet_list:
            s = replacement(s, s[i], t[i])
            yet_list.append(s[i])
if s == t:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import sys
s = input()
t = input()
yetlist = {}
yetlist2 = {}
for i in range(len(s)):
    if s[i] in yetlist:
        if t[i] != yetlist[s[i]]:
            print("No")
            sys.exit()
    else:
        yetlist[s[i]] = t[i]
    if t[i] in yetlist2:
        if s[i] != yetlist2[t[i]]:
            print("No")
            sys.exit()
    else:
        yetlist2[t[i]] = s[i]   
            
print("Yes")
### BUGGY CODE ###

n = int(input())
s = input()
l = [[0] * n for _ in range(n)]
ans = 0

for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        if i >= j and s[i] == s[j]:
            l[i][j] += 1
            
            if i < n-1 and j < n-1 and l[i+1][j+1] > 0:
                l[i][j] += l[i+1][j+1]
                
        now = min(l[i][j], i - j)
        ans = max(ans, now)

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
l = [[0] * n for _ in range(n)]
ans = 0

for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        if i >= j and s[i] == s[j]:
            l[i][j] += 1
            
            if i < n-1 and j < n-1 and l[i+1][j+1] > 0:
                l[i][j] += l[i+1][j+1]
                
        now = min(l[i][j], i - j)
        ans = max(ans, now)

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

n = int(input())
l = []
for i in range(n):
    a = int(input())
    l.append(a)
M = max(l)
for i in range(n):
    if M == l[i]:
         print(sorted(l)[-2])
    else:
        print(M)

    

### FIXED CODE ###

n = int(input())
l = []
for i in range(n):
    a = int(input())
    l.append(a)
M = max(l)
m = sorted(l)[-2]
for i in range(n):
    if M == l[i]:
         print(m)
    else:
        print(M)
### BUGGY CODE ###

h, n = map(int, input().split())
a = []
b = []
for _ in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
 
dp = [float("inf")] * (2 * 10000 + 1)
dp[0] = 0
for i in range(h):
    for j in range(n):
        if (i + a[j]) > 2 * 10000:
            dp[2 * 10000] = min(dp[2 * 10000], dp[i] + b[j])
            continue
        dp[i + a[j]] = min(dp[i + a[j]], dp[i] + b[j])
 
ans = float('inf')
for j in range(h, 2 * 10000 + 1):
    ans = min(ans, dp[j])
print(ans)

### FIXED CODE ###

h, n = map(int, input().split())
a = []
b = []
for _ in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
 
dp = [float("inf")] * (2 * 10000 + 1)
dp[0] = 0
for i in range(h):
    for j in range(n):
        if (i + a[j]) > 2 * 10000:
            dp[2 * 10000] = min(dp[2 * 10000], dp[i] + b[j])
            continue
        dp[i + a[j]] = min(dp[i + a[j]], dp[i] + b[j])
 
ans = float('inf')
for j in range(h, 2 * 10000 + 1):
    ans = min(ans, dp[j])
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
A_set = set(A)
A_set_len = len(A_set)
rewrite_set = A_set_len - K

A_dict = {}
for i in A_set:
    A_dict[i] = A.count(i)

A_dict_values = sorted(A_dict.values())

ans = 0
if rewrite_set > 0:
    ans = sum(A_dict_values[:rewrite_set])

print(ans)

### FIXED CODE ###

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

A_dict = {x:0 for x in A_set}
for i in A:
    A_dict[i] += 1
A_dict = sorted(A_dict.items(), key=lambda x:x[1])

ans = 0
if len(A_set) > K:
    for i in range(len(A_set) - K):
        ans += A_dict[i][1]
        
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
h = [0] + h
cost = [0] * (n+1)
cost[1] = 0
cost[2] = abs(h[1]-h[2])
for i in range(3, n+1):
    c = cost[i-1] + abs(h[i-1]-h[i])
    for j in range(max(1, i-k), i-1):
        c_ = cost[j] + abs(h[j]-h[i])
        if c_ < c:
            c = c_
    cost[i] = c
for i in range(k+1, n+1):
    c = cost[i-1] + abs(h[i-1]-h[i])
    for j in range(i-k, i-1):
        c_ = cost[j] + abs(h[j]-h[i])
        if c_ < c:
            c = c_
    cost[i] = c
print(cost[n])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
c = [0] * n
for i in range(1, n):
    x=h[i]
    c[i] = min([c[j]+abs(x-h[j]) for j in range(max(0, i-k), i)])
print(c[n-1])
### BUGGY CODE ###

# encoding:utf-8

import itertools
from collections import defaultdict


def main():
	n = int(input())
	s = input()

	left = s[:n]
	right = s[n:]
	right = right[::-1]

	ans = 0
	#print(left, right)
	for n_r in range(n+1):
		d_left = defaultdict(lambda: 0)
		d_right = defaultdict(lambda: 0)
		#print([1 if x >= n_r else 0 for x in range(n)])
		pts = itertools.combinations(list(range(n)), r = n_r)
		
		for pt in pts:
			#print(pt)
			b_l = "".join([left[i] for i in range(n) if i in pt])
			r_l = "".join([left[i] for i in range(n) if i not in pt])

			d_left[(b_l, r_l)] += 1

			b_r = "".join([right[i] for i in range(n) if i in pt])
			r_r = "".join([right[i] for i in range(n) if i not in pt])

			d_right[(b_r, r_r)] += 1

		for key in d_left:
#			print(n_r, key, d_left[key], d_right[key])
			ans += d_left[key] * d_right[key]

	print(ans)

if __name__ == '__main__':
	main()


### FIXED CODE ###

# encoding:utf-8

import itertools
from collections import defaultdict


def main():
	n = int(input())
	s = input()

	left = s[:n]
	right = s[n:]
	right = right[::-1]

	ans = 0
	#print(left, right)
	for n_r in range(n+1):
		d_left = defaultdict(lambda: 0)
		d_right = defaultdict(lambda: 0)
		#print([1 if x >= n_r else 0 for x in range(n)])
		pts = itertools.combinations(list(range(n)), r = n_r)
		
		for pt in pts:
			#print(pt)
			b_l = ""
			r_l = ""
			b_r = ""
			r_r = ""
			for i in range(n):
				if i in pt:
					b_l += left[i]
					b_r += right[i]
				else:
					r_l += left[i]
					r_r += right[i]

			d_left[(b_l, r_l)] += 1
			d_right[(b_r, r_r)] += 1

		for key in d_left:
#			print(n_r, key, d_left[key], d_right[key])
			ans += d_left[key] * d_right[key]

	print(ans)

	

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

import fractions
k = int(input())
ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      ans += fractions.gcd(a, fractions.gcd(b, c))
print(ans)

### FIXED CODE ###

import math
k = int(input())
ans = k**3 - (k-1)**3
for a in range(2,k+1):
  for b in range(2,k+1):
    tmp = math.gcd(a,b)
    for c in range(2,k+1):
      ans += math.gcd(tmp, c)
print(ans)
### BUGGY CODE ###

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

ans=0
for r in range(N//R+1):
  for g in range(N//G+1):
    if R*r+G*g>N: continue
    if (N-R*r-G*g)%B!=0: continue
    ans+=1
print(ans)

### FIXED CODE ###

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

ans=0
for r in range(N//R+1):
  for g in range(N//G+1):
    if R*r+G*g>N: continue
    if (N-R*r-G*g)%B!=0: continue
    ans+=1
print(ans)
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(N)]

LR = []
for s in S:
    left, right = 0, 0
    for ss in s:
        if ss == "(":
            left += 1
        else:
            if left:
                left -= 1
            else:
                right += 1
    LR.append([left, right])
#print(LR)

plus = []
minus = []
for l, r in LR:
    if l >= r:
        plus.append([l, r])
    else:
        minus.append([l, r])
        
plus.sort(key = lambda x: x[1])
minus.sort(key = lambda x: -x[0])

cnt = 0
for l, r in plus + minus:
    cnt -= r
    if cnt < 0:
        print("No")
        exit()
    cnt += l
        
if cnt == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = int(input())
S = [input() for i in range(N)]

LR = []
for s in S:
    left, right = 0, 0
    for ss in s:
        if ss == "(":
            left += 1
        else:
            if left:
                left -= 1
            else:
                right += 1
    LR.append([left, right])
#print(LR)

plus = []
minus = []
for l, r in LR:
    if l >= r:
        plus.append([l, r])
    else:
        minus.append([l, r])
        
plus.sort(key = lambda x: x[1])
minus.sort(key = lambda x: -x[0])

cnt = 0
for l, r in plus + minus:
    cnt -= r
    if cnt < 0:
        print("No")
        exit()
    cnt += l
        
if cnt == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

s=list(input().split())
N=int(s[0])
M=int(s[1])
count=0
total=0
a = list(input().split())
for i in range(N):
  a[i]=int(a[i])
while(count<M):
  a[a.index(max(a))]=a[a.index(max(a))]//2
  count+=1

for i in range(N):
  total=total+a[i]
  
print(total)
  

### FIXED CODE ###

from sys import stdin
import heapq

s=stdin.readline().rstrip().split()
N=int(s[0])
M=int(s[1])

a=stdin.readline().rstrip().split()
for i in range(N):
  a[i]=int(a[i])*(-1)
  
heapq.heapify(a)
for i in range(M):
  t=-(-heapq.heappop(a)//2)
  heapq.heappush(a,t)
print(sum(a)*(-1))
### BUGGY CODE ###

from collections import defaultdict
import itertools
d = defaultdict(int)
x='MARCH'
for i in range(5):
  d[x[i]]=i+1
x=[0]*5
def sub(a,b):
  return abs(a[0]-b[0])+abs(a[1]-b[1])

H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
N=H*W
P=[0]*(N)
for h in range(H):
  for w in range(W):
    P[A[h][w]-1]=(h,w)
X=[]
for d in range(D):
  _=[sub(P[i%N],P[i-D]) for i in range(d+D,N+D,D)]
  X.append(_)

Q=int(input())
for q in range(Q):
  l,r=map(int,input().split())
  l,r=l-1,r-1
  if l>r:
    r+=N
  g=l%D
  ans=0
  for i in range(l,r,D):
    ans+=X[g][(i%N)//D]
  print(ans)

### FIXED CODE ###

from collections import defaultdict
import itertools
d = defaultdict(int)
x='MARCH'
for i in range(5):
  d[x[i]]=i+1
x=[0]*5
def sub(a,b):
  return abs(a[0]-b[0])+abs(a[1]-b[1])

H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
N=H*W
P=[0]*(N)
for h in range(H):
  for w in range(W):
    P[A[h][w]-1]=(h,w)
X=[]
for d in range(D):
  _=[0]+[sub(P[i%N],P[i-D]) for i in range(d+D,N+D,D)]
  cumsum = list(itertools.accumulate(_))
  X.append(cumsum)

Q=int(input())
for q in range(Q):
  l,r=map(int,input().split())
  l,r=l-1,r-1
  g=l%D
  if l>r:
    r+=N
    ans=X[g][-1]-X[g][l//D]
    ans+=X[g][r//D]-X[g][0]
  else:
    ans=X[g][r//D]-X[g][l//D]
  
  print(ans)
### BUGGY CODE ###

n,k,*a = map(int,open(0).read().split())
a = [i-1 for i in a]
c = [0]
for i in range(n):
  nt = a[c[-1]]
  if nt in c:
    ws = c.index(nt)
    wst = c[:ws]
    wrt = c[ws:]
    wr = len(wrt)
  else:
    c.append(nt)
#print(c,ws,wst,wr,wrt)
if ws > k:
  ans = wst[k]
else:
  ans = wrt[(k-ws)%wr]
print(ans+1)

### FIXED CODE ###

def main():
  n,k,*a = map(int,open(0).read().split())
  c = [0]
  visit = [False]*n
  visit[0] = True
  for i in range(n):
    nt = a[c[-1]]-1
    if visit[nt]:
      ws = c.index(nt)
      wst = c[:ws]
      wrt = c[ws:]
      wr = len(wrt)
      break
    else:
      c.append(nt)
      visit[nt] = True
  if ws > k:
    ans = wst[k]
  else:
    ans = wrt[(k-ws)%wr]
  print(ans+1)
main()
### BUGGY CODE ###

n = int(input())
s = input()
count_r = s.count("R")
count_g = s.count("G")
count_b = s.count("B")
sum = count_r * count_g * count_b
minus = 0

for i in range(n):
    for j in range(1,(n-i)//2 + 1):
        if i+2*j <= n-1:
            tem = [s[i], s[i+j], s[i+2*j]]
            tem.sort()
            if tem[0] != tem[1] and tem[1] != tem[2]:
                minus += 1
            

print(sum - minus)

### FIXED CODE ###

n = int(input())
s = input()
count_r = s.count("R")
count_g = s.count("G")
count_b = s.count("B")
sum = count_r * count_g * count_b
minus = 0

for i in range(n-2):
    for j in range(2, n-i+1, 2):
        if i+j <= n-1:
            tem = [s[i], s[i+j//2], s[i+j]]
            if tem[0] != tem[1] and tem[0] != tem[2] and tem[1] != tem[2]:
                minus += 1
            

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

# B
N, K = map(int, input().split())
h = list(map(int, input().split()))

cost = [0]*N

cost[0] = 0
for i in range(1,N):
    cost_tmp = [abs(h[i - (1+j)] - h[i]) + cost[i - (1+j)] for j in range(0, min(K,i))]
    cost[i] = min(cost_tmp)

print(cost[-1])

    

### FIXED CODE ###

# B(TLE) 2104ms

import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))
cost = np.zeros(N, dtype="int32")

cost[0] = 0
for i in range(1,N):
    start = 0 if i < K else i-K
    cost[i] = np.min(cost[start:i] + np.abs(h[i]-h[start:i]))

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

def main():
    h, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    dp = [10**10]*(h+1)
    dp[0] = 0
    for i in range(h):
        p = dp[i]
        for a, b in ab:
            j = i+a
            if j > h:
                j = h
            dp[j] = min(dp[j], p+b)
    print(dp[-1])


main()


### FIXED CODE ###

def main():
    h, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    dp = [10**10]*(h+1)
    dp[0] = 0
    for i in range(h):
        for a, b in ab:
            j = i+a
            if j > h:
                j = h
            dp[j] = min(dp[j], dp[i]+b)
    print(dp[-1])


main()
### BUGGY CODE ###

def choose(n,r):
    res = 1
    fac = 1
    for i in range(r):
        res *= n-i
        res %= MOD
        fac *= i+1
        fac %= MOD
    return res*pow(fac,MOD-2,MOD)%MOD        

n,a,b = list(map(int,input().split()))
t=0
ans = pow(2,n)-1
MOD = 10**9+7

ans -= choose(n,a)
ans -= choose(n,b)

ans = ans % MOD
print(int(ans))

### FIXED CODE ###

def choose(n,r):
    res = 1
    fac = 1
    for i in range(r):
        res *= n-i
        res %= MOD
        fac *= i+1
        fac %= MOD
    return res*pow(fac,MOD-2,MOD)%MOD        

n,a,b = list(map(int,input().split()))
MOD = 10**9+7
t=0
ans = pow(2,n,MOD)-1


ans -= choose(n,a)
ans -= choose(n,b)

ans = ans % MOD
print(int(ans))
### BUGGY CODE ###

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

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

### FIXED CODE ###

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

L = [0]*N
for i in range(N):
    L[A[i]-1] = i+1
print(*L)
### BUGGY CODE ###

x,y,a,b,c=map(int,input().split())
r=sorted(list(map(int,input().split())),reverse=True)
g=sorted(list(map(int,input().split())),reverse=True)
w=sorted(list(map(int,input().split())),reverse=True)

p=sorted(r[:x]+g[:y],reverse=True)

i=0
ans=0
while i<x+y:
    if w==[] or p[0]>w[0]: 
        ans+=p.pop(0)
    else: 
        ans+=w.pop(0)
    i+=1
print(ans)

### FIXED CODE ###

x,y,a,b,c=map(int,input().split())
r=sorted(list(map(int,input().split())),reverse=True)
g=sorted(list(map(int,input().split())),reverse=True)
w=list(map(int,input().split()))

p=sorted(r[:x]+g[:y]+w,reverse=True)
print(sum(p[:x+y]))
### BUGGY CODE ###

N = int(input())
S = []
n = 0
eq = True


for i in range(N):
    s = input()
    n += 1
    length = len(S)
    for i in range(length):
        if s == S[i]:
            eq = False
    if not eq:
        n -= 1
    S.append(s)

print(n)

### FIXED CODE ###

N = int(input())

S = [input() for i in range(N)]
print(len(list(set(S))))
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

def next_positions(current_position):
    output = []
    for udrl in [[0,1],[1,0]]:
        y = current_position[0]+udrl[0]
        x = current_position[1]+udrl[1]
        if 0 <= y <= H-1 and 0 <= x <= W-1:
            output.append([y,x])
    return output

d = deque([[0,0]])
distance = [[float("inf")]*W for _ in range(H)]
if s[0][0] == ".":
    distance[0][0] = 0
else:
    distance[0][0] = 1

while d:
    current_position = d.popleft()
    for q in next_positions(current_position):
        if s[q[0]][q[1]] == ".":
            distance[q[0]][q[1]] = min(distance[q[0]][q[1]], distance[current_position[0]][current_position[1]])
        else:
            distance[q[0]][q[1]] = min(distance[q[0]][q[1]], distance[current_position[0]][current_position[1]] + 1)
        d.append(q)

print(distance[H-1][W-1])

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

d = deque([[0,0,s[0][0]]])
distance = [[float("inf")]*W for _ in range(H)]
if s[0][0] == ".":
    distance[0][0] = 0
else:
    distance[0][0] = 1

while d:
    y, x, c = d.popleft()
    for new_y, new_x in ([int(y)+1, int(x)], [int(y), int(x)+1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1:
            if c == "." and s[new_y][new_x] == "#":
                new_cost = distance[y][x] + 1
            else:
                new_cost = distance[y][x]
            if new_cost < distance[new_y][new_x]:
                distance[new_y][new_x] = new_cost
                d.append([new_y, new_x, s[new_y][new_x]])

print(distance[H-1][W-1])