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

from bisect import bisect_left
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N = int(input())
a = set([int(c) for c in input().split()])
a = sorted(list(a))
X = a[-1]//2
i = bisect_left(a, X)
j = i-1 if i>0 else 0
h = i+1 if i<N-1 else N-1
I = a[i]
J = a[j]
H = a[h]
ci = cmb(a[-1],I)
cj = cmb(a[-1],J)
ch = cmb(a[-1],H)
if max(ci,cj,ch)==ci and i!= N-1:
  print(a[-1],a[i])
elif max(ci,cj,ch)==ch and h!=N-1:
  print(a[-1],a[h])
else:
  print(a[-1],a[j])

### FIXED CODE ###

N = int(input())
a = set([int(c) for c in input().split()])
a = sorted(list(a))
X = a[-1]//2+1 if a[-1]%2==1 else a[-1]//2
m = 10**9
x = 0
for i in range(N-1):
  if abs(a[i]-X)<m:
    m = abs(a[i]-X)
    x = i
print(a[-1],a[x])
### BUGGY CODE ###

N , K = map(int,input().split())
h = list(map(int,input().split()))
inf = float('inf')
dp = [inf] * N
if K == 1:
    ans = 0
    for i in range(N - 1):
        ans += abs(h[i + 1] - h[i])
    print(ans)
    exit()

for i in range(N):
    if i == 0:
        min_cost = 0
    elif i == 1:
        min_cost = abs(h[1] - h[0])
    else:
        corrent = h[i]
        tmp_min = min(abs(corrent - h[i - K]) + dp[i - K] , abs(corrent - h[i - K + 1]) + dp[i - K + 1])
        for j in range(K - 2):
            tmp_min = min(abs(corrent - h[i - K + 2 + j]) + dp[i - K + 2 + j], tmp_min)
        min_cost = tmp_min
    dp[i] = min_cost
#print(dp)
print(dp[N - 1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N , K = map(int,input().split())
h = list(map(int,input().split()))
inf = float('inf')
dp = [inf] * N
if K == 1:
    ans = 0
    for i in range(N - 1):
        ans += abs(h[i + 1] - h[i])
    print(ans)
    exit()

for i in range(N):
    if i == 0:
        min_cost = 0
    elif i == 1:
        min_cost = abs(h[1] - h[0])
    else:
        current = h[i]
        tmp_min = min(abs(current - h[i - K]) + dp[i - K] , abs(current - h[i - K + 1]) + dp[i - K + 1])
        for j in range(K - 2):
            tmp_min = min(abs(current - h[i - K + 2 + j]) + dp[i - K + 2 + j], tmp_min)
        min_cost = tmp_min
    dp[i] = min_cost
#print(dp)
print(dp[N - 1])
### BUGGY CODE ###

N,M = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(M)]

for i in range(M):
  l1 = list(range(l[i][0],l[i][1]+1))
  if i == 0:
    valid = l1
  valid = set(valid) & set(l1)
print(len(valid))



### FIXED CODE ###

N,M = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(M)]

for e in l:
  L,R = e[0],e[1]
  if e == l[0]:
    _L,_R = L,R
  else:
    if _L < L:
      _L = L
    if _R > R:
      _R = R
if _R - _L >= 0:
  print(_R - _L + 1)
else:
  print(0)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0]*n

for i in range(k):
  for j in range(n):
    for k in range(n):
      if a[k] >= abs(k-j):
        b[j] += 1
  a = b  
  b = [0]*n
  
print(*a)


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[0]*n
c=[0]*n
cnt=0
while cnt<min(k,101):
  cnt+=1
  for i in range(n):
    b[max(0,i-a[i])]+=1
    if i+a[i]<n-1:
      b[i+a[i]+1]-=1
    c[0]=b[0]
  for j in range(n-1):
    c[j+1]=c[j]+b[j+1]
  a=c
  b=[0]*n
  c=[0]*n
print(*a)
### BUGGY CODE ###

n = int(input())
x = int(input(),2)

