Problem:


Score : 400 points

Problem Statement

Akari has n kinds of flowers, one of each kind.

She is going to choose one or more of these flowers to make a bouquet.

However, she hates two numbers a and b, so the number of flowers in the bouquet cannot be a or b.

How many different bouquets are there that Akari can make?

Find the count modulo (10^9 + 7).

Here, two bouquets are considered different when there is a flower that is used in one of the bouquets but not in the other bouquet.

Constraints

All values in input are integers.

2 \leq n \leq 10^9

1 \leq a < b \leq \textrm{min}(n, 2 \times 10^5)

Input

Input is given from Standard Input in the following format:

n a b

Output

Print the number of bouquets that Akari can make, modulo (10^9 + 7). (If there are no such bouquets, print 0.)

Sample Input 1

4 1 3

Sample Output 1

7

In this case, Akari can choose 2 or 4 flowers to make the bouquet.

There are 6 ways to choose 2 out of the 4 flowers, and 1 way to choose 4, so there are a total of 7 different bouquets that Akari can make.

Sample Input 2

1000000000 141421 173205

Sample Output 2

34076506

Print the count modulo (10^9 + 7).



Sample input:
4 1 3


Sample output:
7

Submission status: Accepted

Solution code:
def mod_inverse(n, mod=10**9+7):
    return pow(n, mod-2, mod)


def combination(n, k, mod=10**9+7):
    numer = denom = 1
    for i in range(k):
        numer = (numer * (n-i)) % mod
        denom = (denom * (i+1)) % mod
    return (numer * mod_inverse(denom, mod)) % mod


mod = 10**9+7
n, a, b = map(int, input().split())
ans = (pow(2, n, mod) - 1 - combination(n, a) - combination(n, b)) % mod
print(ans)

Submission status: Accepted

Solution code:
def comb(n,r,mod):
	'''
	return nCr
	O(min{n-r, r})
	'''
	a=1
	b=1
	r = min(r,n-r)
	for i in range(r):
		a = a*(n-i)%mod
		b = b*(i+1)%mod
	return a*pow(b,mod-2,mod)%mod


mod = 10**9+7

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

ans = pow(2, N, mod) -1
ans -= comb(N,a,mod)
if ans<0:
    ans += mod
ans -= comb(N,b,mod)
if ans<0:
    ans += mod

print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
n,a,b=map(int,input().split())
ans=pow(2,n,mod)-1
x=1
p=1
for i in range(a):
    p=p*(n-i)
    p%=mod
    x=x*(i+1)
    x%=mod
tmp1=(p*pow(x,mod-2,mod))%mod
y=1
q=1
for j in range(b):
    q=q*(n-j)
    q%=mod
    y=y*(j+1)
    y%=mod
tmp2=(q*pow(y,mod-2,mod))%mod
print((ans-tmp1-tmp2)%mod)

Submission status: Accepted

Solution code:
# コンビネーション
mod = 10**9+7
def cmb(n, r, mod=mod):
    ret = 1
    for k in range(1, r+1):
        ret = ret * (n-k+1) * mod_inv(k) % mod
    return ret

# modを取りながらべき乗する
def power_func(a,n,mod=mod):
    bi=str(format(n,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %mod
        if bi[i]=="1":
            res=(res*a) %mod
    return res

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m=mod):
    x = extgcd(a,m)[0]
    return (m+x%m)%m


import sys
input = sys.stdin.readline

N, A, B = map(int, input().split())
ans = (power_func(2, N) - 1 - cmb(N, A) - cmb(N, B))%mod
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,*a = [int(i) for i in read().split()]
#a = [int(i) for i in readline().split()]
#n = int(input())

n,a,b = [int(i) for i in read().split()]

MOD = 10**9+7
ans = pow(2,n,MOD)-1

def choose(n,r):
    res = 1
    fac = 1
    for i in range(r):
        res *= n-i
        res %= MOD
        fac *= i+1
        fac %= MOD
    return res*pow(fac,MOD-2,MOD)%MOD        


ans -= choose(n,a)
ans -= choose(n,b)

#print(choose(n,a),choose(n,b))

print(ans%MOD)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

MOD = 10**9+7
def comb(a, b):
    res = 1
    pres = 1
    for i in range(b):
        res = (res*(a-i))%MOD
        pres = (pres*(i+1))%MOD
    return res*pow(pres, MOD-2, MOD) % MOD


N, A, B = map(int, readline().split())
ans = pow(2, N, MOD) - 1 - comb(N, A) - comb(N, B)
print(ans%MOD)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))

