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
read = sys.stdin.readline


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


class ModInt:
    def __init__(self, x, MOD=10 ** 9 + 7):
        '''
        pypyじゃないと地獄みたいな遅さなので注意
        '''
        self.mod = MOD
        self.x = x % MOD

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

    __repr__ = __str__

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

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

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

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

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

    __radd__ = __add__

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

    __rmul__ = __mul__

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

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


def combination(n, r):
    if r > n:
        return 0  
    r = min(r, n - r)
    nf = rf = ModInt(1)
    for i in range(r):
        nf = nf * (n - i)
        rf = rf * (i + 1)
    return nf / rf



MOD = 10**9 + 7
n, a, b = read_ints()

tmp = ModInt(2)**n - 1
ans = tmp - combination(n, a) - combination(n, b)
print(ans)

Solution (Python):



import sys
read = sys.stdin.readline


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


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

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

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

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

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

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

    __radd__ = __add__

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

    __rmul__ = __mul__

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

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


class ModInt:
    def __init__(self, x, MOD=10 ** 9 + 7):
        '''
        pypyじゃないと地獄みたいな遅さなので注意
        '''
        self.mod = MOD
        self.x = x % MOD

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

    __repr__ = __str__

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

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

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

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

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

    __radd__ = __add__

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

    __rmul__ = __mul__

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

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

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


def combination(n, r):
    if r > n:
        return 0  
    r = min(r, n - r)
    nf = rf = ModInt(1)
    for i in range(r):
        nf = nf * (n - i)
        rf = rf * (i + 1)
    return nf / rf



MOD = 10**9 + 7
n, a, b = read_ints()




tmp = ModInt(2)**n - 1
ans = tmp - combination(n, a) - combination(n, b)
print(ans)

Solution (Python):



import sys
read = sys.stdin.readline


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


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

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

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

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

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

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

    __radd__ = __add__

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

    __rmul__ = __mul__

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

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


def 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


def combination(n, r):
    if r > n:
        return 0  
    r = min(r, n - r)
    nf = rf = ModInt(1)
    for i in range(r):
        nf = nf * (n - i)
        rf = rf * (i + 1)
    return nf / rf



MOD = 10**9 + 7
n, a, b = read_ints()




tmp = ModInt(2)**n - 1
ans = tmp - combination(n, a) - combination(n, b)
print(ans)

Solution (Python):



import sys
read = sys.stdin.readline


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


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

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

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

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

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

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

    __radd__ = __add__

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

    __rmul__ = __mul__

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

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


def 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


def combination(n, r):
    if r > n:
        return 0  
    r = min(r, n - r)
    nf = rf = ModInt(1)
    for i in range(r):
        nf = nf * (n - i)
        rf = rf * (i + 1)
    return nf / rf



MOD = 10**9 + 7
n, a, b = read_ints()




tmp = ModInt(2)**n - 1
ans = tmp - combination(n, a) - combination(n, b)
print(ans)

Solution (Python):



import sys
read = sys.stdin.readline


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


class ModInt:
    def __init__(self, x, MOD=10 ** 9 + 7):
        self.mod = MOD
        self.x = x if 0 <= x < MOD else x % MOD

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

    __repr__ = __str__

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

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

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

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

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

    __radd__ = __add__

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

    __rmul__ = __mul__

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

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


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


def combination(n, r):
    if r > n:
        return 0  
    r = min(r, n - r)
    nf = rf = ModInt(1)
    for i in range(r):
        nf = nf * (n - i)
        rf = rf * (i + 1)
    return nf / rf



MOD = 10**9 + 7
n, a, b = read_ints()




tmp = ModInt(2)**n - 1
ans = tmp - combination(n, a) - combination(n, b)
print(ans)

Solution (Python):



import sys
read = sys.stdin.readline


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


class ModInt:
    def __init__(self, x, MOD=10 ** 9 + 7):
        self.mod = MOD
        self.x = x % MOD

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

    __repr__ = __str__

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

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

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

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

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

    __radd__ = __add__

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

    __rmul__ = __mul__

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

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


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


