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

import sys


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_


def solve(n, q, ccc, queries):
    just_left = {}
    segments = []
    for i in range(n):
        c = ccc[i]
        if c in just_left:
            segments.append((i, 0, just_left[c], 0))
        just_left[c] = i

    for i, (l, r) in enumerate(queries):
        segments.append((r - 1, 1, l - 1, i))

    segments.sort()

    lng = len(segments)

    bit = BinaryIndexedTree(n + 2)
    ans = [0] * q
    for r, tp, l, i in segments:
        if tp == 0:
            bit.add(l + 2, 1)
        else:
            base = r - l + 1
            ans[i] = base - (bit.sum(r + 2) - bit.sum(l + 1))
    return ans


n, q = map(int, sys.stdin.buffer.readline().split())
ccc = list(map(int, sys.stdin.buffer.readline().split()))
mp = map(int, sys.stdin.buffer.read().split())
queries = list(zip(mp, mp))
ans = solve(n, q, ccc, queries)
print('\n'.join(map(str, ans)))


### FIXED CODE ###

import os
import sys

import numpy as np


def solve(inp):
    def bit_add(arr, n, i, x):
        while i <= n:
            arr[i] += x
            i += i & -i

    def bit_sum(arr, i):
        result = 0
        while i > 0:
            result += arr[i]
            i ^= i & -i
        return result

    n = inp[0]
    q = inp[1]
    ccc = inp[2:2 + n]
    lll = inp[2 + n::2] - 1
    rrr = inp[3 + n::2] - 1

    just_left = {}
    segments = []
    for i in range(n):
        c = ccc[i]
        if c in just_left:
            segments.append((i, 0, just_left[c], 0))
        just_left[c] = i

    for i in range(q):
        segments.append((rrr[i], 1, lll[i], i))

    segments.sort()
    bit = np.zeros(n + 2, dtype=np.int64)
    ans = np.zeros(q, dtype=np.int64)

    for r, tp, l, i in segments:
        if tp == 0:
            bit_add(bit, n + 2, l + 2, 1)
        else:
            base = r - l + 1
            ans[i] = base - (bit_sum(bit, r + 2) - bit_sum(bit, l + 1))
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

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

SUM = [0]
ans = 10**20
for a in A:
    SUM.append(SUM[-1]+a)
for i in range(2,N-1): # [1,i]と(i,N]に分割
    low, high = 1, i
    while high - low > 1:
        mid = (low + high)//2
        if SUM[mid] >= SUM[i] - SUM[mid]: high = mid
        else: low = mid
    P1, Q1 = SUM[low], SUM[i]-SUM[low]
    P2, Q2 = SUM[high], SUM[i]-SUM[high]
    if abs(P1-Q1) < abs(P2-Q2): P, Q = P1, Q1
    else: P, Q = P2, Q2
    low, high = i+1, N
    while high - low > 1:
        mid = (low + high)//2
        if SUM[mid]-SUM[i] >= SUM[N]-SUM[mid]: high = mid
        else: low = mid
    R1, S1 = SUM[low]-SUM[i], SUM[N]-SUM[low]
    R2, S2 = SUM[high]-SUM[i], SUM[N]-SUM[high]
    if abs(R1-S1) < abs(R2-S2): R, S = R1, S1
    else: R, S = R2, S2
    ans = min(max(P,Q,R,S) - min(P,Q,R,S), ans)
print(ans)
    


### FIXED CODE ###

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

SUM = [0]
ans = 10**20
for a in A:
    SUM.append(SUM[-1]+a)