def popcount(n):
    return bin(n).count("1")

pops = popcount(x)
x_pop_p = x%(pops + 1)
try:
    x_pop_m = x%(pops - 1)
except:
    x_pop_m = 0
#print(x_pop_p)
#print(x_pop_m)
#print()
pows_of_2 = [0]*(n)
pows_of_2[0] = 1
for i in range(1,n):
    pows_of_2[i] = pows_of_2[i-1] * 2
for i in reversed(range(0,n)):
    bit = x^(1<<i)
    #print(bin(bit))
    #print(bit)
    #print(popcount(bit))
    if bit == 0:
        print(0)
        continue
    if x&(1<<i):
        tmp = (x_pop_m - pows_of_2[i])%(pops - 1)
    else:
        tmp = (x_pop_p + pows_of_2[i]) % (pops + 1)
    #print(tmp)
    if tmp == 0:
        print(1)
        continue
    cnt = 2
    tmp_pop = popcount(tmp)
    if tmp_pop == 0:
        print(cnt-1)
        continue
    tmp = tmp % tmp_pop
    while tmp > 0:
        cnt += 1
        tmp_pop = popcount(tmp)
        if tmp_pop == 0:
            print(cnt-1)
            continue
        tmp %= tmp_pop
    print(cnt)
    #print()

### FIXED CODE ###

n = int(input())
s = input()
x = int(s, 2)
pcx = s.count("1")
pc1 = x % (pcx - 1) if pcx > 1 else 0
pc2 = x % (pcx + 1)

def f(j):
    cnt = 0
    while j:
        j %= bin(j).count("1")
        cnt += 1
    return cnt

for i, y in enumerate(s):
    k = n - 1 - i
    if y == "0":
        print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)
### BUGGY CODE ###

K = int(input())

ans = 1
a = 7
i = K
while K > 0:
    m = a % K
    if m == 0:
        print(ans)
        break
    else:
        ans += 1
        a = m * 10 + 7
        i -= 1
if m != 0:
    print(-1)


### FIXED CODE ###

K = int(input())

ans = 1
a = 7
i = K
while i > 0:
    m = a % K
    if m == 0:
        print(ans)
        break
    else:
        ans += 1
        a = m * 10 + 7
        i -= 1
if m != 0:
    print(-1)
### BUGGY CODE ###

N, x = map(int, input().split())
a = list(map(int, input().split()))
INF = float("inf")
num = INF
rec = [INF] * N
for k in range(N):
    tmp = 0
    for j in range(N):
        rec[j] = min(rec[j], a[j - k])
        tmp += rec[j]

    num = min(tmp + k * x, num)

print(num)


### FIXED CODE ###

N, x = map(int, input().split())
a = list(map(int, input().split()))
INF = float("inf")
num = INF
rec = [INF] * N
for k in range(N):
    tmp = 0
    for j in range(N):
        rec[j] = min(rec[j], a[j - k])
        tmp += rec[j]

    num = min(tmp + k * x, num)

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

import sys
input = sys.stdin.readline

def main():
    r, c, k = map(int, input().split())
    item = [[0]*c for _ in range(r)]
    
    for i in range(k):
        a, b, v = map(int, input().split())
        item[a-1][b-1] = v
    
    dp0 = [[0]*(c+1) for _ in range(r+1)]
    dp1 = [[0]*(c+1) for _ in range(r+1)]
    dp2 = [[0]*(c+1) for _ in range(r+1)]
    dp3 = [[0]*(c+1) for _ in range(r+1)]
    
    for i in range(r):
        for j in range(c):
            if item[i][j] == 0:
                dp0[i+1][j+1] = max([dp0[i][j+1], dp0[i+1][j], dp1[i][j+1], dp2[i][j+1], dp3[i][j+1]])
                dp1[i+1][j+1] = dp1[i+1][j]
                dp2[i+1][j+1] = dp2[i+1][j]
                dp3[i+1][j+1] = dp3[i+1][j]
                continue
            dp0[i+1][j+1] = max([dp0[i][j+1], dp0[i+1][j], dp1[i][j+1], dp2[i][j+1], dp3[i][j+1]])
            dp1[i+1][j+1] = max(dp0[i+1][j]+item[i][j], dp1[i+1][j], dp0[i][j+1]+item[i][j], dp1[i][j+1]+item[i][j], dp2[i][j+1]+item[i][j], dp3[i][j+1]+item[i][j])
            dp2[i+1][j+1] = max(dp1[i+1][j]+item[i][j], dp2[i+1][j])
            dp3[i+1][j+1] = max(dp2[i+1][j]+item[i][j], dp3[i+1][j])
    
    ans = max([dp0[r][c], dp1[r][c], dp2[r][c], dp3[r][c]])
    print(ans)
            
    
    
