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

import sys

sys.setrecursionlimit(2*10**5)

n, q = map(int, input().split())
graph = {i: set() for i in range(n+1)}
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a].add(b)
    graph[b].add(a)
ans = [0] * (n+1)
for _ in range(q):
    p, x = map(int, input().split())
    ans[p] += x

def dfs(now, parent):
    if parent != 0:
        ans[now] += ans[parent]
    for i in graph[now]:
        if i != parent:
            dfs(i, now)

dfs(1, 0)
print(' '.join(map(str, ans[1:])))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n, q = map(int, input().split())
graph = {i: [] for i in range(n)}
for a, b in [[int(i)-1 for i in input().split()] for _ in range(n-1)]:
    graph[a].append(b)
    graph[b].append(a)
ans = [0] * n
for p, x in [[int(i) for i in input().split()] for _ in range(q)]:
    ans[p-1] += x

def dfs(now, parent):
    if parent != -1:
        ans[now] += ans[parent]
    for i in graph[now]:
        if i == parent:
            continue
        dfs(i, now)

dfs(0, -1)
print(' '.join(map(str, ans)))
### BUGGY CODE ###

n=int(input())
c=list(map(int,input().split()))
q=int(input())
s=0
for j in range(q):
	r,s=map(int,input().split())
	d=[]
	for i in range(len(c)):
		if(c[i]==r):
			d.append(i)
	for i in d:
		c[i]=s
	print(sum(c))

### FIXED CODE ###

n=int(input())
c=list(map(int,input().split()))
q=int(input())
su=0
d=[]
for i in range(1000003):
	d.append(0)
for i in range(len(c)):
	d[c[i]]=d[c[i]]+1
	su=su+c[i]
for j in range(q):
	r,s=map(int,input().split())
	su=su-d[r]*r+d[r]*s
	d[s]=d[s]+d[r]
	d[r]=0
	print(su)
### BUGGY CODE ###

import math

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

for x in range(n+1):
  c = math.floor(a*x/b)-a*(math.floor(x/b))
  if c > ans:
    ans = c

print(ans)

### FIXED CODE ###

import math

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

if n >= b:
  c = b-1
else:
  c = n

ans = math.floor(c*a/b)-a*(math.floor(c/b))
print(ans)
### BUGGY CODE ###

S=list(str((input())))
Q=int(input())
for i in range(Q):
    T=list(map(str,input().split()))
    if T[0]=="1":
        S.reverse()
    else:
        if T[1]=="1":
            S.insert(0,T[2])
        else:
            S.append(T[2])

print("".join(S))

### FIXED CODE ###

from collections import deque

S=deque(str((input())))
Q=int(input())
t=0
for _ in range(Q):
    T=list(map(str,input().split()))
    if T[0]=="1":
        t+=1
    else:
        if (T[1]=="1" and t%2 == 0) or (T[1]=="2" and t%2 != 0):
            S.appendleft(T[2])
        else:
            S.append(T[2])


if t%2 != 0:
    S.reverse()