for i in range(2,N-1): # [1,i]と(i,N]に分割
    low, high = 1, i
    while high - low > 1:
        mid = (low + high)//2
        if SUM[mid] >= SUM[i] - SUM[mid]: high = mid
        else: low = mid
    P1, Q1 = SUM[low], SUM[i]-SUM[low]
    P2, Q2 = SUM[high], SUM[i]-SUM[high]
    if abs(P1-Q1) < abs(P2-Q2): P, Q = P1, Q1
    else: P, Q = P2, Q2
    low, high = i+1, N
    while high - low > 1:
        mid = (low + high)//2
        if SUM[mid]-SUM[i] >= SUM[N]-SUM[mid]: high = mid
        else: low = mid
    R1, S1 = SUM[low]-SUM[i], SUM[N]-SUM[low]
    R2, S2 = SUM[high]-SUM[i], SUM[N]-SUM[high]
    if abs(R1-S1) < abs(R2-S2): R, S = R1, S1
    else: R, S = R2, S2
    ans = min(max(P,Q,R,S) - min(P,Q,R,S), ans)
print(ans)
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    h, w = list(map(int, readline().split()))
    a = [list(map(int, readline().split())) for _ in range(h)]
    b = [list(map(int, readline().split())) for _ in range(h)]

    diff = [[abs(an - bn) for an, bn in zip(arow, brow)] for arow, brow in zip(a, b)]

    dp = [[set() for _ in range(w)] for _ in range(h)]

    dp[0][0].add(diff[0][0])

    from collections import deque
    que = deque()
    que.append((0, 0))

    while que:
        row, col = que.popleft()
        for num in dp[row][col]:
            if row + 1 < h:
                dp[row + 1][col].add(num + diff[row + 1][col])
                dp[row + 1][col].add(abs(num - diff[row + 1][col]))
                que.append((row + 1, col))
            if col + 1 < w:
                dp[row][col + 1].add(num + diff[row][col + 1])
                dp[row][col + 1].add(abs(num - diff[row][col + 1]))
                que.append((row, col + 1))

    cand = list(dp[h - 1][w - 1])

    print(min(cand))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    h, w = list(map(int, readline().split()))
    a = [list(map(int, readline().split())) for _ in range(h)]
    b = [list(map(int, readline().split())) for _ in range(h)]

    diff = [[abs(an - bn) for an, bn in zip(arow, brow)] for arow, brow in zip(a, b)]

    dp = [[1 << (80 * 160 + 1) for _ in range(w)] for _ in range(h)]
    dp[0][0] |= 1 << diff[0][0]

    from itertools import product

    for row, col in product(range(h), range(w)):
        diff_cur = diff[row][col]
        prevset = 0

        if row - 1 >= 0:
            prevset |= dp[row - 1][col]
        if col - 1 >= 0:
            prevset |= dp[row][col - 1]

        dp[row][col] |= (prevset << diff_cur)
        dp[row][col] |= (prevset >> diff_cur)
        temp = 0
        for i in range(diff_cur):
            if prevset >> i & 1:
                temp += (1 << diff_cur - i)
        dp[row][col] |= temp

    for i in range(12801):
        if dp[h - 1][w - 1] >> i & 1:
            print(i)
            sys.exit()


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

n = int(input())
a = [int(input()) for _ in range(n)]
b = [0] * n
ans = 0
c = 0
b[0] = 1
while True:
    c = a[c] - 1
    ans += 1
    if b[c] == 1:
        ans = -1
        break
    if c == 1:
        break
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
b = [0] * n
ans = 0
c = 0
b[c] = 1
while True:
    c = a[c] - 1
    ans += 1
    if b[c] == 1:
        ans = -1
        break
    if c == 1:
        break
    b[c] = 1
print(ans)
### BUGGY CODE ###

# -*- coding utf-8 -*-

a,b,x=map(int,input().split())
ans=0
for i in range(a,b+1,1):
    if i%x==0:
        ans+=1

print(ans)


### FIXED CODE ###

# -*- coding utf-8 -*-

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

