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

import sys
sys.setrecursionlimit(10**9)
n,q = map(int,input().split())
ki = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ki[a].append(b)
    ki[b].append(a)
cnt = [0]*n
for _ in range(q):
    p,x = map(int,input().split())
    p -= 1
    cnt[p] += x

def dfs(cur,prev = -1):
    for nxt in ki[cur]:
        if nxt == prev: continue
        cnt[nxt] += cnt[cur]
        dfs(nxt,cur)

dfs(0)
print(*cnt)

### FIXED CODE ###

from collections import deque
n,q = map(int,input().split())
to = [[] for _ in range(n)]
ans = [0]*n

for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

for i in range(q): 
    p,x = map(int,input().split())
    p -= 1
    ans[p] += x

stack = deque()
stack.append((0,0))
while len(stack) != 0:
    cn,pn = stack.pop()
    for nn in to[cn]:
        if nn == pn:
            continue
        ans[nn] += ans[cn]
        stack.append((nn,cn))

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

n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
inf = float('INF')
bag = [inf for _ in range(10**5+1)]
bag[0] = 0

ans = 0
for w,v in a:
  for i in range(min(v,10**5+1), 10**5+1)[::-1]:
    if bag[i-v] + w < min(bag[i],W+1):
        bag[i] = bag[i-v] + w
        if i > ans:
          ans = i
print(ans)


### FIXED CODE ###

n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
inf = float('INF')
bag = [inf for _ in range(10**5+1)]
bag[0] = 0

ans = 0
for w,v in a:
  for i in range(min(v,10**5+1), 10**5+1)[::-1]:
    if bag[i-v] + w < min(bag[i],W+1):
        bag[i] = bag[i-v] + w
        ans = max(ans, i)
print(ans)
### BUGGY CODE ###

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

r_i = [i for i, x in enumerate(s) if x=='R']
g_i = [i for i, x in enumerate(s) if x=='G']
b_i = [i for i, x in enumerate(s) if x=='B']

ans = 0

for i in range(len(r_i)):
    for j in range(len(g_i)):
        for k in range(len(b_i)):
            ijk = [r_i[i], g_i[j], b_i[k]]
            ijk.sort()
            if ijk[1] - ijk[0] != ijk[2] - ijk[1]:
                ans += 1
print(ans)

### FIXED CODE ###

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

ri = [i for i, x in enumerate(s) if x=='R']
gi = [i for i, x in enumerate(s) if x=='G']
bi = [i for i, x in enumerate(s) if x=='B']

ans = len(ri) * len(gi) * len(bi)

for i in range(n):
    for d in range(n):
        j=i+d
        k=i+2*d
        if k>=n:
            break
        if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
            ans -= 1

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

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = []
c = []
for i in range(q):
    b_i, c_i = map(int, input().split())
    b.append(b_i)
    c.append(c_i)

res = {}
for a_i in a:
    if not a_i in res:
        res[a_i] = 0
    res[a_i] += 1

for b_i, c_i in zip(b, c):
    num = res[b_i] if b_i in res else 0
    res[b_i] = 0
    if not c_i in res:
        res[c_i] = 0
    res[c_i] += num

    ans = 0
    for key, val in res.items():
        ans += key * val
    print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = []
c = []
for i in range(q):
    b_i, c_i = map(int, input().split())
    b.append(b_i)
    c.append(c_i)


res = {}
for a_i in a:
    if not a_i in res:
        res[a_i] = 0
    res[a_i] += 1

ans = 0
for key, val in res.items():
    ans += key * val

for b_i, c_i in zip(b, c):
    num = res[b_i] if b_i in res else 0
    res[b_i] = 0
    if not c_i in res:
        res[c_i] = 0
    res[c_i] += num

    ans += (c_i - b_i) * num

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

# /usr/bin/python3
# -*- coding: utf-8 -*-


if __name__ == '__main__':
    input()
    s_data = [int(c) for c in input().strip()]
    cnt = 0
    last = len(s_data)
    for num in range(1000):
        f = num // 100
        s = (num-f*100) // 10
        t = (num-(f*100+s*10))
        # f = str(f)
        # s = str(s)
        # t = str(t)
        # fflg = False
        # sflg = False
        # for i in range(last):
        #     if not fflg:
        #         fflg = S[i] == f
        #         continue
        #     elif not sflg:
        #         sflg = S[i] == s
        #         continue
        #     elif S[i] == t:
        #         cnt += 1
        #         break
        fflg = False
        sflg = False
        for i in range(last):
            if not fflg:
                fflg = s_data[i] == f
                continue
            elif not sflg:
                sflg = s_data[i] == s
                continue
            elif s_data[i] == t:
                cnt += 1
                break
        

    # 出力
    print(cnt)


