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

def solve(N, K, heights):
  dp = [float('inf')] * N
  dp[0] = 0
  for i in range(N - 1):
    for k in range(1, K + 1):
      if i + k < N:
        dp[i + k] = min(dp[i + k], dp[i] + abs(heights[i] - heights[i + k]))
  print(dp[N - 1])

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

N, K = iln()
solve(N, K, iln())


### FIXED CODE ###

def solve(N, K, heights):
  dp = [0] * N
  for i in range(1, N):
    min_cost = float('inf')
    for k in range(max(0, i - K), i):
      # min_cost = min(min_cost, dp[k] + abs(heights[i] - heights[k]))
      temp = dp[k] + abs(heights[i] - heights[k])
      if temp < min_cost:
        min_cost = temp
    dp[i] = min_cost
  print(dp[N - 1])


 
def iin(): return int(input())
def iln(): return list(map(int, input().split()))
 
N, K = iln()
solve(N, K, iln())
### BUGGY CODE ###

def main():
  import collections
  x = int(input())
  num_list = list(map(int, input().split()))
  for i in range(x):
    set_list = num_list[:i] + num_list[i+1:]
    count = collections.Counter(set_list)
    score = 0
    for j in count.values():
      score += j * (j-1) / 2
    print(int(score))
main()

### FIXED CODE ###

def main():
  import collections
  x = int(input())
  num_list = list(map(int, input().split()))
  count = collections.Counter(num_list)
  score = 0
  for j in count.values():
    score += j * (j-1) / 2
  for k in num_list:
    k_num = count[k]
    print(int(score - k_num + 1))
main()
### BUGGY CODE ###

import math
K, N  = map(int,input().split())
List = list(map(int,input().split()))
d = []
for i in range(N):
  for j in range(N):
    x = min(abs(List[i]-List[j]), K-abs(List[i]-List[j]))
    d.append(x)
result = K - int(max(d))
print(result)

### FIXED CODE ###

K, N  = map(int,input().split())
List = list(map(int,input().split()))
d = []
for i in range(1,N):
  x = min(abs(List[i]-List[i-1]), K-abs(List[i]-List[i-1]))
  d.append(x)
d.append(min(abs(List[N-1]-List[0]), K-abs(List[N-1]-List[0])))
result = K - int(max(d))
print(result)
### BUGGY CODE ###

import sys

MAX = 999999
L = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

def is_prime(n):
  if n == 2:return True
  if n % 2 == 0:return False
  for i in range(3,int(n**0.5)+1,2):
    if n % i == 0:return False
  return True

def is_prime_2(n):
  a = int(n ** 0.5)
  for i in L:
    if i > a:return True
    if n % i == 0:return False
  return True

def prime_count(n):
  result = 0
  if n >= 2:result+=1
  for i in range(3,n+1,2):
    if is_prime_2(i):result+=1
  return result

def prime_list(n):
  result = []
  if n >= 2:result.append(2)
  for i in range(3,n+1,2):
    if is_prime(i):result.append(i)
  return result

L2 = prime_list(MAX)

def prime_count_2(n):
  for i,v in enumerate(n):
    if n > v:return i
  return len(L2)

for n in sys.stdin:
  print(prime_count(int(n)))

### FIXED CODE ###

import sys
import time

MAX = 999999

def is_prime(n):
  if n == 2:return True
  if n % 2 == 0:return False
  for i in range(3,int(n**0.5)+1,2):
    if n % i == 0:return False
  return True

def prime_list(n):
  return ([2] if n > 1 else []) + [i for i in range(3,n+1,2) if is_prime(i)]

L = prime_list(int(MAX**0.5))

def is_prime_2(n):
  a = int(n ** 0.5)
  for i in L:
    if i > a:return True
    if n % i == 0:return False
  return True

def prime_count(n):
  result = 0
  if n >= 2:result+=1
  for i in range(3,n+1,2):
    if is_prime_2(i):result+=1
  return result

def prime_list2(n):
  return ([2] if n > 1 else []) + [i for i in range(3,n+1,2) if is_prime_2(i)]

L2 = prime_list2(MAX)

def prime_count_2(n):
  for i,v in enumerate(L2):
    if v > n:return i
  return len(L2)

for n in sys.stdin:
  print(prime_count_2(int(n)))
### BUGGY CODE ###

def c(S):
    cnt = 0
    for i in range(len(bin(S))-2):
        cnt += S>>i&1
    return cnt