if __name__ == "__main__":
    main()




### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    r, c, k = map(int, input().split())
    item = [[0]*c for _ in range(r)]
    
    for i in range(k):
        a, b, v = map(int, input().split())
        item[a-1][b-1] = v
    
    dp0 = [[0]*(c+1) for _ in range(r+1)]
    dp1 = [[0]*(c+1) for _ in range(r+1)]
    dp2 = [[0]*(c+1) for _ in range(r+1)]
    dp3 = [[0]*(c+1) for _ in range(r+1)]
    
    for i in range(r):
        for j in range(c):
            if item[i][j] == 0:
                dp0[i+1][j+1] = max([dp0[i][j+1], dp0[i+1][j], dp1[i][j+1], dp2[i][j+1], dp3[i][j+1]])
                dp1[i+1][j+1] = dp1[i+1][j]
                dp2[i+1][j+1] = dp2[i+1][j]
                dp3[i+1][j+1] = dp3[i+1][j]
                continue
            dp0[i+1][j+1] = max([dp0[i][j+1], dp0[i+1][j], dp1[i][j+1], dp2[i][j+1], dp3[i][j+1]])
            dp1[i+1][j+1] = max(dp0[i+1][j]+item[i][j], dp1[i+1][j], dp0[i][j+1]+item[i][j], dp1[i][j+1]+item[i][j], dp2[i][j+1]+item[i][j], dp3[i][j+1]+item[i][j])
            dp2[i+1][j+1] = max(dp1[i+1][j]+item[i][j], dp2[i+1][j])
            dp3[i+1][j+1] = max(dp2[i+1][j]+item[i][j], dp3[i+1][j])
    
    ans = max([dp0[r][c], dp1[r][c], dp2[r][c], dp3[r][c]])
    print(ans)
            
    
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

MOD = 10**9 + 7

dp = [0] * (n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1

for i in range(2, n+1):
    if i in a:
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % MOD

print(dp[-1])

### FIXED CODE ###

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

MOD = 10**9 + 7

dp = [0] * (n+1)
flag = [False] * (n+1)
for i in a:
    flag[i] = True

dp[0] = 1
if 1 not in a:
    dp[1] = 1

for i in range(2, n+1):
    if flag[i]:
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % MOD

print(dp[-1])
### BUGGY CODE ###

from fractions import gcd

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

l = A[0]
for i in range(1, N):
    l = l * A[i] // gcd(l, A[i])

for i in range(N):
    res += l//A[i]

print(res % 1000000007)

### FIXED CODE ###

from fractions import gcd

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

l = A[0]
for i in range(1, N):
    l = l * A[i] // gcd(l, A[i])

for a in A:
    res += l//a

print(res % 1000000007)
### BUGGY CODE ###

n,t=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]


rieki=0
count=0
for ind,i in enumerate(A):
    lst=A[:ind+1]
    if(ind==len(A)-1):
        break
    elif(A[ind+1]-min(lst) > rieki):
        rieki=A[ind+1]-min(lst)
        count=1
    elif(A[ind+1]-min(lst) == rieki):
        count+=1


print(count)


### FIXED CODE ###

n,t=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]

