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) .

Solution (Python):
import sys
from functools import reduce
from operator import mul


class ModIntMeta(type):
    def __new__(cls, name, bases, classdict):
        ret = super().__new__(cls, name, bases + (_ModIntMixIn,), classdict)
        max_ = ret._max = classdict.get('_max', 510000)
        mod = ret._mod = classdict.get('_mod', 10 ** 9 + 7)

        fac = ret._fac = [0] * max_
        finv = ret._finv = [0] * max_
        inv = ret._inv = [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
        
        return ret


class _ModIntMixIn:
    _max: int
    _mod: int

    def __init__(self, value):
        self._value = value % self._mod
    
    def __int__(self):
        return self._value

    def __hash__(self):
        return hash((self._value, self._mod))

    def __lt__(self, other):
        if isinstance(other, self.__class__):
            return self._value < other._value
        else:
            return NotImplemented

    def __le__(self, other):
        if isinstance(other, self.__class__):
            return self._value <= other._value
        else:
            return NotImplemented

    def __eq__(self, other):
        if isinstance(other, self.__class__):
            return self._value == other._value
        else:
            return NotImplemented

    def __ne__(self, other):
        if isinstance(other, self.__class__):
            return self._value != other._value
        else:
            return NotImplemented

    def __gt__(self, other):
        if isinstance(other, self.__class__):
            return self._value > other._value
        else:
            return NotImplemented

    def __ge__(self, other):
        if isinstance(other, self.__class__):
            return self._value >= other._value
        else:
            return NotImplemented

    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 0
        if n < 0 or k < 0:
            return 0

        if n < cls._max:
            return cls(cls._fac[n] * (cls._finv[k] * cls._finv[n - k] % cls._mod) % cls._mod)
        else:
            a = reduce(mul, map(ModInt, range(n - k + 1, n + 1)))
            b = reduce(mul, map(ModInt, range(1, k + 1)))
            return a / b

    def __repr__(self):
        return f'{self.__class__.__name__}({self._value!r})'

    def __str__(self):
        return f'{self._value}'


class ModInt(metaclass=ModIntMeta):
    _max = 2


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()

Solution (Python):
k = 2 *10**5
mod = 10**9+7

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

modinv_table = [-1]*(k+1)
for i in range(1,k+1):
    modinv_table[i] = pow(i,-1,mod)

def binomial_coefficients(n,k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i+1]
        ans %= mod
    return ans
print((pow(2,n,mod)-binomial_coefficients(n,a)-binomial_coefficients(n,b)-1)%mod)

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


def pow(x, n, MOD):
    res = 1
    while n:
        if n & 1:
            res *= x
            res %= MOD
        x *= x
        x %= MOD
        n >>= 1
    return res    


def fact(a, b, MOD):
    res = 1
    for i in range(a, b+1):
        res *= i
        res %= MOD
    return res


def combi(n, k, MOD):
    x = fact(n - k + 1, n, MOD)
    y = fact(1, k, MOD)
    return x * pow(y, MOD - 2, MOD) % MOD
    

def solve():
    ans = pow(2, n, MOD) - 1 - combi(n, a, MOD) - combi(n, b, MOD)
    print(ans % MOD)
    


if __name__ == "__main__":
    solve()

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


def pow(x, n, MOD):
    res = 1
    while n:
        if n & 1:
            res *= x
            res %= MOD
        x *= x
        x %= MOD
        n >>= 1
    return res    


def fact(a, b, MOD):
    res = 1
    for i in range(a, b+1):
        res *= i
        res %= MOD
    return res


def combi(n, k, MOD):
    x = fact(n - k + 1, n, MOD)
    y = fact(1, k, MOD)
    return x * pow(y, MOD - 2, MOD) % MOD
    

def solve():
    ans = pow(2, n, MOD) - 1 - combi(n, a, MOD) - combi(n, b, MOD)
    print(ans % MOD)
    


if __name__ == "__main__":
    solve()

Solution (Python):
n,a,b = map(int,input().split())
mod = 10**9 + 7
ans = pow(2,n,mod) - 1
fa = 1
fb = 1
for i in range(1, a+1):
    fa *= i
    fa %= mod
for i in range(1, b+1):
    fb *= i
    fb %= mod

fa = pow(fa, mod-2, mod)
fb = pow(fb, mod-2, mod)

for i in range(a):
    fa *= n - i
    fa %= mod
for i in range(b):
    fb *= n - i
    fb %= mod

print((ans - fa - fb) % mod)

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

Solution (Python):
def modpow(a, n, mod):
    if n == 0:
        return 1
    else:
        if n % 2 == 0:
            return (modpow((a * a)%mod, n//2, mod)) % mod
        else:
            return ((a%mod) * modpow(a, n-1, mod)) % mod


def modinv(a, mod):
    return modpow(a, mod-2, mod) % mod

def moddiv(a, b, mod):
    return ((a%mod) * modinv(b, mod)) % mod


def modcombination(n, k, mod):
    fact = [1 for _ in range(n+1)]
    inv = [1 for _ in range(n+1)]
    finv = [1 for _ in range(n+1)]

    for i in range(2, n+1):
        fact[i] = (fact[i-1] * i) % mod
        inv[i] = (-inv[mod % i] * (mod // i)) % mod
        finv[i] = (finv[i-1] * inv[i]) % mod
    return fact[n] * (finv[k] * finv[n-k] % mod) % mod


def modcombination_smallk(n, k, mod):
    result = 1
    for i in range(k):
        result = (((result * (n-i))%mod) * modinv(i+1, mod))%mod
    return result

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


total = modpow(2, n, mod)
tota = modcombination_smallk(n, a, mod)
totb = modcombination_smallk(n, b, mod) 
print((total-tota-totb-1)%mod)

Solution (Python):
n,a,b=map(int,input().split())
mod=10**9+7
sum=(pow(2,n,mod)-1)%mod
nume_a=1
deno_a=1
for i in range(n-a+1,n+1):
    nume_a=(nume_a*(i%mod))%mod
    deno_a=(deno_a*(i-(n-a+1)+1)%mod)%mod
ans_a=(nume_a*(pow(deno_a,mod-2,mod)))%mod
nume_b=1
deno_b=1
for i in range(n-b+1,n+1):
    nume_b=(nume_b*(i%mod))%mod
    deno_b=(deno_b*(i-(n-b+1)+1)%mod)%mod
ans_b=(nume_b*(pow(deno_b,mod-2,mod)))%mod
print((sum-ans_a-ans_b)%mod)

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

def modpow(x, n):
    ret = 1
    while n:
        if n & 1:
            ret = ret * x % MOD
        x = x * x % MOD
        n >>= 1
    return ret

@functools.lru_cache(maxsize=None)
def modinv(x):
    return modpow(x, MOD - 2)

def modcomb(n, r):
    ret = 1
    for i in range(n, n - r, -1):
        ret *= i
        ret %= MOD
    for i in range(r, 1, -1):
        ret *= modinv(i)
        ret %= MOD
    return ret

total = modpow(2, N) - 1
ans = total - (modcomb(N, A) + modcomb(N, B))
ans %= MOD
print(ans)

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

def modpow(x, n):
    ret = 1
    while n:
        if n & 1:
            ret = ret * x % MOD
        x = x * x % MOD
        n >>= 1
    return ret

@functools.lru_cache(maxsize=None)
def modinv(x):
    return modpow(x, MOD - 2)

def modcomb(n, r):
    ret = 1
    for i in range(n, n - r, -1):
        ret *= i
        ret %= MOD
    for i in range(r, 1, -1):
        ret *= modinv(i)
        ret %= MOD
    return ret

total = modpow(2, N) - 1
ans = total - (modcomb(N, A) + modcomb(N, B))
ans %= MOD
print(ans)

Solution (Python):
def solve():
    def combis(n, k, mod):
        from math import factorial
        numerator = 1
        denominator = 1
        for i in range(k):
            numerator = numerator * (n-i) % mod
            denominator = denominator * (i+1) % mod
        return numerator * pow(denominator, mod-2, mod) % mod

    n,a,b = [int(i) for i in input().split()]
    mod = 10**9 + 7
    ans = pow(2, n, mod) - 1 - combis(n, a, mod) - combis(n, b, mod)
    print(ans % mod)

if __name__ == "__main__":
    solve()

Solution (Python):
def inverse(a, mod):
    a %= mod
    p = mod
    x, y = 0, 1
    while a > 0:
        n = p // a
        p, a = a, p % a, 
        x, y = y, x - n * y
    return x % mod

def power(x, n, mod):
    ans = 1
    while n > 0:
        if n % 2 == 1:
            ans = ans * x % mod
        n //= 2
        x = x * x % mod
    return ans

n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
ans = power(2, n, mod)
nCa = 1
for i in range(a):
    nCa = nCa * inverse(i + 1, mod) % mod * (n - i) % mod
nCb = 1
for i in range(b):
    nCb = nCb * inverse(i + 1, mod) % mod * (n - i) % mod
ans = (ans - nCa - nCb - 1) % mod
print(ans)

Solution (Python):
mod = 10**9+7
n,a,b = map(int,input().split())
def combination(n, a):
    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)

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


def pow(x,n,m):
  if n==0:
    return 1
  res=pow(x*x%m,n//2,m)
  if n%2==1:
    res=res*x%m
  return res


c=max(a,b)
inv=[0 for i in range(c+1)]
finv=[0 for i in range(c+1)]
inv[1]=1
finv[0]=finv[1]=1
for i in range(2,c+1):
  
  
  
  
  inv[i]=1000000007-(1000000007//i)*inv[1000000007%i]%1000000007
  finv[i]=finv[i-1]*inv[i]%1000000007
def kaizyou(k):
  num=1
  for i in range(n-k+1,n+1):
    num=num*i%1000000007
  return num

def combinations(k):
  return kaizyou(k)*finv[k]%1000000007

print((pow(2,n,1000000007)-combinations(a)-combinations(b)-1)%1000000007)

Solution (Python):


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

MOD = 10**9 + 7



def combination(n, a):
    
    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


count = (pow(2, n, MOD) - 1 - combination(n, a) - combination(n, b)) % MOD
print(count)

Solution (Python):

MOD = 10 ** 9 + 7


def comb(n, k):
    if n < k or k < 0:
        return 0

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


N, A, B = map(int, input().split())
x1 = comb(N, A)
x2 = comb(N, B)
print((pow(2, N, MOD) - 1 - x1 - x2) % MOD)

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

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

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

Solution (Python):
import sys
from math import factorial

MOD = 10 ** 9 + 7


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


if __name__ == "__main__":
    main()

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

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

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

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

len_inv = 2*(10**5) + 10
inv = [1]*(len_inv)

for i in range(2, len_inv):
    inv[i] = inv[MOD%i] * (MOD - MOD//i) % MOD

def comb(n, k, MOD):
    x = 1
    for i in range(k):
        x *= (n-i)
        x *= inv[i+1]
        x %= MOD
    return x

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

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

def f(x):
    if x == 0:
        return 1
    elif x % 2 == 0:
        return (f(x // 2) ** 2) % mod
    else:
        return (f(x - 1) * 2) % mod
def comb(n,k,p):
    """power_funcを用いて(nCk) mod p を求める"""
    from math import factorial
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    a=factorial(n) %p
    b=factorial(k) %p
    c=factorial(n-k) %p
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
    """a^b mod p を求める"""
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p
    
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
    
    return [w[0], w[1]]


def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m

def nCm(a):
    ans = 1
    for i in range(a):
        ans *= n - i
        ans %= mod
    for i in range(1, a+1):
        ans *= mod_inv(i, mod)
        ans %= mod
    return ans

base = f(n)
comb_a = nCm(a)
comb_b = nCm(b)
print((base - comb_a - comb_b - 1) % mod)

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,a,b = inpm()

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

modinv_table = [-1] * (max(a,b)+1)
modinv_table[1] = 1
for i in range(2, max(a,b)+1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod

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

ret = (ret - aa - bb) % mod

print(ret)

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,a,b = inpm()

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

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

    return K * x

ret = (pow_k(2,n) - 1) % mod

modinv_table = [-1] * (max(a,b)+1)
modinv_table[1] = 1
for i in range(2, max(a,b)+1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod

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

aa = binomial_coefficients(n,a) % mod
bb = binomial_coefficients(n,b) % mod

ret = (ret - aa - bb) % mod

print(ret)

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



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


nCa = 1

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

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

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


ans -= (nCa + nCb)
ans %= mod
print(ans)

Solution (Python):
import math

n, a, b = map(int, input().split())
MOD = 1000000000 + 7

inv = [1, 1]
com = [0, n]
for i in range(2, max(a, b) + 1):
    inv.append(MOD - inv[MOD % i] * (MOD // i) % MOD)
    com.append(com[i - 1] * (n - i + 1) * inv[i] % MOD)

print((pow(2, n, MOD) - com[a] - com[b] - 1) % MOD)

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

M = 10 ** 9 + 7

all = pow(2, n, M) - 1
all %= M

def C(n,x):
    num = 1
    den = 1
    for i in range(x):
        num *= (n-i)
        num %= M
        den *= (i+1)
        den %= M

    inv = pow(den, M-2, M)

    return num * inv % M

ans = all - C(n,a) - C(n,b)
ans %= M
print(ans)

Solution (Python):
def main():
    import sys

    def input(): return sys.stdin.readline().rstrip()

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





if __name__ == '__main__':
    main()

Solution (Python):

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


all_ = pow(2,n,p)


C_=[1]*(b+10)
for i in range(1,b+1):
    C_[i] = (C_[i-1] * (n-i+1)%p * pow(i,p-2,p))%p 


ans = (all_-C_[a]-C_[b])%p
print(ans-1)

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

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

nm= 1
dn = 1

for i in range(a):
  nm = (nm * (n-i)) % (10**9+7)
  dn = (dn * (i+1)) % (10**9+7)

ans = (ans - nm*pow(dn,-1,10**9+7) - 1) % (10**9+7)

for i in range(a,b):
  nm = (nm * (n-i)) % (10**9+7)
  dn = (dn * (i+1)) % (10**9+7)

ans = (ans - nm*pow(dn,-1,10**9+7)) % (10**9+7)

print(ans)

Solution (Python):
import copy

def fast_pow(x, n, MOD):
    res = 1
    while n:
        if n & 1:
            res = res * x % MOD
        x = x * x % MOD
        n >>= 1
    return res
  
  
def prepare(n, MOD):
 
    
    f = 1
    factorials = [1]  
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    
    inv = pow(f, MOD - 2, MOD)
    
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs

MOD = 10**9+7
fact, fact_inv = prepare(2*10**5, MOD)

n, a, b = map(int,input().split())
f = copy.deepcopy(n)
for i in range(1, b+1):
    if i == a:
        nca = f * fact_inv[a] % MOD
    if i == b:
        ncb = f * fact_inv[b] % MOD
        break
    f = f * (n - i) % MOD
print((fast_pow(2, n, MOD) - 1 - nca - ncb) % MOD)

Solution (Python):
import copy

def fast_pow(x, n, MOD):
    res = 1
    while n:
        if n & 1:
            res = res * x % MOD
        x = x * x % MOD
        n >>= 1
    return res
  
  
def prepare(n, MOD):
 
    
    f = 1
    factorials = [1]  
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    
    inv = pow(f, MOD - 2, MOD)
    
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs

MOD = 10**9+7
fact, fact_inv = prepare(2*10**5, MOD)

n, a, b = map(int,input().split())
f = copy.deepcopy(n)
for i in range(1, b+1):
    if i == a:
        nca = f * fact_inv[a] % MOD
    if i == b:
        ncb = f * fact_inv[b] % MOD
        break
    f = f * (n - i) % MOD
print((fast_pow(2, n, MOD) - 1 - nca - ncb) % MOD)

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

Solution (Python):
MOD = 10**9 + 7

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

def getComb(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

ans = pow(2, N, MOD) - 1
ans -= getComb(N, A, MOD)
ans -= getComb(N, B, MOD)
ans %= MOD

print(ans)

Solution (Python):
n, a, b = map(int, input().split())
M = 10**9 + 7
def cmb(n,r):
    x = 1
    y = 1
    for i in range(r):
        x *= n - i
        x %= M
        y *= (i + 1)
        y %= M
    return x * pow(y, M-2, M) % M

print((pow(2,n,M)-cmb(n,a)-cmb(n,b)-1)%M)

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

mod = 10**9+7
total = pow(2,n,mod) - 1 



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

    denominator=1 
    for j in range(1,r+1):
        denominator = (denominator*j) % mod
    
    
    return (numerator * pow(denominator,mod-2,mod)) % mod
    
ans = (total - nCr(n,a,mod) - nCr(n,b,mod)) % mod
print(ans)

Solution (Python):
def combination_mod(n, k, mod=10 ** 9 + 7):
    if k > n:
        return 1

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


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

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

Solution (Python):
def modComb(n,r,mod):
    nume = 1
    deno = 1
    for i in range(r):
        nume = nume*(n-i) % mod
        deno = deno*(i+1) % mod
    return nume*pow(deno, mod-2, mod) % mod

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

mod = 10**9+7

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

print(ans)

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

mod = 10**9+7
total = pow(2,n,mod) - 1 



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

    denominator=1 
    for j in range(1,r+1):
        denominator = (denominator*j) % mod
    
    
    return (numerator * pow(denominator,mod-2,mod)) % mod
    
ans = (total - nCr(n,a,mod) - nCr(n,b,mod)) % mod
print(ans)

Solution (Python):
import math
import sys
import collections
import bisect
readline = sys.stdin.readline


def main():
    n, a, b = map(int, readline().rstrip().split())
    mod = 10 ** 9 + 7

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

    nca, ncb = 1, 1

    for i in range(b):
        ncb = ncb * (n - i) % mod
        ncb *= pow(i + 1, mod - 2, mod)
        if i + 1 == a:
            nca = ncb

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


if __name__ == '__main__':
    main()

Solution (Python):


import sys
input=sys.stdin.readline
MOD=10**9+7

def main():
    n,a,b=map(int,input().split())
    nca=1
    for i in range(a):
        nca=(nca*(n-i))%MOD
    for i in range(a):
        nca=(nca*pow(i+1,MOD-2,MOD))%MOD
    ncb=1
    for i in range(b):
        ncb=(ncb*(n-i))%MOD
    for i in range(b):
        ncb=(ncb*pow(i+1,MOD-2,MOD))%MOD
    print((pow(2,n,MOD)-1-nca-ncb)%MOD)
    
    
    
if __name__=="__main__":
    main()

Solution (Python):
from sys import stdin
input = stdin.readline


def pow_k(x, n, MOD=1_000_000_007):
  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


def comb(n, r, MOD=1_000_000_007):
  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])
      result %= MOD

  return result


def main():
  N, a, b = list(map(int, input().split()))

  print((pow_k(2, N)-1-comb(N, a)-comb(N, b)) % 1_000_000_007)


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

Solution (Python):
def modComb(n, r, mod):
    nume = 1
    deno = 1
    for i in range(r):
        nume = nume*(n-i) % mod
        deno = deno*(i+1) % mod
    return nume*pow(deno, mod-2, mod) % mod
 
n, a, b = map(int, input().split())

mod = 10**9+7

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

print(ans)

Solution (Python):


import sys
input = sys.stdin.readline


from operator import mul
from functools import reduce

def pow_k(x, n, mod):
    """
    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


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 main():
    n, a, b = [int(i) for i in input().strip().split()]
    MOD = 10**9 + 7
    _sum = ((pow_k(2, n,MOD))-1) % MOD
    cmb_a = combination(n, a,MOD)
    cmb_b = combination(n, b,MOD)
    ans = (_sum - cmb_a - cmb_b) % MOD
    
    print(ans)

if __name__ == "__main__":
    main()