def combination(n, r):
    if r > n:
        return 0  
    r = min(r, n - r)
    nf = rf = ModInt(1)
    for i in range(r):
        nf = nf * (n - i)
        rf = rf * (i + 1)
    return nf / rf



MOD = 10**9 + 7
n, a, b = read_ints()




tmp = ModInt(2)**n - 1
ans = tmp - combination(n, a) - combination(n, b)
print(ans)

Solution (Python):



import sys
read = sys.stdin.readline


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


class ModInt:
    def __init__(self, x, MOD=10 ** 9 + 7):
        self.mod = MOD
        self.x = x % MOD

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

    __repr__ = __str__

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

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

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

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

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

    __radd__ = __add__

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

    __rmul__ = __mul__

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

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


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


def combination(n, r):
    if r > n:
        return 0  
    r = min(r, n - r)
    nf = rf = ModInt(1)
    for i in range(r):
        nf = nf * (n - i)
        rf = rf * (i + 1)
    return nf / rf



MOD = 10**9 + 7
n, a, b = read_ints()




tmp = ModInt(2)**n - 1
ans = tmp - combination(n, a) - combination(n, b)
print(ans)

Solution (Python):
n,a,b = map(int,input().split())
def power(x,b):
  if x == 1:
    return b
  if x%2 == 0:
    return (power(x//2,b)**2)%(10**9+7)
  else:
    return (b*power(x-1,b))%(10**9+7)
ans = power(n,2)-1
x1 = 1
y1 = 1
x2 = 1
y2 = 1
for i in range(a):
  x1 = (x1*(n-i))%(10**9+7)
  y1 = (y1*(i+1))%(10**9+7)
for i in range(b):
  x2 = (x2*(n-i))%(10**9+7)
  y2 = (y2*(i+1))%(10**9+7)
ans -= x1*power(10**9+5,y1)
ans -= x2*power(10**9+5,y2)
print(ans%(10**9+7))

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

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

no = {a: 0, b:0}

for k in [a, b]:
    num = 1
    denom = 1
    for i in range(k):
        num *= n - i
        num %= mod
    
    for i in range(1, k+1):
        denom *= i
        denom %= mod
    
    no[k] = num * pow(denom, mod-2, mod)
    no[k] %= mod

print((total - no[a] - no[b]) % mod)

Solution (Python):


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



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

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

    return K * x
    
    

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

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

    return (K * x) % m
    
n, a, b = map(int, input().rstrip().split())

max_num = pow_k_mod(2, n, int(1e9+7)) - 1
a = max(a, n - a)
b = max(b, n - b)

num_a = 1
for i in range(a+1, n+1):
    num_a *= i
    num_a %= int(1e9+7)
for i in range(1, n - a + 1):
    num_a = (num_a * modinv(i, int(1e9+7))) % int(1e9+7)
    
num_b = 1
for i in range(b+1, n+1):
    num_b *= i
    num_b %= int(1e9+7)
for i in range(1, n - b + 1):
    num_b = (num_b * modinv(i, int(1e9+7))) % int(1e9+7)
    
print((max_num - num_a - num_b) % int(1e9+7))

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

def modcomb(n, k, mod):
    def fact(n, k, mod):
        ans = 1
        while n>k:
            ans = (ans * n) % mod
            n -= 1
        return ans

    def inv(k, mod):
        ans = 1
        while k>1:
            ans = (ans * k) % mod
            k -= 1
        return pow(ans, mod-2, mod)

    return (fact(n,n-k,mod) * inv(k, mod))%mod

def resolve():
    N,a,b = list(map(int, input().split()))
    ans = pow(2,N,MOD) - 1 - modcomb(N, a, MOD) - modcomb(N, b, MOD)
    print(ans % MOD)

resolve()

Solution (Python):
import math
n,a,b = [int(i) for i in input().split()]
mod = 10**9+7
  
def comb(n,k):
  ans = 1
  for i in range(k):
    ans = ans*(n-i)%mod
  for i in range(1,k+1):
    ans = ans*pow(i,mod-2,mod)%mod
  return ans

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

Solution (Python):
import math

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

p = 10**9 + 7


def cmb(n, r):
    total = 1
    for i in range(r):
        total = total * (n - i) % p
        
    return total * pow(math.factorial(r), p - 2, p) % p

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

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

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

def c(n, r):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

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

Solution (Python):
mod=10**9+7
def nCr(n, r):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod
n,a,b=map(int,input().split())
f=pow(2, n, mod)-1-nCr(n,a)-nCr(n,b)

while f<0:
    f+=mod
print(f)

Solution (Python):
from functools import reduce
def comb(k, r, mod):
  return (reduce(lambda x, y:(x*y)%mod, range(k-r+1, k+1))*pow(reduce(lambda x, y:(x*y)%mod, range(1, r+1)), mod-2, mod))%mod

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

Solution (Python):
import math

MOD = 10 ** 9 + 7


def cmb(n, r):
    total = 1
    for i in range(r):
        total = total * (n - i) % MOD
    return total * pow(math.factorial(r), MOD - 2, MOD) % MOD


def calc(n, r):
    ret = 1
    for i in range(r):
        ret = ret * (n - i) % MOD
    return ret * pow(math.factorial(r), MOD - 2, MOD) % MOD


if __name__ == '__main__':
    n, a, b = list(map(int, input().split(" ")))

    total = pow(2, n, MOD)
    a_total = cmb(n, a)
    b_total = cmb(n, b)
    print((total - a_total - b_total - 1) % MOD)

Solution (Python):
import math

MOD = 10 ** 9 + 7


def cmb(n, r):
    total = 1
    for i in range(r):
        total *= (n - i) % MOD
    return total * pow(math.factorial(r), MOD - 2, MOD) % MOD


def calc(n, r):
    ret = 1
    for i in range(r):
        ret = ret * (n - i) % MOD
    return ret * pow(math.factorial(r), MOD - 2, MOD) % MOD


if __name__ == '__main__':
    n, a, b = list(map(int, input().split(" ")))

    total = pow(2, n, MOD)
    a_total = calc(n, a)
    b_total = calc(n, b)
    print((total - a_total - b_total - 1) % MOD)

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

def calc(n):
    ret = 1
    for i in range(n):
        ret = ret * (N - i) % MOD
    return ret * pow(factorial(n), MOD - 2, MOD) % MOD

print(max(0, (pow(2, N, MOD) - ((calc(A) + calc(B)) % MOD) - 1) % MOD))

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

def my_pow(num, p, mod):
    if p==0:
        return 1
    elif p%2==0:
        return (my_pow(num, p//2, mod)**2)%mod
    else:
        return (my_pow(num, p-1, mod)*num)%mod

def comb(num, r, mod):
    r = min(r, num-r)
    y = 1
    for i in range(num-r+1, num+1):
        y = (y*i)%mod
    x = 1
    for i in range(1, r+1):
        x = (x*i)%mod
    return (y*my_pow(x, mod-2, mod))%mod

result = my_pow(2, n, mod)-1 -comb(n, a, mod) -comb(n, b, mod)
while result < 0:
    result += mod
print(result)

Solution (Python):
def comb(n, r, p):
    x, y = 1, 1
    for i in range(n, n - r, -1):
        x *= i
        y *= i + r - n
        x %= p
        y %= p
    return pow(y, p - 2, p) * x % p

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

Solution (Python):
n,a,b=map(int,input().split())
mod=10**9+7
def comb_mod(N,r,mod):
    r=min(n-r,r)
    X=1
    Y=1
    for i in range(r):
        X*=N-i
        Y*=i+1
        X%=mod
        Y%=mod
    return X*pow(Y,mod-2,mod)%mod

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

Solution (Python):



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

N=pow(10,9)+7




def modpow(b,e,m): 

    result=1

    while(e!=0): 
          if(e&1==1): 
             result=(result*b)%m 
          e>>=1
          b=(b*b)%m
    
    return result

def combination(n,r,N):
    bunshi=1
    for i in range(n-r+1,n+1):
        bunshi=(bunshi*i)%N
    bunbo=1
    for i in range(1,r+1):
        bunbo=(bunbo*i)%N
    return bunshi*modpow(bunbo,N-2,N)











print (modpow(2,n,N)-combination(n,a,N)-combination(n,b,N)-1)%N

Solution (Python):
from functools import reduce

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

def nCr(N, R, DIV):
    f = lambda x,y: x*y%DIV
    X = reduce(f, range(N-R+1, N+1))
    Y = reduce(f, range(1, R+1))
    return X*pow(Y, DIV-2,DIV)%DIV

all_combi = pow(2,n,DIV)
combi_a = nCr(n,a,DIV)
combi_b = nCr(n,b,DIV)


output = all_combi-1 - combi_a - combi_b


print(output%DIV)

Solution (Python):
import sys
from itertools import combinations, permutations, product, combinations_with_replacement, accumulate
from heapq import heapify, heappop, heappush, heappushpop
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from math import sqrt, log, floor, ceil, factorial, cos, sin, pi
from fractions import gcd
from operator import mul
from functools import reduce
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
INF = float('inf')
LINF = 2**63-1
NIL = -LINF
MOD = 10**9+7
MGN = 4
def II(): return int(input())
def IF(): return float(input())
def IS(): return input().replace('\n', '')
def ILCI(n: int): return [II() for _ in range(n)]
def ILCF(n: int): return [IF() for _ in range(n)]
def ILI(): return list(map(int, input().split()))
def ILLI(n: int): return [[int(j) for j in input().split()] for i in range(n)]
def ILF(): return list(map(float, input().split()))
def ILLF(n: int): return [[float(j) for j in input().split()] for i in range(n)]
def LTOS(lst: list, sep: str = ' '): return sep.join(map(str, lst))
def DEC(lst: list): return list(map(lambda x: x-1, lst))
def INC(lst: list): return list(map(lambda x: x+1, lst))


def nck_mod(N: int, K: int, MOD: int = 10**9+7) -> int:
    """ 非負整数 N, K を受け取り、
    N 個の物から K 個を選ぶ組み合わせの数を返す """
    assert N is not None and K is not None, "N, K は None でない"
    assert N >= 0 and K >= 0

    x, y = 1, 1
    for i in range(K):
        x = x * (N - i) % MOD
        y = y * (i + 1) % MOD

    return x * pow(y, MOD-2, MOD) % MOD


def main():
    N,A,B = ILI()

    all = pow(2, N, MOD)
    ans = (all - nck_mod(N, A, MOD) - nck_mod(N, B, MOD) - 1) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

MOD = 10**9 + 7

def factorial(a):
    return 1 if a == 1 else a * factorial(a - 1) % MOD

def inverse(x):
    return pow(x, MOD - 2, MOD)

def combination(a, b):
    ans = 1
    for i in range(b):
        ans = ans * (a - i) * inverse(i + 1) % MOD
    return ans

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

Solution (Python):
def mod_rep_pow(a, n, mod=(10 ** 9 + 7)):
    res = 1
    while n > 0:
        if n % 2 == 0:
            a = a ** 2 % mod
            n //= 2
        else:
            res = res * a % mod
            n -= 1
    return (res % mod)


def mod_comb(n, k, mod=(10 ** 9 + 7)):
    res1 = 1
    for i in range(n, (n - k), -1):
        res1 *= i
        res1 %= mod
    res2 = 1
    for i in range(1, (k + 1)):
        res2 *= i
        res2 %= mod
    return ((res1 * mod_rep_pow(res2, (mod - 2), mod)) % mod)


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

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,a,b = mi()
p = 10 **9 + 7
nstr = str(n)
nstr = nstr[::-1]
two_ten = []
two_ten.append(2)
for i in range(1,11):
    ima = two_ten[i-1]
    temp = 1
    for _ in range(10):
        temp = temp*ima % p
    two_ten.append(temp)

ans = 1
for i in range(len(nstr)):
    temp = 1
    for j in range(int(nstr[i])):
        temp = temp * two_ten[i] % p
    ans = ans * temp % p
ans -= 1


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)


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

ans -= combination(n,a)
ans -= combination(n,b)
print(ans % p)