mod = 10**9+7
N = int(input())
li = [list(map(int, input().split())) for i in range(N)]
dp = [0]*(1<<N)
dp[0] = 1
for S in range(1, 1<<N):
    num = c(S)
    for i in range(N):
        if S>>i&li[num-1][i] == 1:
            dp[S] = (dp[S]+dp[S-(1<<i)]) %mod
print(dp[(1<<N)-1])

### FIXED CODE ###

mod = 10**9+7
N = int(input())
li = [list(map(int, input().split())) for i in range(N)]
lc = [0] * (1<<N)
dp = [0]*(1<<N)
dp[0] = 1
for S in range(1, 1<<N):
    lc[S] = lc[S>>1]+S%2
    for i in range(N):
        if S>>i&li[lc[S]-1][i] == 1:
            dp[S] = (dp[S]+dp[S-(1<<i)]) %mod
print(dp[(1<<N)-1])
### BUGGY CODE ###

a = input()
q = int(input())
query = [list(input().split()) for i in range(q)]
now = 0
for i in query:
  if i[0] == "1":
    now ^= 1
  elif i[0] == "2":
    f,c = int(i[1]),i[2]
    if (f+now) % 2:
      a = c + a
    else:
      a = a + c
if now:
  a = a[::-1]
print(a)

### FIXED CODE ###

from collections import deque

s = list(input())
q = int(input())
query = [list(input().split()) for i in range(q)]
now = 0
a = deque(s)
for i in query:
  if i[0] == "1":
    now ^= 1
  elif i[0] == "2":
    f,c = int(i[1]),i[2]
    if (f+now) % 2:
      a.appendleft(c)
    else:
      a.append(c)
if now:
  a.reverse()
ans = "".join(a)
print(ans)
### BUGGY CODE ###

q=int(input())
a=[]
b = 0

def query2(a,b,x):
    ret = b
    for sa in a:
        ret += abs(x-sa)
    return ret


for _ in range(q):
    x=list(map(int,input().split()))
    if x[0] ==1:
        a.append(x[1])
        b += x[2]
    elif x[0] == 2:
        a.sort()
        r1 = a[(len(a)-1)//2]
        r2 = query2(a,b,r1)
        print(str(r1)+" "+str(r2))

### FIXED CODE ###

import heapq
import sys 
input = sys.stdin.readline

def main():
    q=int(input())
    res = 0

    x=list(map(int,input().split()))
    a=x[1]
    res += x[2]
    asmall = [a*-1]
    alarge = [a]
    heapq.heapify(asmall)
    heapq.heapify(alarge)

    r1 = a
    r2 = a

    for _ in range(q-1):
        x=list(map(int,input().split()))
        if x[0] ==1:
            a = x[1]
            res += x[2]
            if r1 <= a and a <= r2: pass
            else: res += min(abs(a-r1),abs(a-r2))
            mid1 = asmall[0] * -1
            if mid1 > a:
                heapq.heappush(alarge,heapq.heappop(asmall) * -1)
                heapq.heappush(asmall,-a)
                heapq.heappush(asmall,-a)
            else:
                mid2 = alarge[0]
                if mid2 >= a:
                    heapq.heappush(asmall,-a)
                    heapq.heappush(alarge,a)
                else:
                    heapq.heappush(asmall,heapq.heappop(alarge) * -1)
                    heapq.heappush(alarge,a)
                    heapq.heappush(alarge,a)
            r1 = asmall[0] * -1
            r2 = alarge[0]
        if x[0] == 2:
            print(str(r1)+" "+str(res))

main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in A:
    ans *= i
if ans > 10 ** 18:
    print('-1')
else:
    print(ans) 


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
ans = 1
for i in A:
    ans *= i
    if ans > 10 ** 18:
        print('-1')
        exit()
print(ans)
### BUGGY CODE ###

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(N - 1 + M)]

from collections import defaultdict
from heapq import *

vs = defaultdict(set)
ws = defaultdict(set)

for a, b in AB:
    vs[a].add(b)
    ws[b].add(a)

h = []
heappush(h, (0, 1))
while h:
    l, n = heappop(h)
    if ws[n]:
        for m in ws[n]:
            heappush(h, (l + 1, m))
    else:
        root = n

h = []

heappush(h, (0, root, 0))

rs = [-1] * (N + 1) 

while h:
    l, n, parent = heappop(h)
    rs[n] = parent
    for m in vs[n]:
        heappush(h, (l + 1, m, n))

for i in range(1, N + 1):
    print(rs[i])