c=0
dif=0
m=a[0]
for i in range(1,n):
    if(m>a[i]):
        m=a[i]
    if(dif<a[i]-m):
        c=1
        dif=a[i]-m
    elif(dif==a[i]-m):
        c+=1
print(c)
### BUGGY CODE ###

# # Educational DP Contest D
# 方針：dp[i][w] := i番目の物の中から，重さwを超えない時の価値の最大値
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]

dp = [[0] * (W+10) for _ in range(N+1)]

for i in range(N):
    for w in range(W+1):
        if w >= wv[i][0]:       # 重さwv[i][0]を入れられるか
            dp[i+1][w] = max(dp[i][w - wv[i][0]] + wv[i][1], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])

### FIXED CODE ###

# # Educational DP Contest D
# 方針：dp[i][w] := i番目の物の中から，重さwを超えない時の価値の最大値
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]

dp = [[0] * (W+10) for _ in range(N+1)]

for i in range(N):
    for w in range(W+1):
        if w >= wv[i][0]:       # 重さwv[i][0]を入れられるか
            dp[i+1][w] = max(dp[i][w - wv[i][0]] + wv[i][1], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])
### BUGGY CODE ###

N=int(input())
*A,=map(int,input().split())
i=0
ans=0
while i<N:
    if i+1 in A:
        if A[i]==A.index(i+1)+1:
            ans+=1
    i+=1