def main():
    N,a,b = MI()

    ans = ModInt(2)**N
    A = ModInt(1)
    for i in range(a):
        A*=(N-i)
        A/=i+1

    B = ModInt(1)
    for i in range(b):
        B*=(N-i)
        B/=i+1
    ans += - 1 - A - B
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, a, b = [int(i) for i in input().split()]
p = 10**9+7


def comb(a, b):
    c = 1
    for i in range(b):
        c *= a - i
        c %= p
    d = 1
    for i in range(b):
        d *= i + 1
        d %= p
    return c*pow(d, p-2, p)


ans = pow(2, n, p) - 1 - comb(n, a) - comb(n, b)
print(ans % p)

Submission status: Accepted

Solution code:
mod = 10**9+7

def comb(n,m,p=10**9+7):
    if n < m : return 0
    if n < 0 or m < 0:return 0
    m = min(m, n-m)
    top = bot = 1
    for i in range(m):
        top = top*(n-i) % p
        bot = bot*(i+1) % p
    bot = pow(bot, p-2, p)
    return top*bot % p

n,a,b = map(int, input().split())
ans = pow(2, n, mod)-1 - comb(n,a) - comb(n, b)
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def comb(a,b):
        res = 1
        for i in range(b):
            res *= n-i
            res %= mod
            res *= pow(i+1,mod-2,mod)
            res %= mod
        return res
    n,a,b = LI()
    ans = pow(2,n,mod)-1
    ans -= comb(n,a)+comb(n,b)
    ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution 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)-1-comb(N,A)-comb(N,B))%MOD)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, a, b = na()
mod = 1000000007

def comb(n, r, mod):
    if n < 0 or r < 0 or r > n: return 0
    nu = 1
    de = 1
    for i in range(r):
        nu = nu * (n-i) % mod
        de = de * (i+1) % mod
    return nu * inv(de, mod) % mod

def inv(a, mod):
    b = mod
    p, q = 1, 0
    while b > 0:
        c = a//b
        d = a; a = b; b = d % b
        d = p; p = q; q = d-c*q
    return p+mod if p < 0 else p

print((pow(2, n, mod) - comb(n, a, mod) - comb(n, b, mod) + 2*mod + mod - 1)%mod)

Submission status: Runtime Error

Solution code:
p = pow(10, 9) + 7

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

if n == 2:
  print(0)
  return

inversions = [0, 1] # 0 is unreachable
    