print(b//x - (a-1)//x  )
### BUGGY CODE ###

def find(data, s):
    l = 0
    r = len(data)
    while l < r:
        ind = (l + r) // 2
        if data[ind] == s:
            return True
        elif data[ind] < s:
            l = ind + 1
        else:
            r = ind
    return False


def insert(data, s):
    if len(data) == 0:
        data.append(s)
    else:
        for i in range(len(data)):
            if s <= data[i]:
                data.insert(i, s)
                return data
        data.append(s)
    return data


n = int(input())
data = []
for _ in range(n):
    command = input().split()
    if command[0] == "insert":
        data = insert(data, command[1])
    elif command[0] == "find":
        if find(data, command[1]):
            print("yes")
        else:
            print("no")


### FIXED CODE ###

n = int(input())
data = set()
for _ in range(n):
    command = input().split()
    if command[0] == "insert":
        data.add(command[1])
    elif command[0] == "find":
        if command[1] in data:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
fact = math.factorial
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

N,K = I()
S = list(s())
num = 0
cnt = 0
L = []
for i in range(N):
    if i == N-1:
        L.append(N-num)
    if i < num:
        continue
    s = S[i]
    if s == '0':
        cnt += 1
    for j in range(i,N):
        if S[j] != s:
            L.append(j-num)
            num = j
            break
ruiseki = [0]+list(itertools.accumulate(L))
l = len(ruiseki)
if cnt <= K:
    print(N)
    exit()
start = 0
ans = 0
if S[0] == '0':
    start = 1
for i in range(start,l,2):
    if i+K*2+1 > l-1:
        break
    ans = max(ans,ruiseki[i+K*2+1]-ruiseki[i])
if S[0] == '0':
    ans = max(ans,ruiseki[K*2])
if S[-1] == '0':
    ans = max(ans,ruiseki[-1]-ruiseki[l-K*2-1])
print(ans)

### FIXED CODE ###

import itertools
def s(): return input()
def I(): return map(int,input().split())

N,K = I()
S = list(s())
num = 1
cnt = 0
L = []
for i in range(N-1):
    if S[i] != S[i+1]:
        L.append(num)
        num = 0
        if S[i] == '0':
            cnt += 1
    num += 1
L.append(num)
if S[-1] == '0':
    cnt += 1
ruiseki = [0]+list(itertools.accumulate(L))
l = len(ruiseki)
if cnt <= K:
    print(N)
    exit()
start = 0
ans = 0
if S[0] == '0':
    start = 1
for i in range(start,l,2):
    if i+K*2+1 > l-1:
        break
    ans = max(ans,ruiseki[i+K*2+1]-ruiseki[i])
if S[0] == '0':
    ans = max(ans,ruiseki[K*2])
if S[-1] == '0':
    ans = max(ans,ruiseki[-1]-ruiseki[l-K*2-1])
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import bisect
import numpy as np
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
x = max(max(a),max(b)).bit_length()+1
a = np.array(a)
b = np.array(b)

ans = 0
for i in range(1,x+1):
  c = sorted(np.bitwise_and(a,(1<<i)-1))
  d = sorted(np.bitwise_and(b,(1<<i)-1))
  t = 1<<(i-1)
  anstmp = 0
  for j in range(n):
    t1 = np.searchsorted(d,t-c[j])
    t2 = np.searchsorted(d,2*t-c[j])
    t3 = np.searchsorted(d,3*t-c[j])
    t4 = np.searchsorted(d,4*t-c[j])
    anstmp += (t2-t1)+(t4-t3)
  if anstmp%2:
    ans += t
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
x = max(max(a),max(b)).bit_length()+1
a = np.array(a,dtype=np.int32)
b = np.array(b,dtype=np.int32)
ans = 0
for i in range(1,x+1):
  c = a&(1<<i)-1
  d = b&(1<<i)-1
  d.sort()
  t = 1<<(i-1)
  anstmp = 0
  t1 = np.searchsorted(d,t-c).sum()
  t2 = np.searchsorted(d,2*t-c).sum()
  t3 = np.searchsorted(d,3*t-c).sum()
  anstmp += (t2-t1)+(n-t3)
  if anstmp%2:
    ans += t
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(i) for i in input().split()]

dic = {}
dic[1] = 2
dic[2] = 5
dic[3] = 5
dic[4] = 4
dic[5] = 5
dic[6] = 6
dic[7] = 3
dic[8] = 7
dic[9] = 6