### FIXED CODE ###

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(N - 1 + M)]

import sys
sys.setrecursionlimit(200000)

from collections import defaultdict

vs = defaultdict(set)
ws = defaultdict(set)

for a, b in AB:
    vs[a].add(b)
    ws[b].add(a)

#print(vs)
#print(ws)

L = []

cs = [0] * (1 + N)

def visit(n):
    if cs[n] == 1:
        return
    elif cs[n] == 0:
        cs[n] = 1
        for m in vs[n]:
            visit(m)
        cs[n] = 2
        L.append(n)

for n in range(1, N + 1):
    if cs[n] == 0:
        visit(n)

#print(L)

nrank = {}

for r, n in enumerate(L):
    nrank[n] = r

#print(nrank)

for n in range(1, N + 1):
    r = 0
    if ws[n]:
        r = sorted(ws[n], key=lambda x:nrank[x])[0]
    print(r)
### BUGGY CODE ###

# PROBLEM B
a, b, k = [int(arg) for arg in input().split()]
for x in range(a, b + 1):
    if x - a < k or b - x < k:
        print(x)

### FIXED CODE ###

# PROBLEM B
a, b, k = [int(arg) for arg in input().split()]
if a + k < b + 1 - k:
    for x in range(a, a + k):
        print(x)
    for x in range(b+1-k, b+1):
        print(x)
else:
    for x in range(a, b + 1):
        if x - a < k or b - x < k:
            print(x)
### BUGGY CODE ###

N = int(input())
arr = []
for _ in range(N):
  line = input()
  if line not in arr:
    arr.append(line)
print(len(arr))  
  
  
  
  
  

### FIXED CODE ###

N = int(input())
arr = set()
s = 0
for _ in range(N):
  arr.add(input())
  
print(len(arr))
### BUGGY CODE ###

# E - Coprime
from math import gcd
from functools import reduce

def gcd_list(numbers):
    return reduce(gcd, numbers)