print("".join(S))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
edge = []
edge_inv = [[] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    edge.append((a, b, -c))
    edge_inv[b].append(a)

visited = [False] * n
def dfs(v):
    for u in edge_inv[v]:
        if not visited[u]:
            visited[u] = True
            dfs(u)

visited[n-1] = True
dfs(n-1)
target_nodes = [i for i in range(n) if visited[i]]
# print(target_nodes)

def bellman_ford(n, edge):
    INF = float('inf')
    d = [INF] * n
    d[0] = 0
    for i in range(n):
        update = False
        for v_from, v_to, cost in edge:
            if v_from not in target_nodes or v_to not in target_nodes:
                continue
            if d[v_from] != INF and d[v_to] > d[v_from] + cost:
                d[v_to] = d[v_from] + cost # 緩和
                update = True
    return d, update

d, update = bellman_ford(n, edge)
if update:
    print("inf")
else:
    print(-d[n-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
edge = []
edge_inv = [[] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    edge.append((a, b, -c))
    edge_inv[b].append(a)

visited = [False] * n
def dfs(v):
    for u in edge_inv[v]:
        if not visited[u]:
            visited[u] = True
            dfs(u)

visited[n-1] = True
dfs(n-1)
target_nodes = [i for i in range(n) if visited[i]]
# print(target_nodes)

def bellman_ford(n, edge):
    INF = float('inf')
    d = [INF] * n
    d[0] = 0
    for i in range(n):
        update = False
        for v_from, v_to, cost in edge:
            if v_from not in target_nodes or v_to not in target_nodes:
                continue
            if d[v_from] != INF and d[v_to] > d[v_from] + cost:
                d[v_to] = d[v_from] + cost # 緩和
                update = True
    return d, update

d, update = bellman_ford(n, edge)
if update:
    print("inf")
else:
    print(-d[n-1])
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

for i in range(n):
	b = set(a[:i]+a[i+1:])
	print(max(b))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
m = max(a)

k = [i for i, x in enumerate(a) if x == m]

if len(k)>=2:
	for i in a:
		print(m)
else:
	b = []
	b += a
	mi = b.index(m)
	b.pop(mi) 
	m2 = max(b)
	for i in a:
		if i != m:
			print(m)
		else:
			print(m2)
### BUGGY CODE ###

#python3
def main():
    s = input()
    q = int(input())
    query = []
    for i in range(q):
        t = input()
        query.append(t)
    for i in range(q):
        if query[i][0] == '1':
            #sを反転する
            s = ''.join(reversed(s))
            continue
        if query[i][0] == '2':
            t, f, c = map(str, query[i].split())  
            #あとで消す
            query[i] = (t, f, c)
            #f == 1のとき先頭にcを、f==2のとき最後尾にcを追加する
            if f == '1':
                s = c + s 
            if f == '2':
                s = s + c
    print(s)
main()


### FIXED CODE ###

#python3
def main():
    s = input()
    addfront = ''
    addback = ''
    q = int(input())
    direction = 0
    for i in range(q):
        t = input()
        if t[0] == '1':
            direction += 1
            continue
        if t[0] == '2':
            if direction % 2 == 0:
                if t[2] == '1':
                    addfront = t[4] + addfront 
                if t[2] == '2':
                    addback = addback + t[4]
            else:
                if t[2] == '1':
                    addback = addback + t[4]
                if t[2] == '2':
                    addfront = t[4] + addfront
    ans = addfront + s + addback
    if direction%2 == 0:
        print(ans)
    else:
        ans = ''.join(reversed(ans))
        print(ans)
main()
### BUGGY CODE ###

n = int(input())
aas = list(map(int, input().split()))
if 0 in aas:
    print(0)
    exit()
res = 1
for i in aas:
    res*=i
if res>10**18:
    print(-1)
else:
    print(res)

### FIXED CODE ###

n = int(input())
aas = list(map(int, input().split()))
if 0 in aas:
    print(0)
    exit()
res = 1
for i in aas:
    res*=i
    if res > 10 ** 18:
        print(-1)
        exit()
else:
    print(res)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)
# import time

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


MOD = 998244353

N = d_in()
# start_time = time.time()
total = 3 ** N - (2**N - 2) * 3 - 3

a_list = []
for _ in range(N):
    a_list.append(d_in())
sum_a = sum(a_list)

# 1要素目: i番目の整数までを考慮
# 2要素目: [both>0, 緑>0&青==0, 緑==0&青>0, both==0]
# 3要素目: 最大の色(赤とする)の和
dp = np.zeros((N+1, 4, 1 + (sum_a+1)//2), dtype=int)
dp[0, 3, 0] = 1

for i in range(1, N+1):
    # a = d_in()
    # sum_a += a
    # 赤に入れる
    a = a_list[i-1]
    dp[i, :, a:] += dp[i-1, :, :-a]
    dp[i, :, -1] += dp[i-1, :, -a:].sum(axis=1)

    # 緑に入れる
    dp[i, 0, :] += dp[i-1, 0, :]
    dp[i, 0, :] += dp[i-1, 2, :]
    dp[i, 1, :] += dp[i-1, 1, :]
    dp[i, 1, :] += dp[i-1, 3, :]

    # 青に入れる
    dp[i, 0, :] += dp[i-1, 0, :]
    dp[i, 0, :] += dp[i-1, 1, :]
    dp[i, 2, :] += dp[i-1, 2, :]
    dp[i, 2, :] += dp[i-1, 3, :]

    # # まとめる ---> 数ms...あまり寄与せず
    # dp[:, i, 0] = dp[:, i, 0] + dp[:, i-1, 0]*2 + dp[:, i-1, 2] + dp[:, i-1, 1]
    # dp[:, i, 1] = dp[:, i, 1] + dp[:, i-1, 1] + dp[:, i-1, 3]
    # dp[:, i, 2] = dp[:, i, 2] + dp[:, i-1, 2] + dp[:, i-1, 3]

    if i % 10 == 0:
        dp %= MOD

dp %= MOD
# print((total - dp[-1, 0, (sum_a+1)//2:].sum() * 3) % MOD)
print((total - dp[-1, 0, -1].sum() * 3) % MOD)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)
# import time

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


MOD = 998244353

N = d_in()
total = 3 ** N - (2**N - 2) * 3 - 3

a_list = []
for _ in range(N):
    a_list.append(d_in())
sum_a = sum(a_list)

# 1要素目: i番目の整数までを考慮
# 2要素目: [both>0, 緑>0&青==0, 緑==0&青>0, both==0]
# 3要素目: 最大の色(赤とする)の和
dp = np.zeros((N+1, 3, 1 + (sum_a+1)//2), dtype=int)
dp[0, 2, 0] = 1

for i in range(1, N+1):
    # 赤に入れる
    a = a_list[i-1]
    dp[i, :, a:] += dp[i-1, :, :-a]
    dp[i, :, -1] += dp[i-1, :, -a:].sum(axis=1)

    # 緑or青に入れる
    dp[i, 0, :] += (dp[i-1, 0, :] + dp[i-1, 1, :]) * 2
    dp[i, 1, :] += dp[i-1, 1, :]
    dp[i, 1, :] += dp[i-1, 2, :]

    if i % 10 == 0:
        dp[i, :, :] %= MOD

print((total - dp[-1, 0, -1] * 3) % MOD)
### BUGGY CODE ###

#B問題
import bisect

N = int(input())
S = list(str(input()))
mod = 998244353
N_factorial = 1
for i in range(N):
    N_factorial*=(i+1)
    N_factorial%=mod

r,g,b = [],[],[]
for i in range(3*N):
    if S[i] == "R":
        r.append(i)
    if S[i] == "G":
        g.append(i)
    if S[i] == "B":
        b.append(i)
        
m,M = [],[]
for i in range(N):
    m.append(min(r[i],g[i],b[i]))
    M.append(max(r[i],g[i],b[i]))
    
A,B,C = [],[],[]    
    
for i in range(N):
    A.append(m[i])
    C.append(M[i])
    
for i in range(3*N):
    if i not in A and i not in C:
        B.append(i)
        
count = 1
for i in range(N):
    B_ind = B[i]
    x = bisect.bisect_left(A,B_ind)-i
    y = i+1-bisect.bisect_right(C,B_ind)
    count*=(x*y)%mod
        
ans = (count*N_factorial)%mod
print(ans)

### FIXED CODE ###

#B問題
import bisect

N = int(input())
S = list(str(input()))
mod = 998244353
N_factorial = 1
for i in range(N):
    N_factorial*=(i+1)
    N_factorial%=mod

r,g,b = [],[],[]
for i,s in enumerate(S):
    if s == "R":
        r.append(i)
    if s == "G":
        g.append(i)
    if s == "B":
        b.append(i)
        
A,B,C = [],[],[]
for i in range(N):
    rgb = [r[i],g[i],b[i]]
    rgb.sort()
    A.append(rgb[0])
    B.append(rgb[1])
    C.append(rgb[2])

ans = N_factorial
for i,B_ind in enumerate(B):
    x = bisect.bisect_left(A,B_ind)-i
    y = i+1-bisect.bisect_left(C,B_ind)
    ans*=(x*y)
    ans%=mod

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

X, Y ,Z ,K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

C.sort(reverse=True)

ab_scores = []
for a in A:
    for b in B:
        score = a + b
        ab_scores.append(score)

ab_scores.sort(reverse=True)
ab_scores = ab_scores[:K]

scores = []
for ab in ab_scores:
    for c in C:
        scores.append(ab + c)



scores.sort(reverse=True)

for i in range(K):
    print(scores[i])


### FIXED CODE ###

X, Y ,Z ,K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)


scores = []
for a in range(len(A)):
    for b in range(len(B)):
        if (a + 1) * (b + 1) > K:
            break
        for c in range(len(C)):
            if (a + 1) * (b + 1) * (c + 1) > K:
                break
            score = A[a] + B[b] + C[c]
            scores.append(score)

scores.sort(reverse=True)

for i in range(K):
    print(scores[i])
### BUGGY CODE ###

N = int(input())
H = [int(i) for i in input().split()]

t = 0
if N >= 2:
  for i in range(N-1):
    for j in range(i+1, N):
      if H[i] - H[j] >= 2:
        t += 1

if t == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = int(input())
H = [int(i) for i in input().split()]

t = 0
s = 0
if N >= 2:
  for i in range(N-1):
    if H[i] > H[i+1]:
      t += 1
      if t == 2:
        s += 1
    if H[i] < H[i+1]:
      t = 0
    if H[i] >= H[i+1] +2:
      s += 1
if s == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

N = int(input())
A = map(int, input().split())
B = map(int, input().split())
C = map(int, input().split())

A = list(A)
B = list(B)
B.sort(reverse=True)
C = list(C)
C.sort(reverse=True)

count = 0

for a in A:
    for b in B:
        if a < b:
            for c in C:
                if b < c:
                    count += 1
                else:
                    break
        else:
            break


print(count)


### FIXED CODE ###

import bisect

N = int(input())
A = map(int, input().split())
B = map(int, input().split())
C = map(int, input().split())

A = list(A)
A.sort()
B = list(B)
B.sort()
C = list(C)
C.sort()

count = 0

for b in B:
    l = bisect.bisect_left(A, b)
    r = bisect.bisect_right(C, b)
    count += l * (N - r)

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

import sys
input=sys.stdin.readline
sx,sy,tx,ty=map(int,input().split())
n=int(input())
p=[(sx,sy,0)]
for _ in range(n):
  x,y,r=map(int,input().split())
  p.append((x,y,r))
p.append((tx,ty,0))
n+=2
edge=[[]for _ in range(n)]
for i in range(n-1):
  for j in range(i+1,n):
    sx,sy,sr=p[i]
    tx,ty,tr=p[j]
    t=(abs(sx-tx)**2+abs(sy-ty)**2)**0.5
    c=max(0,t-(sr+tr))
    edge[i].append((j,c))
    edge[j].append((i,c))
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**20
  ans=[inf]*n
  ans[s]=0
  root=[-1]*n
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        root[u]=v
        heappush(h,[c+t,u])
  print(ans[n-1])
dijkstra(0,n,edge)

### FIXED CODE ###

import sys
input=sys.stdin.readline
sx,sy,tx,ty=map(int,input().split())
n=int(input())
p=[(sx,sy,0)]
for _ in range(n):
  x,y,r=map(int,input().split())
  p.append((x,y,r))
p.append((tx,ty,0))
n+=2
edge=[[]for _ in range(n)]
for i in range(n-1):
  for j in range(i+1,n):
    sx,sy,sr=p[i]
    tx,ty,tr=p[j]
    t=(abs(sx-tx)**2+abs(sy-ty)**2)**0.5
    c=max(0,t-(sr+tr))
    edge[i].append((j,c))
    edge[j].append((i,c))
from heapq import heappop,heappush
inf=10**20
ans=[inf]*n
ans[0]=0
root=[-1]*n
h=[(0,0)]
while h:
  c,v=heappop(h)
  if ans[v]<c:continue
  for u,t in edge[v]:
    if c+t<ans[u]:
      ans[u]=c+t
      root[u]=v
      heappush(h,(c+t,u))
print(ans[n-1])
### BUGGY CODE ###

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

sum = 0

for i in range(n):
  for j in range(i+1,n):
    sum += a_list[i] * a_list[j]
    sum = sum%(10**9+7)

print(sum)

### FIXED CODE ###

n = int(input())
a_list = list(map(int,input().split()))
sum_a = sum(a_list)

sum = 0
for i in range(n):
  sum += a_list[i] * (sum_a-a_list[i])
  sum = sum%(10**9+7)
  sum_a -= a_list[i]
print(sum)
### BUGGY CODE ###

import math
from functools import reduce
import itertools
A,B,C,K = map(int,input().split())

count=0
if A>=K:
    ans=K
else:
    count+=A
    if A+B>=K:
        ans=A

    else:
        for i in range(K-(A+B)):
            count-=(K-(A+B))
            ans=count

print(ans)


### FIXED CODE ###

import math
from functools import reduce
import itertools
A,B,C,K = map(int,input().split())

count=0
if A>=K:
    ans=K
else:
    count+=A
    if A+B>=K:
        ans=A

    else:
        count-=(K-(A+B))
        ans=count

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

# 2019/08/16

s=list(input())
t=list(input())

c1={}
c2={}
for ss,tt in zip(s,t):
    c1[ss]=c1.get(ss,'')+tt
    c2[tt]=c2.get(tt,'')+ss
    if len(c1[ss])<2 and len(c2[tt])<2:continue
    if set(c1[ss])=={tt} and set(c2[tt])=={ss}:continue
    else:
        print('No')
        exit()

print('Yes')

### FIXED CODE ###

# 2019/08/16

s=list(input())
t=list(input())

c1={}
c2={}
for ss,tt in zip(s,t):
    if c1.get(ss) is None:
        c1[ss]=tt
    if c2.get(tt) is None:
        c2[tt]=ss
    if c1[ss]==tt and c2[tt]==ss:continue
    else:
        print('No')
        exit()

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

import collections

INF = float('inf')

N, M = list(map(int, input().split()))
d = {i: [] for i in range(N)}

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

queue = collections.deque()
queue.append((0, 0))
results = {i: (INF, -1) for i in range(N)}
results[0] = (0, 0)

while queue:
    cost, cur = queue.pop()
    next_list = d[cur]

    for next_cur in next_list:
        next_cost = cost+1
        if next_cost < results[next_cur][0]:
            results[next_cur] = (next_cost, cur)
            queue.append((next_cost, next_cur))

is_no = False
for k, result in results.items():
    if k == 0:
        continue
    if result[1] == -1:
        is_no = True

if is_no:
    print('No')
else:
    print('Yes')
    for k, result in results.items():
        if k == 0:
            continue
        print(result[1] + 1)


### FIXED CODE ###

import collections

INF = float('inf')

N, M = list(map(int, input().split()))
d = {i: [] for i in range(N)}

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

queue = collections.deque()
queue.append((0, 0))
results = {i: (INF, -1) for i in range(N)}
results[0] = (0, 0)
used = set()

while queue:
    cost, cur = queue.pop()
    if cur in used:
        continue
    used.add(cur)
    next_list = d[cur]

    for next_cur in next_list:
        next_cost = cost+1
        if next_cost < results[next_cur][0]:
            results[next_cur] = (next_cost, cur)
            queue.appendleft((next_cost, next_cur))

is_no = False
for k, result in results.items():
    if k == 0:
        continue
    if result[1] == -1:
        is_no = True

if is_no:
    print('No')
else:
    print('Yes')
    for k, result in results.items():
        if k == 0:
            continue
        print(result[1] + 1)
### BUGGY CODE ###

import itertools
Q = int(input())
l, r = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
lr = zip(l,r)

def Is_prime(n):
    # nが1以下ならFalse
    if n<=1:
        return False
    # nが2または3ならTrue
    if n==2 or n==3:
        return True
    # nが2の倍数ならFalse
    if n%2==0:
        return False
    # nの平方根を整数で取得
    sqrt_root = int(n**.5)
    # nがnの平方根以下の3以上の奇数で1回でも割れたらFalse
    for i in range(3,sqrt_root+1,2):
        if n%i==0:
            return False
    # 上の条件を全てぬけたものはTrue
    return True

def Prime_table(n):
    res = []
    for i in range(n+1):
        if Is_prime(i):
            res.append(i)
    return res

def is_like(x):
    ptb = Prime_table(x)
    if x in ptb and (x+1)//2 in ptb:
        return 1
    return 0

L = list(itertools.accumulate(list(map(is_like,range(max(r)+1)))))

for l,r in lr:
    print(L[r]-L[l-1])

### FIXED CODE ###

MAX = 101010
is_prime = [1]*MAX
is_prime[0] = 0
is_prime[1] = 0
for i in range(2,MAX):
    if not is_prime:
        continue
    for j in range(i*2,MAX,i):
        is_prime[j] = 0

a = [0]*MAX
for i in range(MAX):
    if i%2==0:
        continue
    if is_prime[i] and is_prime[(i+1)//2]:
        a[i] = 1


s = [0]*(MAX+1)
for i in range(MAX):
    s[i+1] = s[i] + a[i]

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(s[r+1]-s[l])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = sum(a) / 2
p = int((n - 1) / 2)

x = []

for i in range(n):
    t = b
    for j in range(p):
        t -= a[(2 * j + i + 1) % n]
    x.append(t * 2)

for i in range(n):
    print(int(x[i]), end=" ")


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = sum(a) / 2
p = int((n - 1) / 2)

x = []

t = b
for j in range(p):
    t -= a[2 * j + 1]
x.append(t * 2)

for i in range(n-1):
    t = a[i] - x[i] / 2
    x.append(t * 2)

for i in range(n):
    print(int(x[i]), end=" ")
### BUGGY CODE ###

import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7

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

ans = pow(2, n, mod) - 1

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, n + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

print(ans - cmb(n, a, mod) - cmb(n, b, mod))

### FIXED CODE ###

import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7

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

ans = pow(2, n, mod) - 1

def fur(n,r):
    p,q = 1,1
    for i in range(r):
        p = p*(n-i)%mod
        q = q*(i+1)%mod
    return p * pow(q,mod-2,mod) % mod

print((ans - fur(n, a) - fur(n, b)) % mod)
### BUGGY CODE ###

from itertools import combinations

N, K = map(int, input().split())
XY = [tuple(map(int, input().split())) for _ in range(N)]

ans = 10**20
for rect in combinations(XY, r=min(K, 4)):
    X = [x for x, _ in rect]
    Y = [y for _, y in rect]

    miX, mxX = min(X), max(X)
    miY, mxY = min(Y), max(Y)

    cnt = len([x for x, y in XY if miY <= y <= mxY and miX <= x <= mxX])
    if cnt >= K:
        ans = min(ans, (mxX - miX) * (mxY - miY))
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
point = []
for _ in range(N) :
    x, y = map(int, input().split())
    point.append((x, y))

ans = float('inf')
for lx, _ in point :
    for rx, _ in point :
        if lx > rx :
            continue
        for _, ly in point :
            for _, ry in point :
                if ly > ry :
                    continue
                count = 0
                for x, y in point :
                    if lx <= x <= rx and ly <= y <= ry :
                        count += 1
                if count >= K :
                    ans = min(ans, (rx - lx) * (ry - ly))

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

s = input()
n = int(input())
li = [input().split() for i in range(n)]
a = 0 #先頭がどっちかという情報

for x in li:
    if x[0] == "1":
        if a == 0:
            a = 1
        else:
            a = 0
    else:
        if (x[1] == "1" and a == 0) or (x[1] == "2" and a == 1):
            s = x[2] + s
        else:
            s = s + x[2]

if a == 0: #先頭が前なら
    print(s)
else: #先頭が後なら
    print(s[::-1])

### FIXED CODE ###

ans = input()
q = int(input())
top = 0
first = str()
last = str()

for i in range(q):
    li =input().split()
    if li[0] =="1":
        top = (top+1)%2
    else:
        if li[1] == "1":
            if top ==0:
                first += li[2]
            else:
                last += li[2]
        else:
            if top ==1:
                first += li[2]
            else:
                last += li[2]

if top == 0:
    ans = first[::-1] + ans + last
else:
    ans = last[::-1] + ans[::-1] + first

print(ans)