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 com(N,K,mod):
    n=N
    k=K
    X=1  #分子
    Y=1  #分母
    for _ in range(K):
        X*=n
        X%=mod
        n-=1
    for _ in range(K):
        Y*=k
        Y%=mod
        k-=1
    Y=pow(Y,mod-2,mod)  #Y**(mod-2) mod(mod)
    return X*Y%mod  #nCk mod(mod)

def main():
    N,a,b=map(int,input().split())
    mod=1000000007
    t=(pow(2,N,mod)-1-com(N,a,mod)-com(N,b,mod))%mod
    print(t)
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

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

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

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

ans = pow(2, n, mod)

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

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
mod = 10 ** 9 + 7
 
fact = [1]
num = [N]
for i in range(1, B + 1):
    fact.append(fact[-1] * (i + 1) % mod)
    num.append(num[-1] * (N - i) % mod)
 
 
def comb(x):
    res = num[x-1] * pow(fact[x-1], mod - 2, mod) % mod
    return res
 
 
ans = (pow(2, N, mod) - comb(A) - comb(B) -1 ) % mod

print(ans)

Submission status: Accepted

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

fact = [1]
num = [N]
for i in range(1, B + 1):
    fact.append(fact[-1] * (i + 1) % mod)
    num.append(num[-1] * (N - i) % mod)


def comb(x):
    res = num[x-1] * pow(fact[x-1], mod - 2, mod) % mod
    return res


ans = (pow(2, N, mod) - comb(A) + mod) % mod
ans = (ans - comb(B) + mod) % mod
ans = (ans - 1 + mod) % mod
print(ans)

Submission status: Accepted

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

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

def comb(n,r):
    ret = 1
    for i in range(r):
        ret *= n-i
        ret *= inv[i+1]
        ret %= MOD
    return ret
ans = p-1 - comb(N,A) - comb(N,B)
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
ans=pow(2,n)-1
mod=10**9+7
def ncr(n,r,mod):
    cnt=1
    for i in range(n-r+1,n+1):
        cnt*=i
        cnt%=mod
    for i in range(1,r+1):
        cnt*=pow(i,mod-2,mod)
        cnt%=mod
    return cnt
comb1=ncr(n,a,mod)
comb2=ncr(n,b,mod)
ans=(ans-comb1-comb2)%mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def comb(n, k, MOD):
    if n < k or n < 0 or k < 0:
        return 0
    if k == 0:
        return 1
    iinv = [1] * (k + 1)
    ans = n
    for i in range(2, k + 1):
        iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
        ans *= (n + 1 - i) * iinv[i] % MOD
        ans %= MOD
    return ans
n, a, b = map(int, input().split())
print((pow(2,n,MOD)-1-comb(n,a,MOD)-comb(n,b,MOD)+MOD*10)%MOD)

Submission status: Accepted

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

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

P = 10**9+7

nCa = comb(n, a, P)
nCb = comb(n, b, P)

ans = (pow(2,n,P) -1 - nCa - nCb + 2*P)%P
print(ans)

Submission status: Accepted

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

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

P = 10**9+7

nCa = comb(n, a, P)
nCb = comb(n, b, P)

ans = (pow(2,n,P) -1 - nCa - nCb + 2*P)%P
print(ans)

Submission status: Accepted

Solution code:
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

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

Submission status: Accepted

Solution code:
import math

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def combination(n,r,mod):
    r = min(r,n-r)

    res = 1
    for i in range(r):
        res = res * (n-i) * modinv(i+1,mod) % mod
    
    return res

mod = 10**9+7

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

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

ans -= combination(n,a,mod)
ans -= combination(n,b,mod)

print(ans % mod)

Submission status: Accepted

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

MOD = 10 ** 9 + 7


def comb(n, r):
    if n - r < r:
        r = n - r

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


res = pow(2, N, MOD)

res -= comb(N, A) + comb(N, B)
res %= MOD
print(res - 1)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = 1000000007
def inv(y, mod):
    return pow(y, mod - 2, mod)

def comb(n, a, mod):
    x = 1
    y = 1
    for i in range(a):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    return (x * inv(y, mod)) % mod
    
print((pow(2, n, mod) - 1 - comb(n, a, mod) - comb(n, b, mod)) % mod)