def lcm(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

N = int(input())
A = list(map(int,input().split()))
seki = 1
for a in A:
    seki *= a
if lcm_list(A)==seki:
    print('pairwise coprime')
elif gcd_list(A)==1:
    print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

# E - Coprime
from math import gcd

N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
MAX = 10**6
L = [0]*(MAX+1)

def prime(x):
    global L
    p = 2
    while x>1:
        if L[x]==1:
            return False
        if x%p==0:
            while x%p==0:
                x //= p
            tmp = p
            while tmp<=MAX:
                L[tmp] = 1
                tmp += p
        p = p+1 if p*p<x else x   
    return True
        
G = A[0]
pairwise = True
_ = prime(A[0])

for i in range(1,N):
    a = A[i]
    if pairwise:
        pairwise = prime(a)
    G = gcd(G,a)

if pairwise:
    print('pairwise coprime')
elif G==1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

import numpy as np

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(n):
        if k <= a[i]:
            continue
        dp = np.zeros((k+1), dtype=np.bool)
        dp[0] = True
        for j in range(n):
            if k <= a[j] or j == i:
                continue
            dp[a[j]:] |= dp[:-a[j]]
        f = False
        for j in range(k-a[i], k):
            f |= dp[j]
        if not f:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    if sum(a) >= k:
        a.sort()
        L, R = -1, n-1
        while L+1 < R:
            P = (L+R+1)//2
            if k <= a[P]:
                R = P
                continue
            dp = np.zeros((k+1), dtype=np.bool)
            dp[0] = True
            for j in range(n):
                if k <= a[j] or j == P:
                    continue
                dp[a[j]:] |= dp[:-a[j]]
            f = False
            for j in range(k-a[P], k):
                f |= dp[j]
            if f:
                R = P
            else:
                L = P
        print(R)
    else:
        print(n)

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

n=int(input())
ans=0
a=list(map(int,input().split()))
now=max(a)
matc=list([] for i in range(n+2*now))
for i in range(n):
  matc[now-a[i]].append([i,0])
  matc[now+a[i]].append([i,1])
  now+=1
#print(matc)
for j in matc: 
  count0=0
  count1=0
  for k in j:
    if k[1]==0:
      count0+=1
    else:
      count1+=1
  ans+=count0*count1
print(ans)
       
       

### FIXED CODE ###

import numpy as np
n=int(input())
ans=0
a=list(map(int,input().split()))
now=max(a)
noww=now
k=n+2*now
matc=[0]*(n+2)
mat2=[0]*(n+2)
for i in range(n):
  neg=i-a[i]
  pos=i+a[i]
  if neg>=0:
    matc[neg]+=1
  if pos<=n:
    mat2[pos]+=1
  now+=1
#print(matc)
for j in range(n+2):
  ans+=matc[j]*mat2[j]
print(ans)
### BUGGY CODE ###

INF = float('inf')

class MinSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in rawData(self.size - 1)[:: -1]:
            self.data[i] = min(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = min(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = INF
        while L < R:
            if R & 1:
                R -= 1
                ret = min(ret, self.data[R - 1])
            if L & 1:
                ret = min(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

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

LRC = []
for _ in range(M):
    L, R, C = map(int, input().split())
    L -= 1
    LRC.append((L, R, C))
LRC.sort()

tree = MinSegTree(N)
tree.update(0, 0)
for l, r, c in LRC:
    newDist = tree.query(l, r) + c
    oldDist = tree.query(r - 1, r)
    if newDist < oldDist:
        tree.update(r - 1, newDist)

ans = tree.query(N - 1, N)
print(-1 if ans == INF else ans)

### FIXED CODE ###

INF = float('inf')

class MinSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in rawData(self.size - 1)[:: -1]:
            self.data[i] = min(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = min(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = INF
        while L < R:
            if R & 1:
                R -= 1
                ret = min(ret, self.data[R - 1])
            if L & 1:
                ret = min(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

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

LRC = []
for _ in range(M):
    L, R, C = map(int, input().split())
    L -= 1
    LRC.append((L, R, C))
LRC.sort()

tree = MinSegTree(N)
tree.update(0, 0)
for l, r, c in LRC:
    newDist = tree.query(l, r) + c
    oldDist = tree.query(r - 1, r)
    if newDist < oldDist:
        tree.update(r - 1, newDist)

ans = tree.query(N - 1, N)
print(-1 if ans == INF else ans)
### BUGGY CODE ###

n = int(input())

print(0)
s0 = str(input())

print(n-1)

def is_ok(x):
    print(x)
    s = str(input())
    if x%2 == 1:
        if s != s0:
            return False
        else:
            return True
    else:
        if s == s0:
            return False
        else:
            return True


l = 0
r = n-1
while l+1 < r:
    c = (l+r)//2
    if is_ok(c):
        r = c
    else:
        l = c


### FIXED CODE ###

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

    def q(i):
        print(i, )
        s = str(input())
        if s == 'Vacant':
            exit()
        else:
            return s

    x = q(n-1)
    x = q(0)

    def ok(m):
        if m == 0:
            return False
        else:
            if (m%2 == 0 and q(m) != x) or (m%2 == 1 and q(m) == x):
                return True
            else:
                return False

    l = 0
    r = n-1
    while l+1 < r:
        c = (l+r)//2
        if ok(c):
            r = c
        else:
            l = c

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

n = int(input())
s = input().split()
for sn in s:
    sn = int(sn)

q = int(input())
t = input().split()
for tn in t:
    tn = int(tn)

answer = 0

import math
for tn in t:
    smin = 0
    smax = n - 1
    c = math.floor(n - 1 / 2)
    while(smax - smin > 0):
        if(tn == s[c]):
            answer = answer + 1
            break
        elif(tn > s[c]):
            smin = c
            c = math.floor((smin + smax) / 2) 
        elif(tn < s[c]):
            smax = c
            c = math.floor((smin + smax) / 2)

print(answer)
    


### FIXED CODE ###

n = int(input())
sinput = input().split()
s=[]
for i in range(n):
    s.append(int(sinput[i]))

q = int(input())
tinput = input().split()
t=[]
for i in range(q):
    t.append(int(tinput[i]))
answer = 0

import math
for tn in t:
    smin = 0
    smax = n - 1
    c = math.floor((n - 1) / 2)
    while(smax - smin > 1):
        if(tn == s[c]):
            answer = answer + 1
            break
        elif(tn > s[c]):
            if(tn == s[smax]):
                answer = answer + 1
                break
            smin = c
            c = math.floor((smin + smax) / 2) 
        elif(tn < s[c]):
            if(tn == s[smin]):
                answer = answer + 1
                break
            smax = c
            c = math.floor((smin + smax) / 2)

print(answer)
### BUGGY CODE ###

h, k = map(int, input().split())
lis = list(map(int, input().split()))
if len(lis) >= k:
    for i in range(k):
        lis.remove(max(lis))
else:
    lis = []
    
print(sum(lis))

### FIXED CODE ###

h, k = map(int, input().split())
lis = list(map(int, input().split()))
if h >= k:
    lis.sort(reverse=True)
    lis = lis[k:]
else:
    lis = []
    
print(sum(lis))
### BUGGY CODE ###

import math
n=int(input())

for p in range(1, n+1):
  right=math.floor(p**(5/12))+2
  cnt=0
  for i in range(1, right):
    for j in range(1, i+1):
      for k in range(1, j+1):
        if (i+j+k)**2-i*j-j*k-k*i==p:
          if i==j and j==k:
            cnt+=1
          elif i==j and j!=k:
            cnt+=3
          elif j==k and k!=i:
            cnt+=3
          elif k==i and i!=j:
            cnt+=3
          elif i!=j and j!=k and k!=i:
            cnt+=6
  print(cnt)

### FIXED CODE ###

n=int(input())
lst=[0]*10000000
for i in range(1, 101):
  for j in range(1, i+1):
    for k in range(1, j+1):
      temp=i**2+j**2+k**2+i*j+j*k+k*i
      if i==j and j==k:
        lst[temp+1]+=1
      elif i==j and j!=k:
         lst[temp+1]+=3
      elif j==k and k!=i:
         lst[temp+1]+=3
      elif k==i and i!=j:
         lst[temp+1]+=3
      elif i!=j and j!=k and k!=i:
         lst[temp+1]+=6
for p in range(1, n+1):
  print(lst[p+1])
### BUGGY CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

def ncr(n, r):
    a = 1
    b = 1
    for i in range(r):
        # a = (a * (n - i) % MOD)
        # b = (b * (r - i) % MOD)

        a *= ((n - i) % MOD)
        b *= ((r - i) % MOD)

    return a * pow(b, MOD - 2, MOD) % MOD

N, A, B = MI()

s = pow(2, N, MOD) - 1
ab = (ncr(N, A) + ncr(N, B)) % MOD

print((s - ab)  % MOD)


### FIXED CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

def ncr(n, r):
    a = 1
    b = 1
    for i in range(r):
        a = (a * (n - i) % MOD)
        b = (b * (r - i) % MOD)

        # a *= ((n - i) % MOD)
        # b *= ((r - i) % MOD)

    return a * pow(b, MOD - 2, MOD) % MOD

N, A, B = MI()

s = pow(2, N, MOD) - 1
ab = (ncr(N, A) + ncr(N, B)) % MOD

print((s - ab)  % MOD)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
done = []
e = 0
for ai in a:
    if ai not in done:
        if a.count(ai) % 2 == 0:
            e += 1
        done.append(ai)
ans = len(done) - (e % 2)
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
c = 0
e = 0
i = 0
while True:
    c += 1
    cai = 1
    while i != n - 1 and a[i] == a[i + 1]:
        cai += 1
        if i != n - 1:
            i += 1
        else:
            break
    if cai % 2 == 0:
        e += 1
    if i != n - 1:
        i += 1
    else:
        break
ans = c - (e % 2)
print(ans)
### BUGGY CODE ###

num=int(input())
s=input()
count=0
for a in range(num-2):
  for b in range(a+1,num-1):
    for c in range(b+1,num):
      if (s[a]!=s[b] and s[b]!=s[c] and s[a]!=s[c]) and c-b!=b-a:
        count=count+1
print(count)

### FIXED CODE ###

num=int(input())
word=input()
alound=word.count("R")*word.count("G")*word.count("B")
for i in range(num-2):
  for j in range(i+1,num-1):
    k=2*j-i
    if k<=num-1:
      if word[i]!=word[j] and word[i]!=word[k] and word[k]!=word[j]:
        alound=alound-1
print(alound)
### BUGGY CODE ###

n=int(input())
count=0
li=[0 for i in range(n)]
for i in range(n):
    a=int(input())
    li[i]=a
li.sort()
i=0
while i<n:
    x=li.count(li[i])
    if x%2==1:
        count+=1
    i+=x
print(count)

### FIXED CODE ###

n=int(input())
count=0
li=[0 for i in range(n)]
for i in range(n):
    a=int(input())
    li[i]=a
li.sort()
i=0
x=1
while i<n-1:
    if li[i]==li[i+1]:
        x+=1
        if i+2==n-1:
            count+=1
    else:
        x=1
        if i+1==n-1:
            count+=1
    if x%2==1:
        count+=1
    i+=x
    x=1
print(count)