### FIXED CODE ###

import copy
import math
import time
 
# a = get_int()
def get_int():
    return int(input())
# a = get_string()
def get_string():
    return input()
# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]
# a_list = get_string_list():
def get_string_list():
    return input().split()
# a, b = get_int_multi()
def get_int_multi():
    return map(int, input().split())
# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))
# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():
 
    idx += 1
'''
 
def main():
    start = time.time()
 
    n = get_int()
    s_list = get_string_char_list()
    s_list = [int(x) for x in s_list]
 
    #n = 30000
    #s_list = [1] * 30000
 
    #ans_set = set([])
 
    #for i in range(0,n):
    #    for ii in range(i+1, n):
    #        for iii in range(ii+1, n):
    #            ans_set.add(int(s_list[i]) * 100 + int(s_list[ii]) * 10 + int(s_list[iii]) * 1)
 
    #print(len(ans_set))
 
    ans = 0
 
    for i in range(0, 1000):
        a = i // 100
        b = (i % 100) // 10
        c = i % 10
 
        find_a = False
        find_b = False
        for ii in s_list:
 
            if (find_a == False) and (ii == a):
                find_a = True
            elif (find_a == True) and (find_b == False) and (ii == b):
                find_b = True
            elif (find_b == True) and (ii == c):
 
                ans += 1
                break
    print(ans)
 
    #print(time.time() - start)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N,C = map(int,input().split())
D = [[int(i) for i in input().split()] for _ in range(C)]
c = [[int(i) for i in input().split()] for _ in range(N)]

D_sum = [[0]*C for _ in range(3)]

for i in range(C):
    for j in range(N):
        for k in range(N):
            D_sum[(j+k)%3][i] += D[c[j][k]-1][i]
            
ans = 1000*500*500
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i==j or j==k or k==i:
                continue
            else:
                ans = min(ans, D_sum[0][i]+D_sum[1][j]+D_sum[2][k])
print(ans)      

### FIXED CODE ###

N,C = map(int,input().split())
D = [[int(i) for i in input().split()] for j in range(C)]
c = [[int(i) for i in input().split()] for j in range(N)]

c_sum = [[0]*C for _ in range(3)]
for i in range(N):
    for j in range(N):
        c_sum[(i+j)%3][c[i][j]-1] += 1

D_sum = [[0]*C for _ in range(3)]
for i in range(C):
    for j in range(C):
        for k in range(3):
            D_sum[k][j] += D[i][j] * c_sum[k][i]

ans = 1000*500*500
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i==j or j==k or k==i:
                continue
            else:
                ans = min(ans, D_sum[0][i]+D_sum[1][j]+D_sum[2][k])
print(ans)
### BUGGY CODE ###

S = list(input())
num_query = int(input())

rev = False
for i in range(num_query):
    query = input().split()
    if len(query) == 1:
        if rev == True:
            rev = False
        else:
            rev = True
    else:
        if rev == False:
            if query[1] == "1":
                S = list(query[2]) + S
            else:
                S.append(query[2])
        else:
            if query[1] == "2":
                S = list(query[2]) + S
            else:
                S.append(query[2])

if rev == True:
    S = S[::-1]
    
print("".join(S))


### FIXED CODE ###

S = input()
num_query = int(input())

rev_flag = False
head = []
tail = []
for i in range(num_query):
    query = input().split()
    if len(query) == 1:
        if rev_flag == True:
            rev_flag = False
        else:
            rev_flag = True
    else:
        if rev_flag == False:
            if query[1] == "1":
                head.append(query[2])
            else:
                tail.append(query[2])
        else:
            if query[1] == "1":
                tail.append(query[2])
            else:
                head.append(query[2])

head = "".join(head)
head = head[::-1]
tail = "".join(tail)
ans = head + S + tail

if rev_flag == True:
    ans = ans[::-1]

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

import sys
input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))
    
    
    ans_start = 0
    tmp = sum(p[:K])
    ms = tmp

    for i in range(K, N):
        tmp = tmp + p[i] - p[i - K]
        if tmp > ms:
            ans_start = i - (K - 1)
            ms = tmp
    
    target = p[ans_start:ans_start + K]
    
    
    ans = 0
    for t in target:
        l = [x for x in range(1, t + 1)]
        ans += sum(l) / t

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))
    
    pi_table = [0] + [(i * (i + 1) // 2) / i for i in range(1,1001)]
    
    pe = [None] * N
    for i in range(N):
        pe[i] = pi_table[p[i]]
    
    tmp = sum(pe[:K])
    ans = tmp
    for i in range(K, N):
        tmp += (pe[i] - pe[i - K])
        ans = max(ans, tmp)
        
    print(ans)



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

from collections import defaultdict
from bisect import bisect
inpl = lambda: list(map(int, input().split()))

N = int(input())
X = inpl()
L = int(input())
Q = int(input())
R = {}

for i in range(N):
    R[(0, i)] = bisect(X, X[i]+L) - 1

for k in range(16):
    for i in range(N):
        R[(k+1, i)] = R[(k, R[(k, i)])]


def reach(a, d):
    O = format(d, "b").zfill(17)[::-1]
    for k in range(16, -1, -1):
        if O[k] == "1":
            a = R[(k, a)]
    return a


def bisearch(a, b):
    a, b = a-1, b-1
    if b < a:
        a, b = b, a
    OK = b-a
    NG = 0

    while abs(OK - NG) > 1:
        mid = (OK+NG)//2
        if reach(a, mid) >= b:
            OK = mid
        else:
            NG = mid
    return OK

print(*[bisearch(*inpl()) for _ in range(Q)], sep="\n")

### FIXED CODE ###

from bisect import bisect
inpl = lambda: list(map(int, input().split()))

N = int(input())
X = inpl()
L = int(input())
Q = int(input())
R = [[0]*(N) for k in range(17)]

for i in range(N):
    R[0][i] = bisect(X, X[i]+L) - 1

for k in range(16):
    for i in range(N):
        R[k+1][i] = R[k][R[k][i]]


def reach(a, d):
    O = format(d, "b").zfill(17)[::-1]
    for k in range(16, -1, -1):
        if O[k] == "1":
            a = R[k][a]
    return a


def bisearch(a, b):
    a, b = a-1, b-1
    if b < a:
        a, b = b, a
    OK = b-a
    NG = 0

    while abs(OK - NG) > 1:
        mid = (OK+NG)//2
        if reach(a, mid) >= b:
            OK = mid
        else:
            NG = mid
    return OK

print(*[bisearch(*inpl()) for _ in range(Q)], sep="\n")
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split(' ')))
for i in range(n-1):
    for j in range(i+1, n):
        if x[i] - x[j] >= 2:
            print('No')
            exit()

print('Yes')

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split(' ')))
now = 0
for i in range(n):
    if now < x[i]:
        now = x[i] - 1
    if now > x[i]:
        print('No')
        exit()

print('Yes')
### BUGGY CODE ###

import sys
N = int(input())
ll=[]
ll = list(map(int, input().split()))

num =0
for i in range(N):
  l2 = ll[:i+1]
  if sorted(l2)[0] == ll[i]:
    num += 1
print(num)


### FIXED CODE ###

import sys

N = int(input())
ll=[]
ll = list(map(int, input().split()))

num =0
mi = ll[0]
for i in range(N):
  a = ll[i]
  if mi >= a:
    mi = a
    num += 1

print(num)
### BUGGY CODE ###

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

route = [1]
for i in range(K):
    next_town = al[route[i]-1]
    if next_town in route:
        loop_start = route.index(next_town)
        loop_end = len(route)
        loop_length = loop_end - loop_start
        if K >= loop_end:
            amari = (K - loop_start)%loop_length
            ans = route[loop_start + amari]
            #print(route)
            print(ans)
            exit()
    else:
        route.append(next_town)

ans = route[-1]
print(ans)


### FIXED CODE ###

from collections import defaultdict


def inpl():
    return list(map(int, input().split()))


N, K = inpl()
aa = inpl()

s = 1

route = [s]
ed = set([s])

for i in range(1, K + 1):
    s = aa[s - 1]
    if s in ed:
        Li = route.index(s)
        Ri = len(route)
        idx = Li + (K - Li) % (Ri - Li)
        print(route[idx])
        break
    else:
        route.append(s)
        ed.add(s)
        continue
else:
    print(s)
### BUGGY CODE ###

n = input()

INFTY = 10000000

color = [0 for i in xrange(n)]
M = [[0 for i in xrange(n)] for i in xrange(n)]
d = [INFTY for i in xrange(n)]
p = [-1 for i in xrange(n)]

def MST():
  d[0] = 0

  while True:
    cost = INFTY
    for i in xrange(n):
      if color[i] != 1 and d[i] < cost:
        cost = d[i]
        u = i

    if cost == INFTY:
      break
    color[u] = 2

    for v in xrange(n):
      if color[v] != 2 and M[u][v] != INFTY:
        if M[u][v] < d[v]:
          d[v] = M[u][v]
          p[v] = u
          color[v] = 1

  sum = 0
  for i in xrange(n):
    if p[i] != -1:
      sum += M[i][p[i]] 
  return sum

for i in xrange(n):
  G = map(int, raw_input().split())
  for j in range(n):
   if G[j] == -1:
     M[i][j] = INFTY
   else:
     M[i][j] = G[j]

print MST()

### FIXED CODE ###

n = input()

INFTY = 10000000

color = [0 for i in xrange(n)]
M = [[INFTY for i in xrange(n)] for i in xrange(n)]
d = [INFTY for i in xrange(n)]
p = [-1 for i in xrange(n)]

def MST():
  d[0] = 0

  while True:
    cost = INFTY
    for i in xrange(n):
      if color[i] != 2 and d[i] < cost:
        cost = d[i]
        u = i

    if cost == INFTY:
      break
    
    color[u] = 2

    for v in xrange(n):
      if color[v] != 2 and M[u][v] != INFTY and M[u][v] < d[v]:
        d[v] = M[u][v]
        p[v] = u
        color[v] = 1

  sum = 0
  for i in xrange(n):
    if p[i] != -1:
      sum += M[i][p[i]]
  return sum

for i in xrange(n):
  G = map(int, raw_input().split())
  for j in range(n):
   if G[j] != -1:
     M[i][j] = G[j]

print MST()
### BUGGY CODE ###

n, m = map(int, input().split())
while m % n != 0:
    n += 1
print(m // n)

### FIXED CODE ###

from math import sqrt

def f(x):
    divisors = [[], []]
    for i in range(1, int(sqrt(x))+1):
        if x % i == 0:
            divisors[0].append(i)
            if i * i != x:
                divisors[1].append(x//i)
    return divisors[0] + divisors[1][::-1]

n, m = map(int, input().split())
for i in f(m):
    if n <= i:
        print(m//i)
        exit()
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
base = ["#" *(w+4)]
base.append("#" * (w+4))
for n in range(h):
    base.append("##" + input() + "##")
base.append("#" * (w+4))
base.append("#" * (w+4))
ans = [[-1] * (w+4) for _ in range(h+4)]
for j in range(w+4):
    for i in range(h+4):
        if base[i][j] == "#":
            ans[i][j] = -2
ch+=1; cw+=1
dh+=1; dw+=1
ans[ch][cw] = 0
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
move2 = [
    [-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], \
    [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2], \
    [0, -2], [0, -1], [0, 0], [0, 1], [0, 2], \
    [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], \
    [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]
    ]
q = deque([[ch, cw]])
one_time = deque([])
while q:
    x, y = q.popleft()
    one_time.append([x, y])
    for i, j in move:
        v1, v2 = x+i, y+j
        if ans[v1][v2] == -1:
            ans[v1][v2] = ans[x][y]
            q.append([v1, v2])
    if len(q) == 0:
        while one_time:
            x2, y2 = one_time.popleft()
            for i, j in move2:
                v1, v2 = x2+i, y2+j
                if ans[v1][v2] == -1:
                    ans[v1][v2] = ans[x2][y2] + 1
                    q.append([v1, v2])
print(ans[dh][dw])

### FIXED CODE ###

from collections import deque
 
 
# In[30]:
 
 
def main():
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    s = ["#"*(W+4)]
    s.append("#"*(W+4))
    for i in range(H):
        s.append("##"+input()+"##")
    s.append("#"*(W+4))
    s.append("#"*(W+4))
    
    ans = [[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ch += 1; cw += 1
    dh += 1; dw += 1
    ans[ch][cw] = 0
    
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    magic = [
        [-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],\
        [-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],\
        [0,-2],[0,-1],[0,0],[0,1],[0,2],\
        [1,-2],[1,-1],[1,0],[1,1],[1,2],\
        [2,-2],[2,-1],[2,0],[2,1],[2,2]
        ]
    
    mylist = deque([[ch,cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x,y = mylist.popleft()
        mylist2.append([x,y])
        for p,q in move:
            v1,v2 = x+p,y+q
            if ans[v1][v2] == -1:
                mylist.append([v1,v2])
                ans[v1][v2] = ans[x][y]
        if len(mylist) == 0:
            while len(mylist2) > 0:
                x2,y2 = mylist2.popleft()
                for v1,v2 in magic:
                    i,j = x2+v1,y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i,j])
    print(ans[dh][dw])
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
INF = float("inf")

# Binary Indexed Tree
class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N+1)
    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x
    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N = int(input())
S = list(input())
Q = int(input())
bit = [BIT(N+1) for i in range(26)]
for i in range(N):
    bit[ord(S[i])-97].add(i+1, 1)
for i in range(Q):
    q, x, y = input().split()
    q = int(q)
    if q == 1:
        i = int(x)-1
        bit[ord(S[i])-97].add(i+1, -1)
        S[i] = y
        bit[ord(y)-97].add(i+1, 1)
    else:
        l, r, ans = int(x), int(y), 0
        for i in range(26):
            ans += (bit[i].sum(r)-bit[i].sum(l-1))> 0
        print(ans)


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
INF = float("inf")

# Binary Indexed Tree
class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N+1)
    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x
    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N = int(input())
S = list(input())
Q = int(input())
bit = [BIT(N+1) for i in range(26)]
for i in range(N):
    bit[ord(S[i])-97].add(i+1, 1)
for i in range(Q):
    q, x, y = input().split()
    q = int(q)
    if q == 1:
        i = int(x)-1
        bit[ord(S[i])-97].add(i+1, -1)
        S[i] = y
        bit[ord(y)-97].add(i+1, 1)
    else:
        l, r, ans = int(x), int(y), 0
        for i in range(26):
            ans += (bit[i].sum(r)-bit[i].sum(l-1))> 0
        print(ans)
### BUGGY CODE ###

from collections import Counter
N = int(input())
Alist = list(map(int,input().split()))
numcntlist = [0] * N 
numCounter = Counter(Alist)

for i in range(1,N+1):
    numcntlist[i-1] = numCounter[i]

ans = 0

for i in Alist:
    numcntlist[i-1] -= 1 
    for j in numcntlist:
        if j == 0 or j == 1:
            None
        else:
            ans += int(j*(j-1)/2)
    
    print(ans)
    numcntlist[i-1] += 1
    ans = 0

### FIXED CODE ###

from collections import Counter
N = int(input())
Alist = list(map(int,input().split()))
numcntlist = [0] * N 
numCounter = Counter(Alist)

for i in range(1,N+1):
    numcntlist[i-1] = numCounter[i]

sumcomb = 0
for i in numcntlist:
    sumcomb += int(i*(i-1)/2)

for i in Alist:
    ans = sumcomb -(numCounter[i] - 1)
    print(ans)
### BUGGY CODE ###


import itertools
import sys
import math
import numpy as np
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def comb(n, r):
    mod = 10**9 + 7
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * pow(i+1, mod-2, mod) % mod
    return res

def main():
    N, a, b = map(int,input().split())

    # print(comb(10**5,5000,10**9+7))
    nCa = comb(N,a)
    nCb = comb(N,b)

    _, ans = divmod(2**N-1 - nCa - nCb,10**9+7)
    print(ans)

if __name__ == "__main__":
  main()


### FIXED CODE ###


import itertools
import sys
import math

sys.setrecursionlimit(10**9)

def comb(n, r):
    mod = 10**9 + 7
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * pow(i+1, mod-2, mod) % mod
    return res

def main():
    N, a, b = map(int,input().split())

    # print(comb(10**5,5000,10**9+7))
    nCa = comb(N,a)
    nCb = comb(N,b)

    _, ans = divmod(2**N-1 - nCa - nCb,10**9+7)
    print(ans)

if __name__ == "__main__":
  main()