Submission status: Accepted

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

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])%mod
            result%=mod

    return result%mod

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

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

    return K * x%mod

ans=pow_k(2,n)-1
ans=ans- cmb(n, min(a,n-a))-cmb(n, min(b,n-b))
print(ans%mod)

Submission status: Accepted

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
from operator import mul
from functools import reduce
# a, b = [int(v) for v in input().split()]


def main():

    def modcmb(n, r, mod):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        if r == 0:
            return 1
        over = 1
        under = 1
#        for i in range(n, n-r, -1):
#            over = over * i % mod
#        for i in range(1, r+1):
#            under = under * i % mod

        over = reduce(lambda v1, v2: (v1 * v2) % mod, range(n, n-r, -1))
        under = reduce(lambda v1, v2: (v1 * v2) % mod, range(1, r+1))
        return (over * pow(under, mod - 2, mod)) % mod

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

    count = pow(2, n, mod) - 1
    count -= modcmb(n, a, mod)
    count -= modcmb(n, b, mod)

    while count < 0:
        count += mod
    print(count % mod)


main()

Submission status: Accepted

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
from operator import mul
from functools import reduce
# a, b = [int(v) for v in input().split()]


def main():

    def modcmb(n, r, mod):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        over = 1
        under = 1
        for i in range(n, n-r, -1):
            over = over * i % mod
        for i in range(1, r+1):
            under = under * i % mod

#        over = reduce(lambda v1, v2: (v1 * v2) % mod, range(n, n-r, -1))
#        under = reduce(lambda v1, v2: (v1 * v2) % mod, range(1, r+1))
        return (over * pow(under, mod - 2, mod)) % mod

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

    count = pow(2, n, mod) - 1
    count -= modcmb(n, a, mod)
    count -= modcmb(n, b, mod)

    while count < 0:
        count += mod
    print(count % mod)


main()

Submission status: Accepted

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
from operator import mul
from functools import reduce
# a, b = [int(v) for v in input().split()]


def main():

    def modcmb(n, r, mod):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        over = 1
        under = 1
        for i in range(r):
            over = over * (n - i) % mod
            under = under * (i + 1) % mod

#        over = reduce(lambda v1, v2: (v1 * v2) % mod, range(n, n-r, -1))
#        under = reduce(lambda v1, v2: (v1 * v2) % mod, range(1, r+1))
        return (over * pow(under, mod - 2, mod)) % mod

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

    count = pow(2, n, mod) - 1
    count -= modcmb(n, a, mod)
    count -= modcmb(n, b, mod)

    while count < 0:
        count += mod
    print(count % mod)


main()

Submission status: Accepted

Solution code:
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
n,a,b = map(int,input().split())
mod=10**9+7
print((pow(2,n,mod)-1-cmb(n,a,mod)-cmb(n,b,mod))%mod)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


m=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np


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

def main():
	n,a,b=map(int,input().split())
	ans=pow(2,n,m)-1-comb(n,a,m)-comb(n,b,m)
	ans%=m
	print(ans)
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7


def mod_pow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        half_p = p // 2
        half = mod_pow(a, half_p)
        return half * half % mod
    else:
        return a * mod_pow(a, p - 1) % mod


def calc_comb(a, b):
    if b > a - b:
        return calc_comb(a, a - b)

    ans_mul = 1
    ans_div = 1
    for i in range(b):
        ans_mul *= (a - i)
        ans_div *= (i + 1)
        ans_mul %= mod
        ans_div %= mod

    ans = ans_mul * mod_pow(ans_div, mod - 2) % mod
    return ans


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

Submission status: Accepted

Solution code:
def ncr(n,r,z):
  x=1
  y=1
  for i in range(min(r,n-r)):
    x=(x*(n-i))%z
    y=(y*(i+1))%z
  y=pow(y,z-2,z)
  return x*y%z

n,a,b=map(int,input().split())
mod=10**9+7
A=ncr(n,a,mod)
B=ncr(n,b,mod)
ans=pow(2,n,mod)-1-A-B
while ans<0:
  ans+=mod
print(ans)

Submission status: Accepted

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

total = (pow(2, n, p) - 1) % p

