Problem:


Score : 400 points

Problem Statement

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

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

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

How many different bouquets are there that Akari can make?

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

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

Constraints

All values in input are integers.

2 \leq n \leq 10^9

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

Input

Input is given from Standard Input in the following format:

n a b

Output

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

Sample Input 1

4 1 3

Sample Output 1

7

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

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

Sample Input 2

1000000000 141421 173205

Sample Output 2

34076506

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



Sample input:
4 1 3


Sample output:
7

Submission status: Accepted

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

def permutation(n,r,mod):
    perm = 1
    for integer in range(n-r+1, n+1):
        perm *= integer
        perm %= mod
    return perm

def RepeatSquaring(x, n, m):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = (ans*x)%m
    x = (x*x)%m
    n = n >> 1
  return ans

def cmb(n, r, mod):
    nume = permutation(n,r,mod)
    deno = permutation(r,r,mod)
    return (nume * RepeatSquaring(deno, mod-2, mod)) % mod

ans = (RepeatSquaring(2, n, mod) - 1 - cmb(n, a, mod) - cmb(n, b, mod)) % mod

print(ans)

Submission status: Accepted

Solution code:
# import bisect
# # import heapq
# # from copy import deepcopy
# # from collections import deque
# # from collections import Counter
# # from itertools import accumulate
# # from itertools import permutations
# import numpy as np
# # import math
n, a, b = map(int, input().split())
twos = 1
count = 0
# p = list(map(int, input().split()))
# n = int(input())
mod = 10 ** 9 + 7
def fac(n,a,mod):
    x,y = 1,1
    for _ in range(a):
        x *= n; y *= a
        x %= mod; y %= mod
        n -= 1; a -= 1

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



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

print(ans)

Submission status: Accepted

Solution code:
mod = 10**9 + 7

def C(n, r, mod):
    x, y = 1, 1
    for _ in range(r):
        x *= n; y *= r
        x %= mod; y %= mod
        n -= 1; r -= 1
    return x * pow(y, mod - 2, mod) % mod


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

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

Submission status: Accepted

Solution code:
def binarev(x):
    ans = []
    while x:
        ans.append(x%2)
        x = x//2
    return ans

def power(a, b, *c):
    if c:
        c = c[0]
        bb = binarev(b)
        n = len(bb)
        pool = [a%c] * n
        for i in range(1, n):
            pool[i] = (pool[i-1]**2)%c
        ans = 1
        for i in range(n):
            if bb[i]: ans = (pool[i]*ans)%c
        return ans
    else:
        bb = binarev(b)
        n = len(bb)
        pool = [a] * n
        for i in range(1, n):
            pool[i] = pool[i-1]**2
        ans = 1
        for i in range(n):
            if bb[i]: ans *= pool[i]
        return ans

def root(x, n):
    a = x
    left = 0
    right = x
    while left+1 < right:
        x = (left + right)//2
        if power(x, n) <= a:
            left = x
        else:
            right = x
    return left

def log(x, n):
    a = x
    left = 0
    right = x
    while left+1 < right:
        x = (left + right)//2
        if power(n, x) <= a:
            left = x
        else:
            right = x
    return left

def permod(MOD, N, R=-1):
    from functools import reduce
    if R==-1: R=N
    return reduce(lambda x,y: x*y%MOD, range(N, N-R, -1))


def combod(MOD, N, R):
    return permod(MOD, N, R) * power(permod(MOD, R), MOD-2, MOD) % MOD


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

Submission status: Accepted

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

MOD = 1000000007  # type: int


def solve(n: int, a: int, b: int):
    al = modPow(2, n, MOD) - 1
    # aに対して
    X = 1
    # 分子
    for i in range(a):
        X = (X * (n - i)) % MOD
    Y = 1
    # Y
    for i in range(a):
        Y = (Y * (a - i)) % MOD
    a_val = (X * modPow(Y, MOD - 2, MOD)) % MOD

    # bに対して
    X = 1
    # 分子
    for i in range(b):
        X = (X * (n - i)) % MOD
    Y = 1
    # Y
    for i in range(b):
        Y = (Y * (b - i)) % MOD
    b_val = (X * modPow(Y, MOD - 2, MOD)) % MOD

    print((al - a_val - b_val) % MOD)


def modPow(a: int, n: int, p: int):
    if n == 1:
        return a
    elif n % 2 == 0:
        n2 = modPow(a, n / 2, p)
        return pow(n2, 2) % p
    else:
        return (a * modPow(a, n - 1, p)) % p


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = int(next(tokens))  # type: int
    b = int(next(tokens))  # type: int
    solve(n, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MAX = 2 * 10 ** 5 + 1
finv = [0] * MAX
inv = [0] * MAX
MOD = 10 ** 9 + 7


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


def COM(n, k):
    if n < k or k < 0:
        return 0
    res = 1
    for i in range(n, n - k, -1):
        res *= i
        res %= MOD
    res *= finv[k]
    return res % MOD


n, a, b = map(int, input().split())
total = pow(2, n, MOD) - 1
COMinit()
not_a = COM(n, a)
not_b = COM(n, b)
ans = total - not_a - not_b
while ans < 0:
    ans += MOD
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc156/submissions/10277689

# コンテスト中に通せたけどmodintクラスで実装してみる
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


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

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc156/submissions/10277689

# コンテスト中に通せたけどmodintクラスで実装してみる
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


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

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc156/submissions/10277689

# コンテスト中に通せたけどmodintクラスで実装してみる
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


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

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc156/submissions/10277689

# コンテスト中に通せたけどmodintクラスで実装してみる
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


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

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc156/submissions/10277689

# コンテスト中に通せたけどmodintクラスで実装してみる
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


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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# mod. m での a の逆元 a^{-1} を計算する
# b * a^{-1} (mod m)を計算したい場合はb * modinv(a, m) % m
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
    
    
# 途中計算でmodを計算する高速な累乗計算
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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
# print(comb(n,a))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

N=pow(10,9)+7
#n=1000000000
#a=141421
#b=173205

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)

#pow(2,n)-nCa-nCb-1
#nCr=n!/((n-r)!*r!)だから
#bunshi=n*n-1*・・・*n-r+1
#bunbo=1*・・・*r
#Nが素数だから、フェルマーの小定理より
#modpow(a,N-1,N)=1
#a*pow(a,N-2)=pow(a,N-1)=1(modN)
#より。aのmodNでの逆元はpow(a,N-2)になる。
#r!の逆元が欲しいから、modpow(bunbo,N-2,N)を掛ける。

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

Submission status: Accepted

Solution code:
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
# if output>(10**9+7):
#     output = output%(10**9+7)
print(output%DIV)