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

f=lambda s,y1,x1,y2,x2:s[y2][x2]-s[y2][x1-1]-s[y1-1][x2]+s[y1-1][x1-1]
H,W,N=map(int,raw_input().split())
a=[map(int,raw_input()) for _ in [0]*H]
s,s1,s2=[ [[0]*(W+1) for _ in [0]*-~H] for _ in [0]*3 ]
for h in range(H):
	for w in range(W):
		s[h+1][w+1]=s[h+1][w]+s[h][w+1]-s[h][w]+a[h][w]
		s1[h+1][w+1]=s1[h+1][w]+s1[h][w+1]-s1[h][w]+(a[h][w]*(w+1<W and a[h][w+1]))
		s2[h+1][w+1]=s2[h+1][w]+s2[h][w+1]-s2[h][w]+(a[h][w]*(h+1<H and a[h+1][w]))
for _ in [0]*N:
	y1,x1,y2,x2=map(int,raw_input().split())
	print f(s,y1,x1,y2,x2)-f(s1,y1,x1,y2,x2-1)-f(s2,y1,x1,y2-1,x2)

### FIXED CODE ###

f=lambda s,y1,x1,y2,x2:s[y2][x2]-s[y2][x1-1]-s[y1-1][x2]+s[y1-1][x1-1]
H,W,N=map(int,raw_input().split())
a=[map(int,raw_input()) for _ in [0]*H]
s,s1,s2=[ [[0]*(W+1) for _ in [0]*-~H] for _ in [0]*3 ]
for h in range(H):
	for w in range(W):
		s[h+1][w+1]=s[h+1][w]+s[h][w+1]-s[h][w]+a[h][w]
		s1[h+1][w+1]=s1[h+1][w]+s1[h][w+1]-s1[h][w]+(a[h][w]*(w+1<W and a[h][w+1]))
		s2[h+1][w+1]=s2[h+1][w]+s2[h][w+1]-s2[h][w]+(a[h][w]*(h+1<H and a[h+1][w]))
for _ in [0]*N:
	y1,x1,y2,x2=map(int,raw_input().split())
	print f(s,y1,x1,y2,x2)-f(s1,y1,x1,y2,x2-1)-f(s2,y1,x1,y2-1,x2)
### BUGGY CODE ###

import sys

N , M = (int(a) for a in input().split())
stair = [1]
brake = []
for i in range(1 , M+1) :
    a = int(input())
    brake.append(a)

for i in range(1, N+1) :
    if i in brake :
        stair.append(0)
    elif i == 1 : 
        stair.append(1) 
    else : stair.append((stair[i-1] + stair[i-2]) % (10**9+7))
         
print(stair[N])





### FIXED CODE ###

N , M = (int(a) for a in input().split())
stair = [1]*(N+1)
for i in range(1 , M+1) :
    a = int(input())
    stair[a] = 0
 
for i in range(2, N+1) :
    stair[i] *= (stair[i-1] + stair[i-2]) % (10**9+7)
         
print(stair[N])
### BUGGY CODE ###

k = int(input())

if k%2==0:
    print('-1')
    exit()

if k%7==0:
    k//=7

mod = 1
i=1
while mod%k!=0:
    mod+=pow(10,i,k)
    i+=1
print(i)


### FIXED CODE ###

k = int(input())

if k%2==0:
    print('-1')
    exit()

if k%7==0:
    k//=7

mod = 1
i=1
mod2 =1
while mod%k!=0 and i<=100000000:
    mod1 = mod2*10%k
    mod+=mod1
    mod%=k
    mod2=mod1
    i+=1
if i>=100000000:
    i=-1
print(i)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10000)
INF = float('inf')

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

counts = [[INF for _ in range(W)] for _ in range(H)]


def ok_range(h, w):
    return 0 <= h < H and 0 <= w < W


