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:
n,a,b=map(int,input().split())
mod = 10**9+7 #998244353 # 変える
MOD = 10**9+7 #素数 変える場所 
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

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

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

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

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

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

    __radd__ = __add__

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

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

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

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
ans=power_func(2,n,mod)
c1=ModInt(1)
for i in range(n,n-a,-1):
    c1*=ModInt(i)
for i in range(1,a+1):
    c1/=ModInt(i)
c2=ModInt(1)
for i in range(n,n-b,-1):
    c2*=ModInt(i)
for i in range(1,b+1):
    c2/=ModInt(i)
print(ModInt(ans)-c1-c2-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

# 逆元comb
def comb(n, k):
    k = min(n-k,k)
    ans = 1
    for i in range(1, k + 1):
        ans *= (n + 1 - i) * pow(i,MOD-2,MOD)
        ans %= MOD
    return ans

def solve(n: int, a: int, b: int):
    comb_sum = pow(2,n,MOD)
    aa = comb(n,a)
    bb = comb(n,b)

    print((comb_sum-1-aa-bb)%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = int(next(tokens))  # type: int
    b = int(next(tokens))  # type: int
    solve(n, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))
MOD=10 ** 9 + 7
n, a, b = MI()

ans = (pow(2, n, MOD) - 1) % MOD
def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod
ans -= combination(n, a)
ans -= combination(n, b)
print(ans % MOD)

Submission status: Accepted

Solution code:
p=pow(10,9)+7
def ncr(n, r, p): 
    # initialize numerator 
    # and denominator 
    num = den = 1 
    for i in range(r): 
        num = (num * (n - i)) % p 
        den = (den * (i + 1)) % p 
    return (num * pow(den,  
            p - 2, p)) % p
n,a,b=list(map(int, input().split()))
x=(pow(2,n,p)-1-ncr(n,a,p)-ncr(n,b,p))
print(x%p)

Submission status: Accepted

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

def cmb(m, n):
    if m - n < n:
        n = m - n
    if n == 0:
        return 1
    if n == 1:
        return m
    
    numerator = [m - n + k + 1 for k in range(n)]
    denominator = [k + 1 for k in range(n)]

    for p in range(2, n+1):
        pivot = denominator[p-1]
        if pivot > 1:
            offset = (m-n) % p
            for k in range(p-1, n, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    
    result = 1
    for k in range(n):
        if numerator[k] > 1:
            result *= int(numerator[k])
            
            # mod(10**9+7)
            result = result % (10**9+7)

    return result

a_value = cmb(n,a)
b_value = cmb(n,b)

ans = (2**n - a_value - b_value -1 ) % (10**9 + 7)
print(ans)

Submission status: Accepted

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

n, a, b = [int(x) for x in input().split()]

def nCk(n, k, mod=10 ** 9 + 7):
    if n < k:
        return 0
    k = min(k, n - k)
    numer = 1
    for x in range(n - k + 1, n + 1):
        numer = (numer * x) % mod
    denom = 1
    for x in range(1, k + 1):
        denom = (denom * x) % mod
    return numer * pow(denom, mod - 2, mod) % mod

ans = 0
total = 0
total = 2 ** n - 1
total %= 7 + 10 ** 9

total -= nCk(n, a) + nCk(n, b)
total %= 7 + 10 ** 9

print(total)

Submission status: Accepted

Solution code:
mod = 1000000007

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

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

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = 10**9+7

def factorial_mod(x, y, mod):
    factorial = 1
    for i in range(x,y+1):
        factorial *= i
        factorial %= mod
    return factorial


#conbinationを何回も求める場合はfactorial_k,nkをあらかじめ計算し, リストに入れておけば良い
def n_C_k(n,k,mod):
    factorial_nk = factorial_mod(n-k+1, n, mod)
    factorial_k = factorial_mod(1,k,mod)
    conbi=factorial_nk*pow(factorial_k, mod-2, mod)
    return conbi%mod

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

Submission status: Accepted

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

mod = 10 ** 9 + 7

n = max(a, b)
nfac = [1]
fac = [1]
caf = [1]


def pow(n, p):
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod


for i in range(1, n + 1):
    nfac.append((nfac[i - 1] * (N + 1 - i)) % mod)
    fac.append((fac[i - 1] * i) % mod)
    caf.append(pow(fac[i], mod - 2))


def ncr(n, r):
    if n < r or r < 0:
        return 0
    return (nfac[r] * caf[r]) % mod


r1 = pow(2, N)
r2 = ncr(N, a)
r3 = ncr(N, b)
print((r1 - r2 - r3 - 1) % mod)

Submission status: Accepted

Solution code:
a, b, c = [int(i) for i in input().split()]

def ncr(n, r, p): 
    # initialize numerator 
    # and denominator 
    num = den = 1 
    for i in range(r): 
        num = (num * (n - i)) % p 
        den = (den * (i + 1)) % p 
    return (num * pow(den,  
            p - 2, p)) % p 

res = (pow(2, a, 10**9 + 7) - ncr(a, b, 10**9 + 7) - ncr(a, c, 10**9 + 7) - 1) %(10 **9 + 7) 
print(res)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

ans = pow(2, n, MOD) - 1

# invs[x]: xの逆元 (x:0～n)
def getInvs(n, MOD):
    invs = [1] * (n+1)
    for x in range(2, n+1):
        invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
    return invs

invs = getInvs(2*10**5, MOD)

def f(n, k):
    num = 1
    for i in range(n-k+1, n+1):
        num *= i
        num %= MOD
    for i in range(k+1):
        num *= invs[i]
        num %= MOD
    return num

numA = f(n, a)
numB = f(n, b)
#print('numA:', numA, '/ numB:', numB)

print((ans - numA - numB) % MOD)

Submission status: Accepted

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

mod = 10 ** 9 + 7

ret = pow(2, n, mod) - 1

def comb(n, r) :
  ret = 1
  for i in range(n - r + 1, n + 1) :
    ret *= i
    ret %= mod
  for i in range(1, r + 1) :
    ret *= pow(i, mod - 2, mod)
    ret %= mod
  return ret

ret -= comb(n, a)
ret -= comb(n, b)

print(ret % mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush
from random import randint
from collections import defaultdict
from itertools import accumulate
from fractions import gcd
from collections import defaultdict
import sys
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))
MOD = 10**9 + 7
N, A, B = inpl()

MOD = 10**9 + 7
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
 
size = 10**6
g1, g2, inverse = [0]*size, [0]*size, [0]*size
 
g1[:2] = [1, 1] # 元テーブル
g2[:2] = [1, 1] #逆元テーブル
inverse[:2] = [0, 1] #逆元テーブル計算用テーブル
 
for i in range(2, size):
    g1[i] =  ( g1[i-1] * i ) % MOD 
    inverse[i] = (-inverse[MOD % i] * (MOD//i) ) % MOD 
    g2[i] =  (g2[i-1] * inverse[i]) % MOD

ans = pow(2, N, MOD) - 1

g = 1
for x in range(N, N-A, -1):
    g = (g*x)%MOD
ans = (ans - g * g2[A])%MOD

g = 1
for x in range(N, N-B, -1):
    g = (g*x)%MOD
ans = (ans - g * g2[B])%MOD

print(ans)

Submission status: Accepted

Solution code:
def modpow(a,n,m):
    res = 1
    while n>0:
        if n%2==1:
            res = (res * a) % m
        a = (a*a) % m
        n = n//2
    return res


def comb(n,k,mod):
    MAX = k+1
    fac = [0]*MAX
    finv = [0]*MAX
    inv = [0]*MAX

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

    res = 1
    for i in range(n,n-k,-1):
        res *= i
        res %= mod
    res *= finv[k]
    return res%mod

MOD = 10**9 + 7
n,a,b = map(int, input().split())

res = modpow(2,n,MOD)
res = MOD + res - comb(n,a,MOD)
res = MOD + res - comb(n,b,MOD)
res = MOD + res - 1

print(res%MOD)

Submission status: Accepted

Solution code:
MOD=10**9+7
n,a,b=map(int,input().split())
def modpow(a, p, mod=MOD):
    # return a**p (mod MOD) O(log p)
    if p==0: return 1
    if p%2==0:
        half = modpow(a, p//2, mod)
        return half*half % mod
    else:
        return a * modpow(a, p-1, mod) % mod

ret=modpow(2,n)
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

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

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

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

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

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

    __radd__ = __add__

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

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
def comb(x,n):
    divd=1
    for i in range(n):
        divd*=ModInt(x-i)
    for i in range(n):
        divd/=ModInt(i+1)
    return divd

print(ret-1-comb(n,a)-comb(n,b))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, a, b = map(int, input().split())
mod = 10 ** 9 + 7
res = pow(2, N, mod) - 1
ta = 1 
for i in range(a):
  ta *= N - i
  ta %= mod
for i in range(a):
  ta *= pow(i + 1, mod - 2, mod)
  ta %= mod
tb = 1
for i in range(b):
  tb *= N - i
  tb %= mod
for i in range(b):
  tb *= pow(i + 1, mod - 2, mod)
  tb %= mod
print((res - ta - tb) % mod)

Submission status: Accepted

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def combination_mod(n, r, mod):
    if r > n:
        return 0  # このような通りの数は無いため便宜上こう定義する
    r = min(r, n - r)
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i) % mod
        rf = rf * (i + 1) % mod
    return nf * pow(rf, mod - 2, mod) % mod


# すべての通り(2^n-1)からnCa,nCbを引けば良い
MOD = 10**9 + 7
n, a, b = read_ints()
tmp = pow(2, n, MOD) - 1
ans = tmp - combination_mod(n, a, MOD) - combination_mod(n, b, MOD)
print(ans % MOD)

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
P = 10**9+7

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

print((pow(2, N, P) - 1 - C(N, A) - C(N, B)) % P)

Submission status: Accepted

Solution code:
def prepare(n, MOD):
    # n! の計算
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs


def ncr(n, r, invs, MOD):
    ret = invs[r]
    for i in range(n, n - r, -1):
        ret = ret * i % MOD
    return ret


n, a, b = list(map(int, input().split()))
MOD = 10 ** 9 + 7
fn, invs = prepare(max(a, b), MOD)
ans = pow(2, n, MOD)
ans = (ans - ncr(n, a, invs, MOD) - ncr(n, b, invs, MOD) - 1) % MOD
print(ans)

Submission status: Accepted

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

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

def p_f(a,n,p):
    bi=str(format(n,"b"))
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
          res=(res*a) %p
    return res


sm=p_f(2,n,10**9+7)-1
tmp1=comb(n,a)
tmp2=comb(n,b)

print((sm-tmp1-tmp2) % (10**9+7))

Submission status: Accepted

Solution code:
N,A,B = map(int,input().split())
MOD = 10**9+7

MAXN = B+5
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD

a = pow(2,N,MOD) - 1
def comb(n,r):
    ret = 1
    for i in range(r):
        ret *= n-i
        ret *= inv[i+1]
        ret %= MOD
    return ret

ans = a - comb(N,A) - comb(N,B)
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
N, A, B = list(map(int, input().split()))

MOD = 10 ** 9 + 7


def modInverse(a, p):
    # Fermat's little theorem, a**(p-1) = 1 mod p
    return pow(a, p - 2, p)


def nCr(n, r, p=MOD):
    # Modulo binomial coefficients. TODO: Can try to use lucas's instead?
    num = 1
    den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return num * modInverse(den, p) % p


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

Submission status: Accepted

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

M = 10**9+7

F = [0]*(2*10**5+1)
F[0] = 1
for i in range(1, 2*10**5+1):
  F[i] = F[i-1]*i%M

def C(x, y):
  ans = 1
  for i in range(y):
    ans = ans*(x-i)%M
  return ans*pow(F[y], M-2, M)%M

ans = pow(2, n, M)-1
ans -= C(n, a)
ans -= C(n, b)

print ans%M

Submission status: Accepted

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

mod = 10**9+7

m = 10**5 * 2 +10 
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

comba = 1
for i in range(n,n-a,-1):
    comba *= i
    comba %= mod
comba *= finv[a]
comba %= mod

combb = 1
for i in range(n,n-b,-1):
    combb *= i
    combb %= mod
combb *= finv[b]
combb %= mod

ans = pow(2,n,mod) - comba - combb - 1
ans %= mod
print(ans)

Submission status: Accepted

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

n, a, b = map(int, readline().split())
P = 10**9 + 7

def mod_prod(a,b):
    return a * b % P

def mod_fact(a):
    ret = 1
    for i in range(a):
        ret = ret * (i + 1) % P
    return ret

def mod_pow(a, n):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % P
        a = a * a % P
        n = n // 2
    return ret

def mod_div(a, b):
    b_inv = mod_pow(b, P - 2)
    return a * b_inv % P

def mod_comb(a,b):
    ret = 1
    b = min(b, a - b)
    for i in range(b):
        ret *= a - i
        ret %= P
    ret = mod_div(ret, mod_fact(b))
    return ret


ans = mod_pow(2, n) - 1 - mod_comb(n, a) - mod_comb(n, b)
ans %= P
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


#solve
def solve():
    N, a, b = LI()
    ans = pow(2, N, mod) - 1
    dp = [0] * (max(a, b) + 1)
    dp[0] = 1
    for i in range(max(a, b)):
        dp[i + 1] = (dp[i] * (N - i)) * pow(i + 1, mod - 2, mod)
        dp[i + 1] %= mod
    print((ans-dp[a]-dp[b]) % mod)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
INF = 10 ** 20
MOD = 10**9 + 7
def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret

def main():
    n,a,b = getList()
    ans = pow(2, n, MOD) - 1
    ans %= MOD
    # print(ans)
    ca = combmod(n,a)
    cb = combmod(n,b)
    ans += MOD
    ans -= (ca+cb)
    ans %= MOD

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MAX = 2*10**5+100
fact = [0]*MAX
inv = [0]*MAX
finv = [0]*MAX
 
def C_init():
    fact[0] = 1
    fact[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    
    for i in range(2, MAX):
        fact[i] = fact[i-1]*i%MOD
        inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
        finv[i] = finv[i-1]*inv[i]%MOD

n, a, b = map(int, input().split())
MOD = 10**9+7
nCa = 1

for i in range(n-a+1, n+1):
    nCa *= i
    nCa %= MOD

nCb = 1

for i in range(n-b+1, n+1):
    nCb *= i
    nCb %= MOD

C_init()

for i in range(1, a+1):
    nCa *= inv[i]
    nCa %= MOD

for i in range(1, b+1):
    nCb *= inv[i]
    nCb %= MOD

ans = pow(2, n, MOD)-nCa-nCb-1
ans %= MOD

print(ans)

Submission status: Accepted

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


mod = 10**9+7 #出力の制限
n = max(a, b)
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 )

A = 1
for i in range(a):
    A *= (N-i)
    A %= mod
B = 1
for i in range(b):
    B *= (N-i)
    B %= mod

ans = pow(2, N, mod) - ((A*g2[a])%mod) - ((B*g2[b])%mod) - 1
print(ans%mod)

Submission status: Accepted

Solution code:
Q = 10**9+7

def getInv(N):
    inv = [0] * (N + 1)
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q % i]) % Q
    return inv

def main():

    n, a, b = map( int, input().split())
    Inv = getInv(2*10**5)
    def cmb(n,r):
        ret = 1
        for i in range(r):
            ret *= n-i
            ret %= Q
            ret *= Inv[i+1]
            ret %= Q
        return ret
    print( (pow(2,n,Q) - cmb(n,a) - cmb(n,b)-1)%Q)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
mod=10**9+7
ans=pow(2,n,mod)-1

def mod_cmb(n, r, mod=10 ** 9 + 7):
	assert n >= r >= 0

	def ex_euclid(x, y):
		a, b = 1, 0
		while y != 0:
			a, b = b, (a - x // y * b)
			x, y = y, x % y
		return a

	p = q = 1
	for i in range(n - r + 1, n + 1):
		p *= i
		p %= mod
	for i in range(2, r + 1):
		q *= i
		q %= mod
	p *= ex_euclid(q, mod)
	p %= mod
	return p

ans+=mod*2
ans-=mod_cmb(n,a)+mod_cmb(n,b)
print(ans%mod)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = 10**9+7
ca = 1
cb = 1
aa = 1
bb = 1
for i in range(1, a+1):
    aa*=i
    aa%=mod
for i in range(1, b+1):
    bb*=i
    bb%=mod
for i in range(n-a+1, n+1):
    ca*=i
    ca%=mod
for i in range(n-b+1, n+1):
    cb*=i
    cb%=mod
ca*=pow(aa, mod-2, mod)
ca%=mod
cb*=pow(bb, mod-2, mod)
cb%=mod
ans = (pow(2, n, mod)-1-ca-cb)%mod
print(ans)

Submission status: Accepted

Solution code:
n,a,b=[int(k) for k in input().strip().split(" ")]
mod=10**9+7
tp=pow(2,n,mod)-1
tpa=1
tpb=1
while a:
    a-=1
    tpa*=(n-a)*pow(a+1,mod-2,mod)
    tpa%=mod
while b:
    b-=1
    tpb*=(n-b)*pow(b+1,mod-2,mod)
    tpb%=mod

res = (tp - tpa - tpb)%mod
print(res)

Submission status: Accepted

Solution code:

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret

def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max,mod=DIV):
    fac,finv,inv = [0]*max, [0]*max, [0]*max
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod -inv[mod%i] * (mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod
    class CONV:
        def __init__(self):
            pass
        def ncr(self,n,k):
            if(n<k):
                return 0
            if(n<0 or k<0 ):
                return 0
            return fac[n]*(finv[k]*finv[n-k]%mod)%mod
    return CONV()


def main():
    n,a,b = isRaw()
    ans = pow(2,n,DIV)-1
    ans = (ans - ncr(n,a)+DIV)%DIV
    ans = (ans -ncr(n,b)+DIV)%DIV
    return ans
    


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
mod=10**9+7
n,a,b=map(int,input().split())
ans=pow(2,n,mod)-1

def comb(n,mm):
  m=min(mm,n-mm)
  ans=1
  for i in range(m):
    ans*=n-i
    ans%=mod
  for i in range(m):
    ans*=pow(i+1,mod-2,mod)
    ans%=mod
  return ans

ans=((ans+(mod-comb(n,a)))%mod)+(mod-comb(n,b))
print(ans%mod)

Submission status: Accepted

Solution code:
n,a,b  = map(int,input().split( ))
mod = 10**9+7
ans = pow(2,n,mod)
def chs(t,s):
    res = 1
    for i in range(t,t-s,-1):
        res *= i
        res %=mod
    for i in range(1,s+1):
        rev = pow(i,mod-2,mod)
        res *= rev
        res %=mod
    return res
ans -= chs(n,a)
ans -= chs(n,b)
ans -= 1
ans %=mod
print(ans)

Submission status: Accepted

Solution code:
mo = 10 ** 9 + 7
n, a, b = map(int, input().split())
u = (pow(2, n, mo) - 1 + mo) % mo
def rev(u):
    return pow(u, mo - 2, mo)
def C(p, q):
    ans = 1
    for i in range(q):
        ans = ans * (p - i) % mo
    for i in range(q):
        ans = ans * rev(i + 1) % mo
    return (ans + mo) % mo
u = (u - C(n, a) - C(n, b) + mo * 2) % mo
print(u)

Submission status: Accepted

Solution code:

n, a, b = map(int,input().split())
mod = 10**9 + 7

mod = 10**9 + 7
l = 3*10**5 + 3

M = [1]  # i!のmod
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  # x**y の mod を返す関数
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  # x の mod での逆元を返す関数
    return pow(x, mod-2, mod)

# print(inv(8,13))

MI = [0] * (l-1) +[inv(M[l-1], mod)]  # i!の逆元
for i in range(l-2, -1, -1):
    MI[i] = MI[i+1] * (i+1) % mod

def C(x, y):  # コンビネーション
    if y < 0 or y > x:
        return 0
    ans = M[x]
    ans = (ans * MI[y]) % mod
    return (ans * MI[x-y]) % mod

ans = pow(2, n, mod)
ans -= 1
m1 = 1
for i in range(n, n-a+1-1, -1):
    m1 = (m1*i) % mod
m1 = (m1 * MI[a]) % mod
m2 = 1
for i in range(n, n-b+1-1, -1):
    m2 = (m2*i) % mod
m2 = (m2 * MI[b]) % mod
ans = (ans-m1) % mod
ans = (ans-m2) % mod
# ans -= 1
print(ans)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = [1]
    r = 1
    for inv in mod_invs(max, mod)[1:]:
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


finvs = factorial_invs(2 * 10 ** 5 + 100, MOD)


def ncr(n, r):
    ret = 1
    for _ in range(r):
        ret *= n
        ret %= MOD
        n -= 1
    return ret * finvs[r] % MOD


N, A, B = list(map(int, sys.stdin.buffer.readline().split()))

comb = Combination(2 * 10 ** 5 + 100, MOD)
ans = pow(2, N, MOD) - 1
ans -= ncr(N, A)
ans -= ncr(N, B)
print(ans % MOD)

Submission status: Accepted

Solution code:
mod = 10**9+7
fact = [1]*(10**6+1)
for i in range(10**6):
    fact[i+1] = (i+1)*fact[i]%mod

n,a,b = map(int,input().split())
ans = pow(2,n,mod)-1
ca = 1
for k in range(a):
    ca *= n-k
    ca %= mod
ca *= pow(fact[a],mod-2,mod)
cb = 1
for k in range(b):
    cb *= n-k
    cb %= mod
cb *= pow(fact[b],mod-2,mod)

ans -= ca+cb
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def comb(n, k):
    t = 1
    for i in range(n - k + 1, n + 1):
        t *= i
        t %= MOD
    a = 1
    for i in range(1, k + 1):
        a *= i
        a %= MOD
    return t * pow(a, MOD - 2, MOD) % MOD


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

def single_mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    if r > n - r:
        r = n - r
    ret = 1
    for i in range(r):
        ret *= n - i
        ret *= pow(i+1, MOD-2, MOD)
        ret %= MOD
    return ret

n, a, b = [int(item) for item in input().split()]
total = pow(2, n, MOD) - 1
pata = single_mod_nCr(n, a)
patb = single_mod_nCr(n, b)
ans = ((total - pata - patb) % MOD + MOD) % MOD
print(ans)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
mod=10**9+7


def Combi2(a,b):# aは大きいが、bは小さいとき
    if b>a:
        return 0
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)*pow(min(b,a-b)-i,mod-2,mod)%mod

    return ANS%mod

ANS=pow(2,n,mod)-1
ANS-=Combi2(n,a)
ANS-=Combi2(n,b)
print(ANS%mod)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
m=10**9+7
def f(x,y):
    c=1
    for i in range(1,y+1):c=(c*(x-i+1)*pow(i,m-2,m))%m
    return c
print((pow(2,n,m)-1-f(n,a)-f(n,b))%m)