ls = [-1]*8
dp = [-1]*(N+1)
dp[0] = 0
for i in a:
  j = dic[i]
  if ls[j]<i:
    ls[j] = i

tag = []
for i in range(len(ls)):
  if ls[i]!=-1:
    tag += [i]
for i in range(N+1):
  for j in tag:
    if i-j>-1 and dp[i-j]!=-1:
      keta = 0
      while 10**keta<=dp[i-j]:
        keta += 1
      s = ls[j]*(10**keta)+dp[i-j]
      if dp[i]<s:
        dp[i] = s

print(dp[N])


### FIXED CODE ###

n,m=map(int,input().split())
A=list(map(int,input().split()))
L=[0,2,5,5,4,5,6,3,7,6]
dp=[0]+[-1]*n
for i in range(n+1):
  for a in A:
    if i+L[a]<=n:
      dp[i+L[a]]=max(dp[i+L[a]],dp[i]*10+a)
print(dp[n])
### BUGGY CODE ###

l, r = map(int, input().split())
lst = []
for i in range(l,r):
  for j in range(i+1,r+1):
    lst.append(i*j%2019)
print(min(lst))

### FIXED CODE ###

l, r = map(int, input().split())
tmp = 2019*(l//2019)
l -= tmp
r -= tmp
if r >= 2019:
  print(0)
else:
  m = 2020
  for i in range(l, r):
    for j in range(i+1, r+1):
      if m > i*j%2019:
        m = i*j%2019
  print(m)
### BUGGY CODE ###

K, S = map(int, input().split())

count=0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z == S:
                count +=1

print(count)


### FIXED CODE ###

K, S = map(int, input().split())

count=0
for x in range(K+1):
    for y in range(K+1):
        if 0 <= S-(x+y) <= K:
            count +=1

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

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

MOD=10**9+7

primes=[]
is_prime=[True]*(10**6)
for i in range(2,10**6):
    if not is_prime[i]: continue
    primes.append(i)
    for j in range(2*i,10**6,i):
        is_prime[j]=False

F=[[0 for _ in range(len(primes))] for __ in range(N)]
LCM=[0 for _ in range(len(primes))]
for i in range(N):
    n=A[i]
    for j,p in enumerate(primes):
        while n%p==0:
            F[i][j]+=1
            LCM[j]=max(LCM[j],F[i][j])
            n//=p

ans=0
for i in range(N):
    tmp=1
    for j,p in enumerate(primes):
        tmp=tmp*pow(p,LCM[j]-F[i][j],MOD)%MOD
    ans=(ans+tmp)%MOD

print(ans)

### FIXED CODE ###

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

MOD=10**9+7
def gcd(a,b):
    while b: a,b=b,a%b
    return a
def lcm(a,b): return a*b//gcd(a,b)

LCM=A[:]
num=N
while num>1:
    for i in range(1,num,2):
        LCM[i//2]=lcm(LCM[i-1],LCM[i])
    if num&1:
        LCM[num//2]=LCM[num-1]
    num=(num+1)//2

ans=0
l=LCM[0]%MOD
for a in A:
    ans+=l*pow(a,MOD-2,MOD)
    ans%=MOD

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

n,k=map(int,input().split())
dp=[0 for i in range(n)]
num=[False for i in range(n)]
dp[0]=1
mod=998244353
for i in range(k):
    l,r=map(int,input().split())
    for j in range(l,r+1):
        if j<n:
            num[j]=True
for i in range(n):
    for j in range(n-i):
        if num[j]:
            dp[i+j]+=dp[i]
            dp[i+j]%=mod
print(dp[n-1]%mod)

### FIXED CODE ###

n,k=map(int,input().split())
dp=[0 for i in range(n+1)]
acc=[0 for i in range(n+1)]
dp[1]=1
mod=998244353
acc[1]=1
l,r=[],[]
for i in range(k):
    a,b=map(int,input().split())
    l.append(a)
    r.append(b)
for i in range(2,n+1):
    for j in range(k):
        if i-l[j]<0:
            continue
        dp[i]+=(acc[i-l[j]]-acc[max(0,i-r[j]-1)])
        dp[i]%=mod
    acc[i]=(acc[i-1]+dp[i])%mod
print(dp[-1])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N = int(input())
S = input()
c = 0
for i in range(1000):
    if 0 <= i and i <= 9:
        s0 = "0"
        s1 = "0"
        s2 = str(i)
    elif 10 <= i and i <= 99:
        s0 = "0"
        s = str(i)
        s1 = s[0]
        s2 = s[1]
    else:
        s = str(i)
        s0 = s[0]
        s1 = s[1]
        s2 = s[2]
    i0 = -1
    i1 = -1
    i2 = -1
    for k in range(N-2):
        if S[k] == s0:
            i0 = k
            break
    if i0 == -1:
        continue
    for j in range(i0+1,N-1):
        if S[j] == s1:
            i1 = j
            break
    if i1 == -1:
        continue
    for l in range(i1+1,N):
        if S[l] == s2:
            i2 = l
            break
    if i2 != -1:
        c +=1
print(c)


    
    








### FIXED CODE ###

import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N = int(input())
S = input()
c = 0
for i in range(1000):
    if 0 <= i and i <= 9:
        s0 = "0"
        s1 = "0"
        s2 = str(i)
    elif 10 <= i and i <= 99:
        s0 = "0"
        s = str(i)
        s1 = s[0]
        s2 = s[1]
    else:
        s = str(i)
        s0 = s[0]
        s1 = s[1]
        s2 = s[2]
    i0 = -1
    i1 = -1
    i2 = -1
    for k in range(N-2):
        if S[k] == s0:
            i0 = k
            break
    if i0 == -1:
        continue
    for j in range(i0+1,N-1):
        if S[j] == s1:
            i1 = j
            break
    if i1 == -1:
        continue
    for l in range(i1+1,N):
        if S[l] == s2:
            i2 = l
            break
    if i2 != -1:
        c +=1
print(c)
### BUGGY CODE ###

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

result=0

L_p=[j+A[j] for j in range(N)]
L_n=[j-A[j] for j in range(N)]

for j in range(N-1):
    result += L_n[j+1:].count(L_p[j])

print(result)

### FIXED CODE ###

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

result=0

D={}

for j in range(N):
    if j+A[j] in D:
        D[j+A[j]] += 1
    else:
        D[j+A[j]]=1

for j in range(N):
    if j-A[j] in D:
        result += D[j-A[j]]

print(result)
### BUGGY CODE ###

from collections import*
n,*s=open(0)
n=int(n)
s=deque([tuple(t.rstrip())for t in s])
c=0
for _ in range(n):
  if all(x==y for x,y in zip(s,zip(*s))):c+=n
  s.rotate(1)
print(c)

### FIXED CODE ###

n,*s=[t[:-1]for t in open(0)]
n=int(n)
c=0
for _ in range(n):
  c+=all(x==''.join(y)for x,y in zip(s,zip(*s)))*n
  s=s[1:]+s[:1]
print(c)
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
import sys
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    # A, B = [int(a) for a in input().split()]
    # H = [int(a) for a in input().split()]
    A = {
        i: list(reversed([int(a) - 1 for a in input().split()]))
        for i in range(N)
    }

    Q = set(range(N))

    count = 0
    while True:
        pool = []
        for i in Q:
            ai = A[i]
            if len(ai) == 0:
                continue
            target = ai[-1]
            if target < i:
                continue
            target_q = A[target]
            if target_q[-1] == i:
                # print(i,target)
                pool.append(i)
                pool.append(target)

        if len(pool) == 0:
            if len(Q) != 0:
                print(-1)
                return
            else:
                raise ValueError("test")
        for i in pool:
            A[i].pop()
            if len(A[i]) == 0:
                Q.remove(i)

        count += 1
        if len(Q) == 0:
            print(count)
            return


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, deque, Counter
import sys
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    # A, B = [int(a) for a in input().split()]
    # H = [int(a) for a in input().split()]
    A = {
        i: list(reversed([int(a) - 1 for a in input().split()]))
        for i in range(N)
    }

    Q = set(range(N))

    count = 0
    while True:
        pool = []
        for i in Q:
            ai = A[i]
            if len(ai) == 0:
                continue
            target = ai[-1]
            # if target < i:
            #     continue
            target_q = A[target]
            if target_q[-1] == i:
                # print(i,target)
                pool.append(i)
                pool.append(target)

        if len(pool) == 0:
            if len(Q) != 0:
                print(-1)
                return
            else:
                raise ValueError("test")

        qq = []
        for i in set(pool):
            A[i].pop()
            if len(A[i]) != 0:
                qq.append(i)
        Q = set(qq)

        count += 1
        if len(Q) == 0:
            print(count)
            return


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

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

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

mod = 10 ** 9 + 7


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)



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


nca = comb(n, a, mod)#factorial(n) // factorial(a) // factorial(n-a)
ncb = comb(n, b, mod)#factorial(n) // factorial(b) // factorial(n-b)

ans = pow_k(2, n)

ans -= 1 + nca + ncb
ans %= mod
print(ans)

### FIXED CODE ###

mod = 10 ** 9 + 7

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

def combmod(n,k,mod):
    a = 1
    b = 1
    for i in range(k):
        a = a * (n-i) % mod
        b = b * (i+1) % mod
    return a * pow(b, mod-2, mod) % mod

nca = combmod(n, a, mod) #comb(n, a, mod)#factorial(n) // factorial(a) // factorial(n-a)
ncb = combmod(n, b, mod) #comb(n, b, mod)#factorial(n) // factorial(b) // factorial(n-b)

ans = pow(2, n, mod)

ans -= 1 + nca + ncb
ans %= mod
print(ans)
### BUGGY CODE ###

import bisect

_ = input()

heads = list(sorted(map(int,input().split())))
bodies = list(map(int,input().split()))
legs = list(sorted(map(int,input().split())))


cnt = 0
for body in bodies:
    #  頭は、体より小さくなければならない
    head_idx = bisect.bisect_left(heads, body)
    head_cnt = len(heads[:head_idx])

    #  足は、体より大きくなければならない
    leg_idx = bisect.bisect_right(legs, body)
    leg_cnt = len(legs[leg_idx:])

    cnt += head_cnt * leg_cnt # 組み合わせの掛け算

print(cnt)


### FIXED CODE ###

import bisect

N = int(input(), 10)

heads = list(sorted(map(int,input().split())))
bodies = list(map(int,input().split()))
legs = list(sorted(map(int,input().split())))


cnt = 0
for body in bodies:
    #  頭は、体より小さくなければならない
    head_cnt = bisect.bisect_left(heads, body)
    #  足は、体より大きくなければならない
    leg_cnt = N - bisect.bisect_right(legs, body)

    cnt += head_cnt * leg_cnt # 組み合わせの掛け算

print(cnt)
### BUGGY CODE ###

# 同じ町に二回到達したときに、前回たどり着いたときとの差を観る

import sys

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

X = [0] * (N + 1)
X[0] = 1

for i in range(1, K + 1):
    if A[X[i - 1] - 1] in X:
        # 前回の位置を取得
        hoge = X.index(A[X[i - 1] - 1])
        print(X[hoge + ((K - hoge) % ((i-1) - hoge + 1))])
        sys.exit()
    else:
        X[i] = A[X[i - 1] - 1]

print(X[K])


### FIXED CODE ###

# 同じ町に二回到達したときに、前回たどり着いたときとの差を観る

import sys

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

Flag = [0] * (N+1)
X = [0] * (N + 1)
X[0] = 1

for i in range(1, K + 1):
    if Flag[A[X[i - 1] - 1]] == 1:
        # 前回の位置を取得
        hoge = X.index(A[X[i - 1] - 1])
        print(X[hoge + ((K - hoge) % ((i-1) - hoge + 1))])
        sys.exit()
    else:
        X[i] = A[X[i - 1] - 1]
        Flag[A[X[i - 1] - 1]] = 1


print(X[K])