for i in range(H + W - 1):
    for j in range(max(0, i - W + 1), min(i + 1, H)):
        h = j
        w = i - j
        if A[h][w] == '#':
            counts[h][w] = 0
        else:
            counts[h][w] = min(
                counts[h][w],
                counts[h - 1][w] + 1 if ok_range(h - 1, w) else INF,
                counts[h][w - 1] + 1 if ok_range(h, w - 1) else INF,
            )
        h2, w2 = H - h - 1, w
        if A[h2][w2] == '#':
            counts[h2][w2] = 0
        else:
            counts[h2][w2] = min(
                counts[h2][w2],
                counts[h2 + 1][w2] + 1 if ok_range(h2 + 1, w2) else INF,
                counts[h2][w2 - 1] + 1 if ok_range(h2, w2 - 1) else INF,
            )
        h3, w3 = h, W - w - 1
        if A[h3][w3] == '#':
            counts[h3][w3] = 0
        else:
            counts[h3][w3] = min(
                counts[h3][w3],
                counts[h3 - 1][w3] + 1 if ok_range(h3 - 1, w3) else INF,
                counts[h3][w3 + 1] + 1 if ok_range(h3, w3 + 1) else INF,
            )
        h4, w4 = H - h - 1, W - w - 1
        if A[h4][w4] == '#':
            counts[h4][w4] = 0
        else:
            counts[h4][w4] = min(
                counts[h4][w4],
                counts[h4 + 1][w4] + 1 if ok_range(h4 + 1, w4) else INF,
                counts[h4][w4 + 1] + 1 if ok_range(h4, w4 + 1) else INF,
            )

ans = 0
for c in counts:
    ans = max(ans, *c)
print(ans)


### FIXED CODE ###

import sys
import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

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

counts = np.zeros((H, W))
counts[A == '.'] = np.inf

for h in range(1, H):
    counts[h, :] = np.minimum(counts[h, :], counts[h - 1, :] + 1)
    counts[-1 - h, :] = np.minimum(counts[-1 - h, :], counts[-h, :] + 1)
for w in range(1, W):
    counts[:, w] = np.minimum(counts[:, w], counts[:, w - 1] + 1)
    counts[:, -1 - w] = np.minimum(counts[:, -1 - w], counts[:, -w] + 1)

print(int(np.max(counts)))
### BUGGY CODE ###

N,K = list(map(int, input().split()))
p = list(map(int, input().split()))
kitai = []

for i in range(N-K+1):
    kitai.append((sum((p[i:i+K]))+K)*0.5)
print('{:.12f}'.format(max(kitai)))


### FIXED CODE ###

N,K = list(map(int, input().split()))
p = list(map(int, input().split()))
p2 = [p[i]*0.5 + 0.5 for i in range(N)]
size = N + 1
cusum = [0] * size
max = 0

for i in range(N):
    cusum[i+1] = cusum[i] + p2[i]

for i in range(N-K+1):
    tmp = cusum[i+K] - cusum[i]
    if max < tmp:
        max = tmp
print(max)
### BUGGY CODE ###

H,W = map(int,input().split())
grid = [list(input()) for _ in range(H)]
L = [[0]*W for _ in range(H)]
R = [[0]*W for _ in range(H)]
U = [[0]*W for _ in range(H)]
D = [[0]*W for _ in range(H)]

for w in range(W):
    for h in range(H):
        if grid[h][w] == '#':
            L[h][w] = 0
        elif w == 0:
            L[h][w] = 1
        else:
            L[h][w] = L[h][w-1] + 1

for w in range(W):
    for h in range(H):
        if grid[h][w] == '#':
            U[h][w] = 0
        elif h == 0:
            U[h][w] = 1
        else:
            U[h][w] = U[h-1][w] + 1

for w in range(W-1,-1,-1):
    for h in range(H):
        if grid[h][w] == '#':
            R[h][w] = 0
        elif w == W-1:
            R[h][w] = 1
        else:
            R[h][w] = R[h][w+1] + 1

for w in range(W):
    for h in range(H-1,-1,-1):
        if grid[h][w] == '#':
            D[h][w] = 0
        elif h == H-1:
            D[h][w] = 1
        else:
            D[h][w] = D[h+1][w] + 1
ans = 0
for w in range(W):
    for h in range(H):
        lighted = D[h][w] + U[h][w] + L[h][w] + R[h][w] - 3
        ans = max(ans,lighted)
print(ans)

### FIXED CODE ###

import numpy as np
h, w = map(int, input().split())
table = np.array([list(input())for _ in range(h)]) == '.'
 
d = np.zeros((h, w), dtype = int)
u = np.zeros((h, w), dtype = int)
r = np.zeros((h, w), dtype = int)
l = np.zeros((h, w), dtype = int)

for i in range(h):
    d[i] = (d[i-1]+1) * table[i]
    u[-i-1] = (u[-i]+1) * table[-i-1]

for i in range(w):
    r[:, i] = (r[:, i-1]+1) * table[:, i]
    l[:, -i-1] = (l[:, -i]+1) * table[:, -i-1]
