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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
    #print(pow(2, MOD, MOD))


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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 #n*(n-1)*...*(n-k+1) 分子
    w = w*(i+1)%m #1*2*...*k 分母
  #pow(w,m-2,m)はmod mの世界でのwの逆元
  return (v*pow(w,m-2,m)%m)
print((pow(2,n,m)-1-c(a)-c(b))%m)

Submission status: Accepted

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

# modが素であるとする
def modinv(a, mod):
    return modpow(a, mod-2, mod) % mod

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

# nがある程度小さい時(10^7程度)
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

# kが小さい時
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
# 全部でn**2(0本は除くかも)
# a本を選ぶ場合の数はnCa
total = modpow(2, n, mod)
tota = modcombination_smallk(n, a, mod)
totb = modcombination_smallk(n, b, mod) 
print((total-tota-totb-1)%mod)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,a,b=list(map(int,input().split()))
#2^n-nCa-nCbを求めればいい。ただし100000007で割ったあまりでなくてはならない
#まずは2^nを求める
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):
  #iの逆数を求める。
  #mod　p=1000000007の世界で逆元を求める
  #p=(p//a)*a+(p%a)
  #mod pをとると a=-(p//a)*(p%a)^-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)

Submission status: Accepted

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

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
# 二項展開より 2**n - 1 - nCa - nCb を MOD 10**9 + 7 で求めればよい


def combination(n, a):
    # nCk = n! / k! (n-k)! のうち、 n!/(n-k)! を計算する
    res = 1
    div = 1
    for i in range(a):
        res *= n-i
        res %= MOD
        div *= a - i
        div %= MOD

    # print(f'n {n}, a {a}, res {res}, div {div}')
    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)

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from math import factorial

MOD = 10 ** 9 + 7


def main():
    # input = sys.stdin.buffer.readline
    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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
    # 互いに素なa,bについて、a*x+b*y=1の一つの解
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
    # [x,y]
    return [w[0], w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

#n種類の花を使って、花束を作る組み合わせは2^n-1通り
#pow(x,y,mod) : (x**y) % mod
ans = pow(2, n, mod)-1

#nCa
nCa = 1
#分子:n*(n-1)*...*(n-a+1)
for i in range(n-a+1, n+1):
    nCa *= i
    nCa %= mod
#分母:1/a! = 1/(1*2*...*a) = 1^(p-2)*2^(p-2)*,,,*a^(p-2)
for i in range(1, a+1):
    nCa *= pow(i, mod-2, mod)
    nCa %= mod
    
#nCb
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

#2^n-1通りからnCaとnCbを引く
ans -= (nCa + nCb)
ans %= mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

#全体の組み合わせの数：All
all_ = pow(2,n,p)

#n本からi本選ぶ組み合わせの数:C[i],i:0~b
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 
# C_

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return 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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

mod = 10**9+7
total = pow(2,n,mod) - 1 # 制約なしの全パターン_n**2-1※'-1'は0本の花束

# n個からr個を選択した時のパターン総数_組み合わせ重複なし
# n! / (r! * (n-r)!) → nが大き過ぎて出来ない →変形→ n*(n-1)*･･･(n-r+1)/r! ↓関数化
def nCr(n, r, mod):
    numerator=1 #分子_n*(n-1)*･･･(n-r+1)
    for i in range(n-r+1, n+1):
        numerator = (numerator*i) % mod

    denominator=1 #分母_r!
    for j in range(1,r+1):
        denominator = (denominator*j) % mod
    # 剰余の計算において割るとよくない → 割るのではなく逆元を掛ける
    # フェルマーの小定理_pが素数なら整数aのmod pにおける逆元は a**(p-2) ※aとpは互いに素
    return (numerator * pow(denominator,mod-2,mod)) % mod
    
ans = (total - nCr(n,a,mod) - nCr(n,b,mod)) % mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

mod = 10**9+7
total = pow(2,n,mod) - 1 # 制約なしの全パターン_n**2-1※'-1'は0本の花束

# n個からr個を選択した時のパターン総数
# n! / (r! * (n-r)!) → nが大き過ぎて出来ない →変形→ n*(n-1)*･･･(n-r+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
    # 割るとよくない → 逆元を掛ける
    # フェルマーの小定理_modが素数なら1/aの逆元は a**(mod-2)
    return (numerator * pow(denominator,mod-2,mod)) % mod
    
ans = (total - nCr(n,a,mod) - nCr(n,b,mod)) % mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc156/tasks/abc156_d

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