for i in range(2, max(a, b) + 1):
    inversion = p - (p // i) * inversions[p % i]
    inversions.append(inversion)

c = [1, n]

for i in range(2, max(a, b) + 1):
    nCi = (c[i - 1] * (n - i + 1) % p) * inversions[i] % p # nCi = nCi-1 * (n - i + 1) / i

    if nCi < 0:
        nCi += p

    c.append(nCi)


ans = pow(2, n, p) - (c[0] + c[a] + c[b])
if ans < 0:
    ans += p
print(ans)

Submission status: Runtime Error

Solution code:
# nC0 + nC1 + nC2 + ... + nCn - (nC0 + nCa + nCb)
p = pow(10, 9) + 7 # prime number

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

if n == 2:
  print(0)
  return

inversions = [0, 1] # 0 is unreachable
    
for i in range(2, max(a, b) + 1):
    inversion = p - (p // i) * inversions[p % i]
    inversions.append(inversion)

c = [1, n]

for i in range(2, max(a, b) + 1):
    nCi = (c[i - 1] * (n - i + 1) % p) * inversions[i] % p # nCi = nCi-1 * (n - i + 1) / i

    if nCi < 0:
        nCi += p

    c.append(nCi)


ans = pow(2, n, p) - (c[0] + c[a] + c[b])
if ans < 0:
    ans += p
print(ans)

Submission status: Runtime Error

Solution code:
# nC0 + nC1 + nC2 + ... + nCn - (nC0 + nCa + nCb)
p = pow(10, 9) + 7 # prime number

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

if n == 2:
  return print(0)

inversions = [0, 1] # 0 is unreachable
    
for i in range(2, max(a, b) + 1):
    inversion = p - (p // i) * inversions[p % i]
    inversions.append(inversion)

c = [1, n]

for i in range(2, max(a, b) + 1):
    nCi = (c[i - 1] * (n - i + 1) % p) * inversions[i] % p # nCi = nCi-1 * (n - i + 1) / i

    if nCi < 0:
        nCi += p

    c.append(nCi)


ans = pow(2, n, p) - (c[0] + c[a] + c[b])
if ans < 0:
    ans += p
print(ans)

Submission status: Runtime Error

Solution code:
# nC0 + nC1 + nC2 + ... + nCn - (nC0 + nCa + nCb)
p = pow(10, 9) + 7

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

inversions = [0, 1]
    
for i in range(2, min(max(a, b) + 1, p)):
    i %= p
    inversion = p - (p // i) * inversions[p % i]
    inversions.append(inversion)

c = [1, n]
for i in range(2, max(a, b) + 1):
    nCi = (c[i - 1] * (n - i + 1) % p) * inversions[i % p] % p
    if nCi < 0:
        nCi += p
    c.append(nCi)


ans = pow(2, n, p) - (c[0] + c[a] + c[b])
print(ans < 0 ? ans + p : ans)

Submission status: Runtime Error

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

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

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

p = 10**9+7
r1 = 2 ** n - 1
r2 = cmb(n, a, p)
r3 = cmb(n, b, p)
print(r1-r2-r3)

Submission status: Runtime Error

Solution code:
# nC0 + nC1 + nC2 + ... + nCn - (nC0 + nCa + nCb)
p = pow(10, 9) + 7

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

def combination_of(n, k) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    
    if k == 0:
        return 1
    
    return int(combination_of(n, k - 1) * ((n - k + 1) / k) % p)

def for_combination_of(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    
    c = [1]
    
    for i in range(1, k + 1):
        c.append(int(c[i - 1] * ((n - i + 1) / i) % p))
    
    return c[k]

print("nC0 is", for_combination_of(n, 0))
print("nCa is", for_combination_of(n, a))
print("nCb is", for_combination_of(n, b))
ans = pow(2, n, p) - (combination_of(n, 0) + combination_of(n, a) + combination_of(n, b)) % p
print(ans % p)

Submission status: Runtime Error

Solution code:
n, a, b = tuple(map(int, input().split()))

def combination_of(n, k) -> int:
    numerator = 1
    for i in range(n - k + 1, n + 1):
        numerator *= i
    denominator = 1
    for i in range(1, k + 1):
        denominator *= i
    return int(numerator / denominator)
    
ans = pow(2, n, 1000000007) - pow((1 + combination_of(n, a) + combination_of(n, b)), 1, 1000000007)
print(ans)

Submission status: Runtime Error

Solution code:
n, a, b = tuple(map(int, input().split()))

def combination_of(n, k):
    numerator = 1
    for i in range(n - k + 1, n + 1):
        numerator *= i
    denominator = 1
    for i in range(1, k + 1):
        denominator *= i
    return int(numerator / denominator)
    
print(pow(2, n, 1000000007) - pow((1 + combination_of(n, a) + combination_of(n, b)), 1, 1000000007))

Submission status: Runtime Error

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


class Combination:

    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * \
                modinv[self.mod % i] % self.mod
        return modinv


n, a, b = LI()
comb = Combination(n)
print((pow(2, n, mod)-1-comb(n, a)-comb(n, b)) % mod)

Submission status: Runtime Error

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


class Combination:

    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # ??????????mod????????? O(n)
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0??n???mod????????? O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * \
                modinv[self.mod % i] % self.mod
        return modinv


n, a, b = LI()
comb = Combination(n)
print((pow(2, n, mod)-1-comb(n, a)-comb(n, b)) % mod)

Submission status: Runtime Error

Solution code:
import functools
import operator

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

def nCr(n, r):
    r = min(r, n-r)
    num = functools.reduce(lambda x, y: x*y%mod, range(n, n-r, -1))
    den = functools.reduce(lambda x, y: x*y%mod, map(lambda x: pow(x, mod-2, mod), range(1, r+1)))
    return num * den % mod

mod = 10**9 + 7
print((pow(2, n, mod) - nCr(n, a) - nCr(n, b) - 1) % mod)

Submission status: Runtime Error

Solution code:
def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u

def nCk(N, k, mod):
    ret_val = 1
    for i in range(k):
        ret_val *= (N - i)
        ret_val %= mod
        ret_val *= modinv(i + 1, mod)
        ret_val %= mod
    return ret_val


n, a, b = map(int, input().split())
MOD = 10 ** 9 + 7
all_cnt = pow(2, n, MOD) - 1
a_cnt = nCk(n, a, MOD)
b_cnt = nCk(n, b, MOD)
ans = all_cnt - a_cnt - b_cnt
print(ans　% MOD)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[23]:


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


# In[24]:


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


# In[25]:


ans = pow(2, n, mod)-1
ans -= nCk(n, a, mod) + nCk(n, b, mod)
print(ans%mod)


# In[ ]:

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[14]:


import math


# In[21]:


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


# In[22]:


ans = pow(2, n, mod)-1
ans -= nCk(n, a, mod) + nCk(n, b, mod)
print(ans%mod)


# In[ ]:

Submission status: Runtime Error

Solution code:
def main():
    n, a, b = map(int, input().split())
    mod = 10 ** 9 + 7 #素数
    
    def modpow(x, n, mod):
        res = 1
        while n:
            if n % 2:
                res *= x % mod
            x *= x % mod
            n >>= 1
        return res
    
    def cmb(n, r, mod):
        # 分子(n*(n-1)*...*(n-r+1))
        nume = 1
        for i in range(n-r+1, n+1):
            nume = nume * i
        # 分母（1*2*...*r）
        deno = 1
        for j in range(1, r+1):
            deno = deno * jc # % mod
        d = modpow(deno, mod-2, mod)
        return nume * d# % mod
    
    all_cmb = pow(2, n, mod) - 1
    bad_a = cmb(n, a, mod)
    bad_b = cmb(n, b, mod)    
    print((all_cmb-bad_a-bad_b) % mod)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
en, 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 = 10**4
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 )

mylist=list(range(1,en+1)) #1からenまでの配列
mylist.remove(a)
mylist.remove(b)

sum = 0
for r in  mylist:
  t = cmb(en,r,mod)
  sum += t
  
print(sum)

Submission status: Runtime Error

Solution code:
def cmb(a,b,c):
    b = min(b,a-b)
    num = 1
    for i in range(b):
        num = num*(n-i) % c
    den = 1
    for i in range(b):
        den = den*(i+1) % c
    return num*pow(den,-1,c) % c
mod = 10**9+7
n,a,b = map(int,input().split())
ans  = (pow(2,n,mod)-cmb(n,a,mod)-cmb(n,b,mod)-1) % mod
if ans < 0:
    ans = ans + mod
print(ans)

Submission status: Runtime Error

Solution code:
def comb_mod(n,r):
    mod = 10**9+7
    ans = 1
    for i in range(r):
        ans *= n-i
        ans %= mod
    for i in range(1,r+1):
        ans *= pow(i,-1,mod)
        ans %= mod
    return ans

def solve():
    n, a, b = map(int, input().split())
    mod = 10**9+7
    ans = pow(2,n,mod)-comb_mod(n,a)-comb_mod(n,b)-1
    ans %= mod
    return ans
print(solve())

Submission status: Runtime Error

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math

#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
  return int(readline())
n,a,b = readInts()
ans = (1 << n)%mod


MAXN = n+10
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % mod
    inv[i] = -inv[mod%i] * (mod // i) % mod
    finv[i] = finv[i-1] * inv[i] % mod

def ncr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
print((ans - 1 - ncr(n,a) - ncr(n,b))%mod)

Submission status: Runtime Error

Solution code:
def main():
    n, a, b = map(int, input().split())
    mod = 10 ** 9 + 7 #素数
    
    def modpow(x, n, mod):
        res = 1
        while n:
            if n % 2:
                res *= x % mod
            x *= x % mod
            n >>= 1
        return res
    
    def cmb(n, r):
        # 分子(n*(n-1)*...*(n-r+1))
        nume = 1
        for i in range(n-r+1, n+1):
            nume = nume * i % mod
        # 分母（1*2*...*r）
        deno = 1
        for j in range(1, r+1):
            deno = deno * j % mod
        d = modpow(deno, mod-2, mod)
        return nume * d
    
    all_cmb = pow(2, n, mod) -　1
    bad_a = cmb(n, a)
    bad_b = cmb(n, b)    
    print((all_cmb-bad_a-bad_b) % mod)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, a, b = map(int, input().split())
mod = 10**9+7
 
def cmb2(n, r, mod):
    res = 1
    temp = 1
    for k in range(1, r+1):
        res *= (n-k+1)
        temp *= k
        res %= mod
        temp %= mod
    res *= pow(temp,(mod-2),mod)
    res %= mod
    return res

def power(a, n, mod):
  	bi=str(format(n,"b")) #2進数
  	res=1
  	for i in range(len(bi)):
    	res=(res*res) %mod
    	if bi[i]=="1":
      		res=(res*a) %mod
  	return res

ans = power(2, n, mod) - cmb2(n, a, mod) - cmb2(n, b, mod) -1
ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from functools import reduce
from operator import mul
from typing import Callable, ClassVar, Sequence, Type, TypeVar


T = TypeVar('T', bound='ModIntBase')


class ModIntBase:
    value: int
    mod: ClassVar[int]
    fac: ClassVar[Sequence[int]] = ()
    inv: ClassVar[Sequence[int]] = ()
    finv: ClassVar[Sequence[int]] = ()

    def __init__(self, value: int) -> None:
        self.value = value % self.mod

    def __hash__(self) -> int:
        return hash((self.value, self.mod))

    def __eq__(self, other) -> bool:
        if isinstance(other, self.__class__):
            return self.value == other.value
        else:
            return NotImplemented

    def __ne__(self, other) -> bool:
        if isinstance(other, self.__class__):
            return self.value != other.value
        else:
            return NotImplemented

    # TODO: Add type hints
    def __add__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__((self.value + other.value) % self.mod)
        else:
            return NotImplemented

    def __sub__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__((self.value - other.value) % self.mod)
        else:
            return NotImplemented

    def __mul__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__(self.value * other.value % self.mod)
        else:
            return NotImplemented

    def __truediv__(self, other):
        if isinstance(other, self.__class__):
            a = other.value
            b = self.mod
            u = 1
            v = 0
            while b:
                t = a // b
                a, b = b, a - t * b
                u, v = v, u - t * v
            return self.__class__(self.value * u % self.mod)
        else:
            return NotImplemented

    def __pow__(self, other):
        if isinstance(other, self.__class__):
            v = 1
            a = self.value
            b = other.value
            mod = self.mod
            while b > 0:
                if b & 1:
                    v = v * a % mod
                a = a * a % mod
                b >>= 1
            return self.__class__(v)
        else:
            return NotImplemented

    @classmethod
    def comb(cls, n: int, k: int):
        if n < k:
            return cls(0)
        if n < 0 or k < 0:
            return cls(0)

        if n < len(cls.fac):
            return cls(cls.fac[n] * (cls.finv[k] * cls.finv[n - k] % cls.mod) % cls.mod)
        else:
            k = min(k, n - k)
            a = reduce(mul, map(cls, range(n - k + 1, n + 1)))
            b = reduce(mul, map(cls, range(1, k + 1)))
            return a / b

    def __repr__(self) -> str:
        return f'{self.__class__.__name__}({self.value!r})'

    def __str__(self) -> str:
        return str(self.value)


class ModInt(ModIntBase):
    mod = 1000000007  # 10 ** 9 + 7



def resolve(in_):
    N, A, B = map(int, in_.readline().split())
    
    c = ModInt(2) ** ModInt(N) - ModInt(1)
    a = ModInt.comb(N, A)
    b = ModInt.comb(N, B)
    
    return c - a - b


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
mod = 10**9+7
n,a,b = map(int,input().split())
frac = [1]*(n+1)
finv = [1]*(n+1)
def combination(n, a):
    # nCk = n! / k! (n-k)! のうち、 n!/(n-k)! を計算する
    res = 1
    div = 1
    for i in range(a):
        res *= n-i
        res %= mod
        div *= a - i
        div %= mod
    res = (res * pow(div, mod-2, mod)) % mod
    return res
 
print((pow(2,n,mod)-1-combination(n,a)-combination(n,b))%mod)

Submission status: Runtime Error

Solution code:
def com(n,k):
    bunshi = 1
    bunbo = 1
    for i in range(k):
        bunshi *= (n - i)
        bunbo *= (i + 1)
    while bunshi%10 == 0 and bunbo%10 == 0:
        bunshi = bunshi//10
        bunbo = bunbo//10
    return int(bunshi/bunbo)%(10**9 + 7)

n,a,b = map(int,input().split())
ans = 0
for i in range(1,n+1):
    if i != a and i != b:
        ans += com(n,i)
print(ans%(10**9 + 7))

Submission status: Runtime Error

Solution code:
from functools import lru_cache
from itertools import combinations
from math import factorial

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

@lru_cache
def count(num):
  return factorial(n) // factorial(n-num)

cnt = 0
for num in range(1,n+1):
  if num not in [a, b]:
  	cnt += count(min(num, n-num))
    
print(cnt)

Submission status: Runtime Error

Solution code:
mod = pow(10, 9) + 7

class Combination:
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod

    def calc(self, n, k):  # nCk
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod

n, a, b = map(int, input().split())
C = Combination(n)
p, q = C.calc(n, a), C.calc(n, b)

ans = pow(2, n, mod) - p - q - 1
print(ans)