print(np.max(d+u+r+l)-3)
### BUGGY CODE ###

#三井住友2019 D 貪欲法
def main():
    import sys
    N = int(sys.stdin.readline())
    S = sys.stdin.readline().rstrip()
    ans = 0
    for i in range(1000):
        num = str(i).zfill(3)
        L = []
        k = 0
        for j in range(N):
            #print(num, S[j])
            if int(S[j])==int(num[k]):
                #print('Yes', num)
                L.append(S[j])
                k+=1
            if len(L)==3:
                #print(L)
                ans +=1
                break
                
    print(ans)
        
    
if __name__=='__main__':
    main()


### FIXED CODE ###

#三井住友2019 D 貪欲法
def main():
    import sys
    N = int(sys.stdin.readline())
    S = sys.stdin.readline().rstrip()
    ans = 0
    for i in range(1000):
        num = str(i).zfill(3)
        L = []
        k = 0
        for j in range(N):
            #print(num, S[j])
            if int(S[j])==int(num[k]):
                #print('Yes', num)
                L.append(S[j])
                k+=1
            if len(L)==3:
                #print(L)
                ans +=1
                break
                
    print(ans)
        
    
if __name__=='__main__':
    main()
### BUGGY CODE ###

n = int(input())
a = []
for _ in range(0, n):
    a.append(int(input()))
for i in range(0, n):
    if not a[i] == max(a):
        print(max(a))
    else:
        b = a.pop(i)
        print(max(a))
        a.insert(i, b)
        

### FIXED CODE ###

n = int(input())
a = []
for _ in range(0, n):
    a.append(int(input()))
first = max(a)
second_1 = sorted(a)
second = second_1[-2]
for i in range(0, n):
    if a[i] == first:
        print(second)
    else:
        print(first)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
a = [list(map(int, input().split())) for _ in range(q)]

b = []
for i in range(n-1):
	if s[i:i+2] == "AC":
		b.append((i,i+1))
for i in a:
	cnt = 0
	for j in b:
		if (i[0]-1) <= j[0] and j[1] <= (i[1]-1):
			cnt += 1
	print (cnt)


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
a = [list(map(int, input().split())) for _ in range(q)]

b = [0] * n
cnt = 0
for i in range(n-1):
	if s[i:i+2] == "AC":
		b[i+1] = b[i] + 1
	else:
		b[i+1] = b[i]
for i in a:
	print (b[i[1]-1] - b[i[0]-1])
### BUGGY CODE ###

import queue
x=int(input())
avail=list(range(100,106))+[0]*x
q=queue.Queue()
for i in avail:
    q.put(i)
while not q.empty():
    f=q.get()
    for i in range(100,106):
        if(i+f<=x and i+f not in avail):
            avail.append(i+f)
            q.put(i+f)
print(1 if x in avail else 0)

### FIXED CODE ###

import queue
x=int(input())
avail=list(range(100,106))
ok=[False]*max(x+1,106)
q=queue.Queue()
for i in avail:
    ok[i]=True
    q.put(i)
while not q.empty():
    f=q.get()
    for i in range(100,106):
        if(i+f<=x and not ok[i+f]):
            ok[i+f]=True
            q.put(i+f)
print(1 if ok[x] else 0)
### BUGGY CODE ###

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

class UnionFind():
    def __init__( self, n ):
        self.n = n
        self.parents = [ - 1 ] * n
        
    def find( self, x ):
        if self.parents[ x ] < 0:
            return x
        else:
            self.parents[ x ] = self.find( self.parents[ x ] )
            return self.parents[ x ]

    def union( self, x, y ):
        x = self.find( x )
        y = self.find( y )
        if x == y:
            return
        if self.parents[ x ] > self.parents[ y ]:
            x, y = y, x
        self.parents[ x ] += self.parents[ y ]
        self.parents[ y ] = x
        
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

uf = UnionFind( N + 1 )
friends = [ [] for _ in range( N + 1 ) ]
for i in range( M ):
  a, b = map( int, input().split() )
  uf.union( a, b )
  friends[ a ].append( b )
  friends[ b ].append( a )

block = [ [] for _ in range( N + 1 ) ]
for i in range( K ):
  c, d = map( int, input().split() )
  block[ c ].append( d )
  block[ d ].append( c )