def cmb(n, r):
    x = 1
    y = 1
    for i in range(r):
        x = (x * (n - i)) % p
        y = (y * (r - i)) % p
    ret = x * pow(y, p - 2, p) % p
    return ret

total = (pow(2, n, p) - 1 - cmb(n, a) - cmb(n, b)) % p
print(total)

Submission status: Accepted

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


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


def comb(n, r, mod):
    numerator = denominator = 1
    for i in range(r):
        numerator = numerator * (n - i) % mod
        denominator = denominator * (i + 1) % mod
    return numerator * inv(denominator, mod) % mod


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

Submission status: Accepted

Solution code:
N,a,b=map(int,input().split())
MOD=10**9+7
def comb(n,k):
  tmp=1
  for i in range(n-k+1,n+1):
    tmp*=i
    tmp%=MOD
  for i in range(1,k+1):
    tmp*=pow(i,MOD-2,MOD)
    tmp%=MOD
  return tmp
ans = pow(2,N,MOD) - 1 - comb(N,a) - comb(N,b)
print(ans%MOD)

Submission status: Accepted

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

from functools import reduce
mod = 10**9+7

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


def nCk(n, k):
    numer = reduce(lambda x, y: (x * y) % mod, range(n, n - k, -1))
    denom = reduce(lambda x, y: (x * y) % mod, range(1, k + 1))
    return numer * pow(denom, mod - 2, mod) % mod


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

Submission status: Accepted

Solution code:
from math import factorial

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


def sq(a, b, mod):
    if b == 0:
        return 1
    elif b % 2 == 0:
        return sq(a, b // 2, mod)**2 % mod
    else:
        return sq(a, b - 1, mod) * a % mod


def nCk(n, k, mod=10 ** 9 + 7):
    x = max(k, n - k)
    y = min(k, n - k)
    kkai = 1
    for i in range(2, y + 1):
        kkai = (kkai * i) % mod
    nkkai = 1
    for i in range(x + 1, n + 1):
        nkkai = (nkkai * i) % mod
    answer = sq(kkai, mod - 2, mod) * nkkai % mod
    return answer


mod = 10 ** 9 + 7

s = pow(2, n, mod) - 1 - nCk(n, a, mod) - nCk(n, b, mod)

s = (s + mod) % mod

print(s)

Submission status: Accepted

Solution code:
mod = 10**9+7
N, A, B = [int(i) for i in input().split()]


def ncr(n, r):
    r = min(r, n-r)
    res = 1
    m = n
    for _ in range(r):
        res *= m
        res %= mod
        m -= 1
    m = r
    for _ in range(r):
        res *= pow(m, mod-2, mod)
        res %= mod
        m -= 1
    return res


print((pow(2, N, mod)-1-ncr(N, A)-ncr(N, B)) % mod)

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
mod = 10**9+7
ans = pow(2,n,mod)-1
inv_t = [0]+[1]
for i in range(2,b+1):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]
nCk = [1]*(b+1)
for i in range(1,b+1):
  nCk[i]=(((nCk[i-1]*(n-i+1))%mod)*inv_t[i])%mod
ans -= nCk[a]+nCk[b]
print(ans%mod)

Submission status: Accepted

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