print(ans//2)

### FIXED CODE ###

N=int(input())
*A,=map(int,input().split())
i=0
ans=0
while i<N:
    if i+1==A[A[i]-1]:
        ans+=1
    i+=1
print(ans//2)
### BUGGY CODE ###

def main():
    s = list(input())[::-1]
    ary_mod = [0] * 2019
    ary_mod[0] = 1
    now = 0

    for i, ss in enumerate(s):
        now += int(ss) *( 10 ** i) % 2019
        remind = now % 2019
        ary_mod[remind] += 1
    ans = 0
    for i, n in enumerate(ary_mod):
        ans += (n*(n-1)) // 2
    print(ans)
if __name__=='__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)


S = input()
N = len(S)
P = 2019

if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
    sys.exit()

num = [0] * P
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % P
    _10 *= 10
    _10 %= P
    ans += num[now]
    num[now] += 1

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

N, K = map(int, input().split())
ans = 0
if K % 2 != 0:
    M = [a for a in range(0, N+1, K)]
    M.pop(0)
else:
    M = [a for a in range(0, N+1, K//2)]
    M.pop(0)
for a in M:
    for b in M:
        for c in M:
            if ((a+b)%K) == ((b+c)%K) == ((c+a)%K) == 0:
                ans += 1
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
ans = 0
M1 = []
M2 = []
M1 = [a for a in range(N+1) if a % K == 0]
M1.pop(0)
if K % 2 == 0:
    M2 = [a for a in range(N+1) if a % K == K//2]
print(len(M1)**3 + len(M2)**3)
### BUGGY CODE ###

import collections

n=int(input())
s=[]

for i in range(n):
    s.append(input())

d=collections.Counter(s)
max_k_list = [kv[0] for kv in d.items() if kv[1] == max(d.values())]
max_k_list.sort()

for i in range(len(max_k_list)):
    print(max_k_list[i])

### FIXED CODE ###

import collections

n=int(input())
s=[]

for i in range(n):
    s.append(input())

d=collections.Counter(s).most_common()

ans=[]
past=d[0][1]

for i,m in d:
    if past==m:
        ans.append(i)
        past=m
    else:
        break

ans.sort()
for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

s = list(input())

q = int(input())

for i in range(q):
    t = list(input().split())
    
    if t[0] == "1":
        s = s[::-1]
    else:
        f = t[1]
        c = t[2]
        if f == "1":
            s.insert(0,c)
        else:
            s.append(c)
            
for i in s:
    print(i,end = "")

### FIXED CODE ###

s = list(input())

q = int(input())

before = []

after = []

cnt = 0

for i in range(q):
    t = list(input().split())
    
    if t[0] == "1":
        cnt += 1
    else:
        f = t[1]
        c = t[2]
        if f == "1":
            if cnt%2 == 0:
                before.append(c)                      
            else:
                after.append(c)
        else:
            if cnt%2 == 0:
                after.append(c)
            else:
                before.append(c)
                
if cnt%2 == 1:
    s.reverse()
    after.reverse()
    #before.reverse()
    for i in after:
        print(i,end = "")
    for i in s:
        print(i,end = "")
    for i in before:
        print(i,end = "")
else:
    before.reverse()
    before.extend(s)
    before.extend(after)
            
    for i in before:
        print(i,end = "")
### BUGGY CODE ###

def popcount(number, bit_counter):
    num = number
    counter = 0
    while num != 0: # 5,6回程度
        bit_con = 0
        if counter == 0:
            bit_con = bit_counter  
        else:
            bit_con = bin(num)[2:].count('1')
        num = num % bit_con
        counter += 1

    return counter

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X_str= readline()
    X = list(X_str)
    bit_count = X_str.count('1')

    for i in range(N):
        # ビットの反転
        x_copy = X.copy()
        bit_count_n = bit_count
        if x_copy[i] == '0':
            x_copy[i] = '1'
            bit_count_n += 1
        else:
            x_copy[i] = '0'
            bit_count_n -= 1

        bit_int = int("".join(x_copy), 2)

        print(popcount(bit_int, bit_count_n))






### FIXED CODE ###

def popcount(n):
    bit_count = bin(n).count('1')
    n = n % bit_count 
    return n

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X = readline()
    bit_count = X.count('1')
    mod1 = int(X, 2) % (bit_count + 1)
    mod2 = int(X, 2) % (bit_count - 1) if (bit_count - 1) != 0 else 0

    for i in range(N):
        if X[i] == '0':
            X_rest = (mod1 + pow(2, N - 1 - i, bit_count + 1)) % (bit_count + 1)
        else:
            if bit_count - 1 != 0:
                X_rest = (mod2 - pow(2, N - 1 - i, bit_count - 1)) % (bit_count - 1)
            else:
                print(0)
                continue

        counter = 1
        while X_rest != 0:
            X_rest = popcount(X_rest)
            counter += 1
        print(counter)
### BUGGY CODE ###

import numpy as np


def main():
    N = int(input())
    A = np.array([])
    B = np.array([])
    for i in range(0, N):
        a, b = map(int, input().split())
        A = np.append(A, [a])
        B = np.append(B, [b])
    
    # 自分に一番良い手と相手にとって一番良い手を考える
    # 自分にとって一番良い手が複数ある場合、その中で相手が一番良い手を選ぶ
    # 自分にとって一番良い手が１つの場合、相手にとって一番良い手との比較をして、差が大きい方を選ぶ
    # 自分にとって良いてと相手にとっていい手が同じ場合(相手にとっていい手が複数ある場合も)、それを選ぶ
    sub(N, A, B)


def sub(N, A, B):
    takahashi = 0
    aoki = 0
    # 足し算して一番大きいところからとる
    sum_AB = A + B
    #  print(A, B)
    for i in range(1, N + 1):
        max_idx = np.argmax(sum_AB)
        #  print(sum_AB, max_idx)
        if i % 2 == 1:
            takahashi += A[max_idx]
        else:
            aoki += B[max_idx]
        sum_AB[max_idx] = -1

    print(int(takahashi - aoki))



main()


### FIXED CODE ###

import numpy as np


def main():
    N = int(input())
    A = []
    B = []
    for i in range(0, N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
    
    takahashi = 0
    aoki = 0
    # 足し算して一番大きいところからとる
    A = np.array(A)
    B = np.array(B)
    sum_AB = A + B
    l = sum_AB.argsort()[::-1]
    takahashi = sum([A[i] for i in [j for idx, j in enumerate(l) if idx % 2 == 0]])
    aoki = sum([B[i] for i in [j for idx, j in enumerate(l) if idx % 2 != 0]])

    print(int(takahashi - aoki))


main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Mar  4 19:06:03 2020

@author: Kanaru Sato
"""
import math

X = int(input())

target = X
flag = 0

while flag == 0:
    for i in range(2, int(math.sqrt(X))+1):
        if X%i == 0:
            X += 1
            break
        elif i == int(math.sqrt(X)):
            flag = 1
            break
        else:
            continue

print(X)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Mar  4 19:06:03 2020

@author: Kanaru Sato
"""
import math

X = int(input())

target = X
flag = 0

if X == 2 or X == 3:
    flag = 1

while flag == 0:
    rootX = int(math.sqrt(X))
    for i in range(2, rootX+1):
        if X%i == 0:
            if X%2 == 0:
                X += 1
                break
            else:
                X += 2
                break
        elif i == rootX:
            flag = 1
            break
        else:
            continue

print(X)
### BUGGY CODE ###

from numba import jit
N,K = map(int, input().split())
S = []
for i in range(K):
    L,R = map(int, input().split())
    S += [ j for j in range(L,R+1)]
S = set(S)

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

@jit
def F():
    for j in range(1,N):
        for s in S:
            if j + s > N or step[j] == 0:
                continue
            step[j+s] += (step[j]%998244353)
            step[j+s] %= 998244353
    return step[N]

print(F())

### FIXED CODE ###

mod = 998244353
n, k = map(int, input().split())
lr = [list(map(int, input().split())) for i in range(k)]
for i in range(k):
    lr[i][1] += 1

dp = [0]*n
dp[0] = 1
for i in range(1,n):
    dp[i] = dp[i-1]
    if i == 1:
        dp[1] = 0
    for l,r in lr:
        if i - l >= 0:
            dp[i] += dp[i-l]
        if i - r >= 0:
            dp[i] -= dp[i-r]
        dp[i] %= mod
print(dp[n-1])
### BUGGY CODE ###

inf = 2019
L, R = map(int, input().split())
ans = 2018

for i in range(L, L + 2019):
    if i >= R:
        break
    for j in range(i + 1, R + 1):
        tmp = int((i * j) % inf)
        ans = min(ans, tmp)
    if ans == 0:
        break

print(ans)


### FIXED CODE ###

inf = 2019
L, R = map(int, input().split())
ans = 0
df = R - L
if df < 2019:
    L = L % inf
    R = L + df
    ans = 2019
    for i in range(L, R):
        for j in range(i + 1, R + 1):
            tmp = int((i * j) % inf)
            ans = min(ans, tmp)

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

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

MOD = 1000000007

def pow_mod(x, y):
    if y == 0: return 1
    ans = 1
    while y > 1:
        if y % 2 != 0: 
            ans *= x
            ans %= MOD
        x *= x
        x %= MOD
        y //= 2
    return ans * x % MOD 

mod_inv = lambda x: pow_mod(x, MOD - 2)

nCk = {0: 1}

for i in range(1, max(a,b) + 1):
  nCk[i] = nCk[i-1] * ((n-i+1) % MOD)
  nCk[i] %= MOD
  nCk[i] *= mod_inv(i)
  nCk[i] %= MOD

print((pow_mod(2, n) - 1 - nCk[a] - nCk[b]) % MOD)



### FIXED CODE ###

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

MOD = 1000000007

def pow_mod(x, y):
    if y == 0: return 1
    ans = 1
    while y > 1:
        if y % 2 != 0: 
            ans *= x
            ans %= MOD
        x *= x
        x %= MOD
        y //= 2
    return ans * x % MOD 

mod_inv = lambda x: pow_mod(x, MOD - 2)

nCk = {0: 1}

for i in range(1, max(a,b) + 1):
  nCk[i] = nCk[i-1] * ((n-i+1) % MOD)
  nCk[i] %= MOD
  nCk[i] *= mod_inv(i)
  nCk[i] %= MOD

print((pow_mod(2, n) - 1 - nCk[a] - nCk[b]) % MOD)
### BUGGY CODE ###

# D - AtCoder Express 2

import bisect, copy

N, M, Q = map(int, input().split())
LRidx = [list(map(int, input().split())) + [i] for i in range(M)]
p, q = [], []
for _ in range(Q):
    tmp_p, tmp_q = map(int, input().split())
    p.append(tmp_p)
    q.append(tmp_q)

# l,rはそれぞれ高々500通りなので、l,rの値に対して探索結果をメモしておく
LRidx = sorted(LRidx, key = lambda x: x[0])
tmp_L = [LRidx[idx][0] for idx in range(M)]
l_memo = [[-1] for _ in range(N+1)]
l_ok_idx = [[] for _ in range(Q)]
for i in range(Q):
    if l_memo[p[i]] and l_memo[p[i]][0] == -1:
        b_idx = bisect.bisect_left(tmp_L, p[i])
        tmp = [LRidx[j][2] for j in range(b_idx, M)]
        l_ok_idx[i] = tmp.copy()
        l_memo[p[i]] = tmp.copy()
    else:
        l_ok_idx[i] = l_memo[p[i]].copy()
    
LRidx = sorted(LRidx, key = lambda x: x[1])
tmp_R = [LRidx[idx][1] for idx in range(M)]
r_memo = [[-1] for _ in range(N+1)]
r_ok_idx = [[] for _ in range(Q)]
for i in range(Q):
    if l_ok_idx[i] and r_memo[q[i]] and r_memo[q[i]][0] == -1:
        b_idx = bisect.bisect_right(tmp_R, q[i])
        tmp = [LRidx[j][2] for j in range(b_idx)]
        r_ok_idx[i] = tmp.copy()
        r_memo[q[i]] = tmp.copy()
    else:
        r_ok_idx[i] = r_memo[q[i]].copy()
    
for i in range(Q):
    print(len(set(l_ok_idx[i]) & set(r_ok_idx[i])))

### FIXED CODE ###

# D - AtCoder Express 2

import numpy as np

N, M, Q = map(int, input().split())
LR = np.zeros((N+1, N+1))

for _ in range(M):
    l, r = map(int, input().split())
    LR[l,r] += 1

np.cumsum(LR, axis = 0, out = LR)
np.cumsum(LR, axis = 1, out = LR)
    
for _ in range(Q):
    p, q = map(int, input().split())
    print(int(LR[q,q] - LR[p-1,q] - LR[q,p-1] + LR[p-1,p-1]))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math
n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))

dp = [0 for _ in range(n)]
if 1 in a:
    dp[0] = 0
elif not 1 in a:
    dp[0] = 1
if n >= 2 and 2 in a:
    dp[1] = 0
elif n >= 2 and not 2 in a:
    dp[1] = dp[0] + 1

for i in range(2, n):
    if i + 1 in a:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % (pow(10, 9) + 7)
#print(dp)
print(dp[n - 1] % (pow(10, 9) + 7))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))

if m == 0:
    dp = [0 for _ in range(n)] #i + 1段目に登る方法の数
    dp[0] = 1
    if n >= 2:
        dp[1] = 2
    for i in range(2, n):
        dp[i] = (dp[i - 1] + dp[i - 2]) % (pow(10, 9) + 7)
    print(dp[n - 1])
    exit()

tmp = 0
dp = [0 for _ in range(n)]
if 1 == a[tmp]:
    dp[0] = 0
    tmp += 1
else:
    dp[0] = 1
if n >= 2 and tmp < m and 2 == a[tmp]:
    dp[1] = 0
    tmp += 1
elif n >= 2 and (tmp >= m or 2 != a[tmp]):
    dp[1] = dp[0] + 1

for i in range(2, n):
    if tmp < m and i + 1 == a[tmp]:
        dp[i] = 0
        tmp += 1
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % (pow(10, 9) + 7)
#print(dp)
print(dp[n - 1] % (pow(10, 9) + 7))