ans = str( len( set( uf.members( 1 )) - set( block[ 1 ] + friends[ 1 ]))  - 1 )
for i in range( 2, N + 1 ):
  ans += " " + str( len( set( uf.members( i )) - set( block[ i ] + friends[ i ]))  - 1 )
print( ans )

### FIXED CODE ###

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

class UnionFind():
    def __init__( self, n ):
        self.n = n
        self.parents = [ - 1 ] * n
        
    def find( self, x ):
        if self.parents[ x ] < 0:
            return x
        else:
            self.parents[ x ] = self.find( self.parents[ x ] )
            return self.parents[ x ]

    def union( self, x, y ):
        x = self.find( x )
        y = self.find( y )
        if x == y:
            return
        if self.parents[ x ] > self.parents[ y ]:
            x, y = y, x
        self.parents[ x ] += self.parents[ y ]
        self.parents[ y ] = x
        
    def size( self, x ):
      return -self.parents[ self.find( x ) ]
        
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def same( self, x, y ):
      return self.find( x ) == self.find( y )

uf = UnionFind( N + 1 )
not_use = [ 0 ] * ( N + 1 )
for i in range( M ):
  a, b = map( int, input().split() )
  uf.union( a, b )
  not_use[ a ] += 1
  not_use[ b ] += 1

block = [ [] for _ in range( N + 1 ) ]
for i in range( K ):
  c, d = map( int, input().split() )
  if uf.same( c, d ):
    not_use[ c ] += 1
    not_use[ d ] += 1

ans = str( uf.size( 1 ) - not_use[ 1 ] - 1 )
for i in range( 2, N + 1 ):
  ans += " " + str( uf.size( i ) - not_use[ i ] - 1 )
print( ans )
### BUGGY CODE ###

n = int(input())
al = [int(i) for i in input().split()]

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors[:-1]
  
import collections

if n == 1:
  print(1)
else:
  total = 0
  ss = set(al)
  c = collections.Counter(al)
  for num in al:
    if c[num] >= 2:
      continue
    for d in make_divisors(num):
      if d in ss:
        break
    else:
      total += 1
  print(total)



### FIXED CODE ###

n = int(input())
al = [int(i) for i in input().split()]  
al.sort()
ma = al[-1]
from collections import Counter
c = Counter(al)

if n == 1:
  print(1)
else:
  sn = set()
  total = 0
  l = len(al)
  for num in al:
    if num in sn:
      continue
    if c[num] == 1:
      total += 1
    tmp = num
    while tmp <= ma:
      sn.add(tmp)
      tmp += num
  print(total)
### BUGGY CODE ###

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

count = 0
I = [0]*N
J = [0]*N

for i in range(N):
  I[i] = i+A[i]
  J[i] = i-A[i]
for j in range(N):
  count += J.count(I[j])

print(count)

### FIXED CODE ###

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

ans = 0
B = [0]*N
C = [0]*N

for i in range(N):
  b = i+A[i]
  c = i-A[i]
  if 0 < b < N:
    B[b] += 1
  if 0 < c < N:
    C[c] += 1

for i in range(N):
  ans += B[i]*C[i]

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

import math
denom = int(1e9+7)