def power(x, y, z):
    if x == 1 or y == 0:
        return 1
    a = power(x, y // 2, z)
    a = (a * a) % z
    if y % 2 == 1:
        a = (a * x) % z
    return a


def choose(n, r, z):
    x = 1
    y = 1

    for i in range(min(r, n - r)):
        x = (x * (n - i)) % z
        y = (y * (i + 1)) % z

    y = power(y, z - 2, z)
    return (x * y) % z


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

print(ans)

Submission status: Accepted

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


def power(x, y, z):
    if y == 0:
        return 1
    a = power(x, y // 2, z)
    a = (a * a) % z
    if y % 2 == 1:
        a = (a * x) % z
    return a


def choose(n, r, z):
    x = 1
    y = 1

    for i in range(min(r, n - r)):
        x = (x * (n - i)) % z
        y = (y * (i + 1)) % z

    y = power(y, z - 2, z)
    return (x * y) % z


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

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

class ModInt:
    def __init__(self, x):
        if isinstance(x, ModInt):
            self.x = x.x
        else:
            self.x = x % MOD
    
    # str関数を使用したとき
    def __str__(self):
        return str(self.x)
    
    def __int__(self):
        return self.x
    
    __index__ = __int__
    
    # print関数を使用したとき
    __repr__ = __str__

    ## 四則演算
    def __add__(self, other):
        return ModInt(self.x + ModInt(other).x)
    
    def __sub__(self, other):
        return ModInt(self.x - ModInt(other).x)

    def __mul__(self, other):
        return ModInt(self.x * ModInt(other).x)
    
    # /
    def __truediv__(self, other):
        # a * a^(p - 2) ≡ 1 (mod p) 逆元から求める
        return ModInt(self.x * pow(ModInt(other).x, MOD - 2, MOD))

    # //
    def __floordiv__(self, other):
        return self.x // ModInt(other).x

    # 累乗
    def __pow__(self, other):
        return ModInt(pow(self.x, ModInt(other).x, MOD))

    ## 四則演算の順序
    __radd__ = __add__

    def __rsub__(self, other):
        return ModInt(other - self.x)
    
    __rmul__ = __mul__

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

    def __rfloordiv__(self, other):
        return ModInt(other // self.x)
    
    # 累乗の順序
    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))
    
    ## 不等号
    def __lt__(self, other):
        return self.x < ModInt(other).x
    
    def __gt__(self, other):
        return self.x > ModInt(other).x

    def __le__(self, other):
        return self.x <= ModInt(other).x
    
    def __ge__(self, other):
        return self.x >= ModInt(other).x
    
    def __eq__(self, other):
        return self.x == ModInt(other).x
    
    def __ne__(self, other):
        return self.x != ModInt(other).x

def comb(n, r):
    res = ModInt(1)
    for i in range(n-r+1, n+1):
        res = res * i
    for i in range(2, r+1):
        res = res / i
    return res

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

ans = 2 ** n

ans = ans - comb(n, a)
ans = ans - comb(n, b)
ans = ans - 1

print(ans)

Submission status: Accepted

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

x = 1
y = 1
for i in range(1, a+1):
  x = x * (n-i+1) % mod
  y = (y * i) % mod
da = ((x % mod) * (pow(y, mod-2, mod) % mod)) % mod

x = 1
y = 1
for i in range(1, b+1):
  x = x * (n-i+1) % mod
  y = (y * i) % mod
db = ((x % mod) * (pow(y, mod-2, mod) % mod)) % mod

ans = pow(2,n,mod) - 1 - da - db
print(ans % mod)

Submission status: Accepted

Solution code:
from math import factorial

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

mod = 10**9+7

def comb(n,k,p):
  x = 1
  y = 1
  for i in range(k):
    x= (x *(n-i))%p
    y= (y* (k-i))%p
  yinv = pow(y,p-2,p)
  return (x*yinv)%p

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

Submission status: Accepted

Solution code:


from functools import *
import sys
sys.setrecursionlimit(100000)



def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())
mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def cmb2(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return int(result)

    return count


def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y
    
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
    
def combination(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 modpow(a, n, mod):
    res = 1
    while n > 0:
        #print(n)

        if n & 1:
            res = res*a % mod
        a = a*a % mod
            #n >>= 1
        n>>=1

    return res


n,a,b=acinput()




#print(combination(n,a))
c=combination(n,min(n,n-a))+combination(n,min(b,n-b))



print((modpow(2,n,mod)-c-1)%mod)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

def inverse(a, p):
    return pow(a, p-2, p)

def nCr(n, r, p = MOD):
    x, y = 1, 1
    for i in range(r):
        x = (x * (n - i)) % p
        y = (y * (i + 1)) % p
    return x * inverse(y, p) % p

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

print(((ans - nCr(n, a) - nCr(n, b)) % MOD))

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
mod=10**9+7
n_max=2*(10**5+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
FI[n_max-1]=pow(F[n_max-1],mod-2,mod)
for i in reversed(range(n_max-1)):
  FI[i]=(FI[i+1]*(i+1))%mod
ans=pow(2,n,mod)
c=1
for i in range(b):
  c=(c*(n-i))%mod
  if i==a-1:
    c1=c
c2=c
c1=(c1*FI[a])%mod
c2=(c2*FI[b])%mod
print((ans-c1-c2-1)%mod)

Submission status: Accepted

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

def main():
    mod = 10**9+7
    n,a,b=map(int,input().split())
    f=1
    fa=0
    for i in range(1,b+1):
        f=(f*(n-i+1)*pow(i,mod-2,mod))%mod
        if i==a:
            fa=f
    ans=(pow(2,n,mod)-fa-f-1)%mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

factorial = [1]
for i in range(1, N+1):
    factorial.append((factorial[i-1]*i)%mod)

p_list = [n%mod]
for i in range (1,N+1):
    p_list.append((p_list[i-1]*(n-i))%mod)
    
x = pow(2,n,mod)-1
ya = pow(factorial[a],10**9+5,mod)
yb = pow(factorial[b],10**9+5,mod) 

print ((x-p_list[a-1]*ya-p_list[b-1]*yb)%mod)

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


def comb(n, k):
    nCk = 1
    MOD = 10**9+7

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

    for i in range(1, k+1):
        nCk *= pow(i, MOD-2, MOD)
        nCk %= MOD
    return nCk


def main():
    mod = 10**9+7
    N, a, b = map(int, input().split())
    ans = pow(2, N, mod)-1 - comb(N, a) - comb(N, b)
    print(ans % mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()


def inv_mod(a, N):
    """
    Fermatの小定理より(Nが素数のときしか使えない)
    aの逆元 ax = 1 (mod N)を満たすx = a^(N-2) mod Nを返す。
    O(log N)
    """

    def bpm(x, y, N):
        """
         Bisection power method : 二分累乗法
         O(log y)でx^(y) mod N を求める。
        """
        ans = 1
        x %= MOD
        digit = int((math.log(y, 2) // 1 + 1))  # yの２進数表示の桁数
        for i in range(digit):
            if (y >> i) & 1 == 1:
                ans *= x
                ans %= MOD
            x **= 2
            x %= MOD
        return ans

    return bpm(a, N - 2, N)


def bpm(x, y, N):
    """
     Bisection power method : 二分累乗法
     O(log y)でx^(y) mod N を求める。
    """
    ans = 1
    x %= MOD
    digit = int((math.log(y, 2) // 1 + 1))  # yの２進数表示の桁数
    for i in range(digit):
        if (y >> i) & 1 == 1:
            ans *= x
            ans %= MOD
        x **= 2
        x %= MOD
    return ans


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

nCa = 1
nCb = 1

inv_list = [1]  # 0で割るというのは定義されないので無視。
for i in range(max(a, b)):
    inv_list.append(int(MOD - inv_list[(MOD % (i + 2)) - 1] * (MOD // (i + 2)) % MOD))

for i in range(a):
    nCa *= inv_list[i]
    nCa %= MOD
    nCa *= n - i
    nCa %= MOD

for i in range(b):
    nCb *= inv_list[i]
    nCb %= MOD
    nCb *= n - i
    nCb %= MOD

print((bpm(2, n, MOD) - 1 - nCa - nCb) % MOD)

Submission status: Accepted

Solution code:
from functools import reduce

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

# nCr の計算
def F(n,r):
    # 分子 n*(n-1)*(n-2)*...(n-r+1)
    numerator = reduce(lambda x,y: x * y % MOD, range(n,n-r,-1))
    # 分母 r!(rの階乗)
    denominator = reduce(lambda x,y: x * y % MOD, range(1,r+1))
    return numerator * pow(denominator, MOD - 2, MOD) % MOD

# 繰り返し二乗法
ans = pow(2,n,MOD)-1
ans -=F(n,a)
ans -=F(n,b)
ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
def mcomb(n, k):
    a = 1
    b = 1
    for i in range(k):
        a *= n - i
        a %= 1000000007
        b *= i + 1
        b %= 1000000007
    return a * pow(b, 1000000005, 1000000007) % 1000000007


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

result = pow(2, n, 1000000007) - 1
result -= mcomb(n, a)
result + 1000000007
result %= 1000000007
result -= mcomb(n, b)
result + 1000000007
result %= 1000000007
print(result)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import math

mod = 10**9+7

def pow_mod(a, b, mod):
    x = 1
    while b > 0:
        if b & 1:
            x = (x*a)%mod
        a = (a**2)%mod
        b //= 2
 
    return x

def modinv(a, mod):
    return pow_mod(a, mod-2, mod)

def comb(n,r,mod):
    combsum=1
    for i in range(n-r+1,n+1):
        combsum = (combsum * i)%mod

    for i in range(1,r+1):
        combsum = (combsum * inv[i])%mod

    return combsum

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

a=min([a,n-a])
b=min([b,n-b])

maxab=max([a,b])

inv=[modinv(i,mod) for i in range(0,maxab+2)]

def resolve():

    ptn = pow_mod(2,n,mod)
    ptn -= 1

    comba=comb(n,a,mod)
    combb=comb(n,b,mod)

    ptn = (ptn-comba-combb)%mod

    print(ptn)

    return 

resolve()

Submission status: Accepted

Solution code:
#python3
from math import factorial
MOD = int(1e9+7)
INF = int(1e9)

def comb(n, m, mod):
    comb_a = 1
    for i in range(m):  
        comb_a *= (n-i)
        comb_a %= mod
    comb_b = factorial(m)%mod
    comb_b = pow(comb_b, mod-2, mod)
    return (comb_a * comb_b) % mod
    
def main():
    n, a, b = map(int, input().split())
    print((pow(2, n, MOD)-1-comb(n, a, MOD)-comb(n, b, MOD))%MOD)
main()

Submission status: Accepted

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

mod = 10**9 + 7

import time
start = time.time()


# x ** a をmodで割った余りを、O(log(a))時間で求める。
def power(x, a):
	if a == 0:
		return 1
	elif a == 1:
		return x
	elif a % 2 == 0:
		return power(x, a//2) **2 % mod
	else:
		return power(x, a//2) **2 * x % mod

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
	return pow(x, mod-2, mod)

modinv_table = [-1] * (b+1)
for i in range(1, b+1):
    modinv_table[i] = modinv(i)

end = time.time()
# print("time: ", end - start)

def binomial_coefficients2(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans

# (2 ** n - 1) - nCa - nCb
ans = power(2, n) - 1

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


# print(binomial_coefficients2 (5, 2) % mod)

Submission status: Accepted

Solution code:
def comb(n, k):
    nCk = 1
    MOD = 10**9+7

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

    for i in range(1, k+1):
        nCk *= pow(i, MOD-2, MOD)
        nCk %= MOD
    return nCk


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

Submission status: Accepted

Solution code:
m=10**9+7
n,a,b=map(int,input().split())
s=r=1
for i in range(b):s+=r*(i==a);r=r*(n-i)*pow(i+1,m-2,m)%m
print((pow(2,n,m)-s-r)%m)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
read = sys.stdin.read
n,a,b = [int(i) for i in read().split()]

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

# 全部の場合から、aとbの場合を引き算する
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(ans%MOD)

Submission status: Accepted

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

mod = 10**9 + 7

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

all = pow(2,n,mod)-1
comb_a = comb(n,a,mod)
comb_b = comb(n,b,mod)
answer = (all -comb_a -comb_b) % mod

print(answer)

Submission status: Accepted

Solution code:
import numpy as np
n, a, b = map(int, input().split())
a, b = min(a, b), max(a, b)
MOD = 10**9 + 7
v = pow(2, n, MOD) - 1


def cumprod(arr, MOD):
    L = len(arr)
    Lsq = int(L**.5 + 1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n - 1]
        arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n - 1, -1]
        arr[n] %= MOD
    return arr.ravel()[:L]


def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64)
    x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64)
    x[0] = pow(int(fact[-1]), MOD - 2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv


# a / b = (a % N * pow(b, N - 2, N)) % N(mod=N)
fact, fact_inv = make_fact(2 * 10**5 + 1, MOD)
# print(fact)
a_fact = fact[a]
b_fact = fact[b]

n_fact = [n % MOD] * (b + 1)
for i in range(1, b + 1):
    n_fact[i] = (n_fact[i - 1] * (n - i)) % MOD
an_fact = n_fact[a - 1]
bn_fact = n_fact[b - 1]


def f(a, b, MOD):
    a, b = int(a), int(b)
    return (a % MOD * pow(b, MOD - 2, MOD)) % MOD


ca = f(an_fact, a_fact, MOD)
cb = f(bn_fact, b_fact, MOD)

print((v - ca - cb) % MOD)