def combi(n,r):
    return (int(math.factorial(n)) // int(math.factorial(r)) // int(math.factorial(n - r))) % denom



def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p


def combi2(n,k,p,f):
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=fact_mod[n]
  b=fact_mod[k]
  c=fact_mod[n-k]
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p



N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort(reverse = True)

fact_mod = [1]
current = 1
for i in range(1,N+1):
    current = (current * i) % denom
    fact_mod.append(current)

max_tot = 0
for i in range(N-K+1):
    max_tot += (A[i] * combi2(N-i-1, K-1, denom, fact_mod)) % denom
min_tot = 0
for i in range(N-K+1):
    min_tot += (A[N-i-1] * combi2(N-i-1, K-1, denom, fact_mod)) % denom
    
print((max_tot - min_tot)%denom)

### FIXED CODE ###

import math
denom = int(1e9+7)

def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p


def combi2(n,k,p,f,pow_fun):
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=fact_mod[n]
  b=fact_mod[k]
  c=fact_mod[n-k]
  return (a*pow_fun[b]*pow_fun[c])%p


N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort(reverse = True)

fact_mod = [1]
current = 1
for i in range(1,N+1):
    current = (current * i) % denom
    fact_mod.append(current)

pow_fun = {}
for i in fact_mod:
    pow_fun[i]=power_func(i,denom-2,denom)

max_tot = 0
min_tot = 0
for i in range(N-K+1):
    max_tot += (A[i] * combi2(N-i-1, K-1, denom, fact_mod,pow_fun)) % denom
    min_tot += (A[N-i-1] * combi2(N-i-1, K-1, denom, fact_mod,pow_fun)) % denom
    
print((max_tot - min_tot)%denom)
### BUGGY CODE ###

import sys
n=int(input())
print(0)
l=input()
L=0
if l=='Vacant':
  sys.exit()
print(n-1)
r=input()
R=n-1
if r=='Vacant':
  sys.exit()

while True:
  print((L+R)//2)
  x=input()
  X=(L+R)//2
  if x=='Vacant':
    sys.exit()
  if (X-L)%2==1 and x==l or (X-L)%2==0 and x=!l:
    r=x;R=X
  else:
    l=x;L=X

### FIXED CODE ###

import sys
n=int(input())
print(0)
l=input()
L=0
if l=='Vacant':
  sys.exit()
print(n-1)
r=input()
R=n-1
if r=='Vacant':
  sys.exit()

while True:
  print((L+R)//2)
  x=input()
  X=(L+R)//2
  if x=='Vacant':
    sys.exit()
  if ((X-L)%2==1 and x==l) or ((X-L)%2==0 and x!=l):
    r=x;R=X
  else:
    l=x;L=X
### BUGGY CODE ###

n = int(input())
s = list(input())
m = 3 * 10 ** 5

for i in range(n):
    w = s[:i]
    e = s[i + 1:]
    count = w.count('W') + e.count('E')
    m = min(m, count)

print(m)

### FIXED CODE ###

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

reS = S[::-1]

wSum = [0 for i in range(N)]
eSum = [0 for i in range(N)]

for i in range(N):
    if i == 0:
        if S[i] == 'W':
            wSum[i] = 1
        if reS[i] == 'E':
            eSum[i] = 1
    else:
        if S[i] == 'W':
            wSum[i] = wSum[i-1] + 1
        else:
            wSum[i] = wSum[i-1]
        if reS[i] == 'E':
            eSum[i] = eSum[i-1] + 1
        else:
            eSum[i] = eSum[i-1]

eSum = eSum[::-1]

cost = eSum[1]

for i in range(1,N):
    if i == N - 1:
        if cost > wSum[N-2]:
            cost = wSum[N-2]
    else:
        if cost > wSum[i-1] + eSum[i+1]:
            cost = wSum[i-1] + eSum[i+1]
print(cost)
### BUGGY CODE ###

# coding:UTF-8
import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = 10000000000


def main():
    # ------ 入力 ------#
    N, Q = list(map(int, input().split()))     # スペース区切り連続数字

    queList = [list(map(int, input().split())) for _ in range(Q)]     # スペース区切り連続数字(行列)

    # ------ 処理 ------#
    black = (N-2)**2
    chList = [[N-2] * N for _ in range(2)]

    for que in queList:
        x = que[1]
        y = que[0]-1
        ch = chList[y][x]
        black -= ch
        for i in range(2, min(ch+2, N)):
            chList[1-y][i] = min(max(x-2, 0), chList[1-y][i])

    # ------ 出力 ------#
    print("{}".format(black))

if __name__ == '__main__':
    main()


### FIXED CODE ###

# coding:UTF-8
import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = 10000000000

# 二分探査
def binary_search(list, item):
    # 1:以上 2:以下　
    mode = 2
    low = 0
    high = len(list) - 1
    upper = len(list) - 1
    lower = 0
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
            upper = mid
        else:
            low = mid + 1
            lower = mid
    if mode == 1:
        return upper
    elif mode == 2:
        return lower

def main():
    # ------ 入力 ------#
    N, Q = list(map(int, input().split()))     # スペース区切り連続数字

    queList = [list(map(int, input().split())) for _ in range(Q)]     # スペース区切り連続数字(行列)

    # ------ 処理 ------#
    black = (N-2)**2
    m = [N, N]
    chList = [[-1] * N for _ in range(2)]
    for que in queList:
        x = que[1]
        y = que[0]-1
        ch = chList[y][x]
        if ch == -1:
            ch = m[1-y] - 2
            m[y] = x
            i = 0
            while x+i <= N-1 and chList[y][x+i] == -1:
                chList[y][x+i] = m[1-y] - 2
                i = i + 1
        black -= ch

    # ------ 処理 ------#
    # black = (N-2)**2
    # div = [{2: N-2}, {2: N-2}]
    # for que in queList:
    #     x = que[1]
    #     y = que[0]-1
    #     kl = list(div[y].keys())
    #     d = binary_search(kl, x)
    #     ch = div[y][kl[d]]
    #     black -= ch
    #     if d == 0:
    #         div[y][x] = div[y][kl[d]]
    #         div[y] = dict(sorted(div[y].items(), key=lambda x:x[0]))
    #         div[1-y][list(div[1-y].keys())[d]] = max(x-2, 0)

    # ------ 出力 ------#
    print("{}".format(black))

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

n = int(input())
a = [0 for n in range(n)]
for i in range(n):
  a[i] = int(input())
a_max = max(a)
for j in range(n):
  if a[j] != a_max:
    print(a_max)
  else:
    a.sort()
    a.reverse()
    print(a[1])

### FIXED CODE ###

n = int(input())
a = [0 for n in range(n)]
for i in range(n):
  a[i] = int(input())
a_max = max(a)
b = sorted(a)
a_second = b[n-2]
for j in range(n):
  if a[j] != a_max:
    print(a_max)
  else:
    print(a_second)
### BUGGY CODE ###

s = list(input())
q = int(input())

#一番最後に1度だけ反転すればよい
reverse_count = 0
for i in range(q):
  y = input().split()
  if y[0] == '1':
    #反転は最後に行う
    reverse_count += 1
    continue
  elif y[0] == '2':
    if y[1] == '1':
      #文字列の先頭に追加。反転回数が奇数なら、末尾に追加と同義
      if reverse_count % 2 == 1:
        s = s + [y[2]]
      else:
        s = [y[2]] + s
    elif y[1] == '2':
      #文字列の末尾に追加。反転回数が奇数なら、先頭に追加と同義
      if reverse_count % 2 == 1:
        s = [y[2]] + s
      else:
        s = s + [y[2]]

#最後に一度だけ反転させる
if reverse_count % 2 == 0:
  #元の順序に戻るので、そのまま
  print("".join(s))
else:
  s.reverse()
  print("".join(s))



### FIXED CODE ###

from collections import deque
#双方向リストにするため、dequeを使用する
#（先頭と末尾に文字を追加するため）
s = deque(input())
q = int(input())

#一番最後に1度だけ反転すればよい
reverse_count = 0
for i in range(q):
  y = input().split()
  if y[0] == '1':
    #反転は最後に行う
    reverse_count += 1
    continue
  elif y[0] == '2':
    if y[1] == '1':
      #文字列の先頭に追加。反転回数が奇数なら、末尾に追加と同義
      if reverse_count % 2 == 1:
        s.append(y[2])
      else:
        s.appendleft(y[2])
    elif y[1] == '2':
      #文字列の末尾に追加。反転回数が奇数なら、先頭に追加と同義
      if reverse_count % 2 == 1:
        s.appendleft(y[2])
      else:
        s.append(y[2])

#最後に一度だけ反転させる
if reverse_count % 2 == 0:
  #元の順序に戻るので、そのまま
  print("".join(s))
else:
  s.reverse()
  print("".join(s))
### BUGGY CODE ###

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

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 3*(10**5)
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

D=[1,2,4]
d=[0,1,2]
for i in range(3,31):
    d.append(d[-1]*2)
    D.append((D[-1]**2)%mod)
D=D[::-1]
d=d[::-1]
#print(len(D),D)
#print(len(d),d)
Num=NN
ALL=1
for i in range(31):
    if Num>=d[i]:
        Num-=d[i]
        ALL*=D[i]
        ALL%=mod
if Num==1:
    Num-=1
    ALL*=2
    ALL%=mod
#print(ALL,Num)

A=1
for i in range(1,a+1):
    A*=(NN-i+1)
    A//=i
A%=mod
B=1
for i in range(1,b+1):
    B*=(NN-i+1)
    B//=i
B%=mod
#print(A,B)

if NN<a or NN<b:
    print(0)
else:
    if ALL-A-B-1<0:
        print((ALL-A-B-1+mod*2)%mod)
    else:
        print(ALL-A-B-1)

### FIXED CODE ###

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

MOD=10**9+7
def comb(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%MOD
    for i in range(2,k+1):
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        ans=ans*(n-k+i)*inv[i]%MOD
    return ans

print((pow(2,N,MOD) - comb(N , A) - comb(N , B) - 1 ) % MOD )