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:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7


# nCr

def ruijo(n, l, mod):
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


def cmb(n, r, mod):
    if r == 1:
        return n
    elif (n == r or r == 0):
        return 1
    else:
        if (r < 0 or r > n):
            return 0
        r = min(r, n - r)
        return ruijo(n, n - r + 1, mod) * g2[r] % mod


mod = 10 ** 9 + 7  # 出力の制限
N = 10 ** 6
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

n,a,b = lr()
total = power(2,n,mod)-1
total -= (cmb(n,a,mod)+cmb(n,b,mod))%mod
total %= mod
print(total)

Submission status: Accepted

Solution code:
def combination(n, r, m):
    res = 1
    r = min(r, n - r)

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

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

total -= (combination(n, a, mod) + combination(n, b, mod)) % mod

print(total % mod)

Submission status: Accepted

Solution code:
def cmb(n, r, p):
    # ex. 5_C_4 = 5_C_1、rが小さい方を計算したほうが楽
    r = min(r, n - r)

    # n*(n-1)*...*(n-r+1)
    # 組み合わせの公式の分子
    upper = 1
    for i in range(n, n - r, -1):
        upper = (upper * i) % p

    # 1*2*...*r
    # 組み合わせの公式の分母
    lower = 1
    for i in range(1, r + 1):
        lower = (lower * i) % p
    # 剰余の計算において、+-*は良いが、/は普通にやると成り立たない
    # ex. 6/3(mod5)...2になって欲しいが1/3になってしまう
    # 割るのではなく、「逆元」を掛けるとすれば割らなくて済む
    # フェルマーの小定理より、pが素数なら1/lowerの逆元はlower**(p-2)
    # powの第3引数を使うことで繰り返し二乗法になる
    return (upper * pow(lower, p - 2, p)) % p

mod = pow(10, 9) + 7
n, a, b = map(int, input().split())
# 全ての選び方-何も選ばない時-a本の時-b本の時
ans = (pow(2, n, mod) - 1 - cmb(n, a, mod) - cmb(n, b, mod)) % mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class Factorial():
    def __init__(self, mod=10**9 + 7):
        self.mod = mod
        self._factorial = [1]
        self._size = 1
        self._factorial_inv = [1]
        self._size_inv = 1

    def __call__(self, n):
        return self.fact(n)

    def fact(self, n):
        ''' n! % mod '''
        if n >= self.mod:
            return 0
        self._make(n)
        return self._factorial[n]
    
    def _make(self, n):
        if n >= self.mod:
            n = self.mod
        if self._size < n+1:
            for i in range(self._size, n+1):
                self._factorial.append(self._factorial[i-1]*i % self.mod)
            self._size = n+1

    def fact_inv(self, n):
        ''' n!^-1 % mod '''
        if n >= self.mod:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        self._make(n)
        if self._size_inv < n+1:
            self._factorial_inv += [-1] * (n+1-self._size_inv)
            self._size_inv = n+1
        if self._factorial_inv[n] == -1:
            self._factorial_inv[n] = self.modinv(self._factorial[n])
        return self._factorial_inv[n]
    
    @staticmethod
    def xgcd(a, b):
        '''
        Return (gcd(a, b), x, y) such that a*x + b*y = gcd(a, b)
        '''
        x0, x1, y0, y1 = 0, 1, 1, 0
        while a != 0:
            (q, a), b = divmod(b, a), a
            y0, y1 = y1, y0 - q * y1
            x0, x1 = x1, x0 - q * x1
        return b, x0, y0

    def modinv(self, n):
        g, x, _ = self.xgcd(n, self.mod)
        if g != 1:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        return x % self.mod

    def comb(self, n, r):
        ''' nCr % mod '''
        if r > n:
            return 0
        t = self(n)*self.fact_inv(n-r) % self.mod
        return t*self.fact_inv(r) % self.mod
    
    def comb_(self, n, r):
        '''
        nCr % mod
        when r is not large and n is too large
        '''
        c = 1
        for i in range(1, r+1):
            c *= (n-i+1) * self.modinv(i)
            c %= self.mod
        return c

    def comb_with_repetition(self, n, r):
        ''' nHr % mod '''
        t = self(n+r-1)*self.fact_inv(n-1) % self.mod
        return t*self.fact_inv(r) % self.mod

    def perm(self, n, r):
        ''' nPr % mod '''
        if r > n:
            return 0
        return self(n)*self.fact_inv(n-r) % self.mod

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

Submission status: Accepted

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

MOD = 10 ** 9 + 7

ans = pow(2, n, MOD) - 1
na = 1
for i in range(a):
    na *=(n - i)
    na %= MOD
    na *= pow(i + 1, MOD - 2, MOD)
    na %= MOD
ans -= na
nb = 1
for i in range(b):
    nb *= (n - i)
    nb %= MOD
    nb *= pow(i + 1, MOD - 2, MOD)
    nb %= MOD
ans -= nb
print(ans % MOD)

Submission status: Accepted

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

def binary(n):
    return bin(n)[2:]

# バイナリ法
def pow_by_binary_exponentiation(a, x, n): # a^x mod n
    x = [int(b) for b in binary(x)]
    y = a
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * a) % n
    return y

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

N = max(a, b)
fact = [1] * (N + 1)

for i in range(N):
    fact[i + 1] = fact[i] * (i + 1) % mod


def comb(r):
    c = n
    for i in range(1, r):
        c = (c * (n - i)) % mod
    c = c * pow_by_binary_exponentiation(fact[r], mod - 2, mod) % mod
    return c

ans = (ans - comb(a)) % mod
ans = (ans - comb(b)) % mod
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce

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

def combination2(n, r, MOD=10**9+7):
    if not 0 <= r <= n: return 0
    r = min(r, n - r)
    numerator = reduce(lambda x, y: x * y % MOD, range(n, n - r, -1), 1)
    denominator = reduce(lambda x, y: x * y % MOD, range(1, r + 1), 1)
    return numerator * pow(denominator, MOD - 2, MOD) % MOD

print((pow(2,n,MOD) - combination2(n,a) - combination2(n,b)-1)%MOD)

Submission status: Accepted

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

def C(n,r):
    p = n*pow(r,MOD-2,MOD)
    for i in range(1,r):
        p = p*(n-i)%MOD
        p = p * pow(i,MOD-2,MOD)
    return p%MOD



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

Submission status: Accepted

Solution code:
def main():
    n,a,b = map(int,input().split())
    mod = 10**9+7
    s = pow(2,n,mod)
    nCa,nCb = 1,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

    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
    print((s-nCa-nCb-1)%mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

lis = []
on = 0 + n
count = 0
while on > 0:
  if on & 1 == 1:
    lis.append(count)
  count += 1
  on >>= 1

two = [2]
for _ in range(count-1):
  two.append(two[-1]*two[-1]%mod)

ans = 1
for item in lis:
  ans = ans * two[item] %mod

op = mod-2
invlis = []
count = 0
while op > 0:
  if op & 1 == 1:
    invlis.append(count)
  count += 1
  op >>= 1


def modinv(N):
  if N == 1:
    return 1
  else:
    res = 1
    Nlis = []
    for _ in range(count):
      Nlis.append(N%mod)
      N = N*N%mod
    for item in invlis:
      res = res * Nlis[item] %mod
    return res

ans_a = 1
for k in range(n-a+1, n+1):
  ans_a = ans_a*k%mod
amother = 1
for k in range(2, a+1):
  amother = amother * k % mod
ans_a = ans_a*modinv(amother)%mod

ans_b = 1
for k in range(n-b+1, n+1):
  ans_b = ans_b*k%mod
bmother = 1
for k in range(2, b+1):
  bmother = bmother * k % mod  
ans_b = ans_b*modinv(bmother)%mod

print((ans-ans_a-ans_b-1)%mod)

Submission status: Accepted

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

nb = str(bin(n))[2:]
nblis = []
for k in range(len(nb)):
  if nb[-k-1] == '1':
    nblis.append(k)

two = [2]
for k in range(len(nb)-1):
  two.append(two[-1]*two[-1]%mod)


ans = 1
for item in nblis:
  ans = ans * two[item] %mod



bi = str(bin(mod-2))[2:]
blis = []
for k in range(len(bi)):
  if bi[-k-1] == '1':
    blis.append(k)


def modinv(N):
  if N == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(len(bi)):
      li.append(N%mod)
      N = N*N%mod
    for item in blis:
      res = res * li[item] %mod
    return res

ans_a = 1
for k in range(n-a+1, n+1):
  ans_a = ans_a*k%mod
amother = 1
for k in range(2, a+1):
  amother = amother * k % mod
ans_a = ans_a*modinv(amother)%mod


ans_b = 1
for k in range(n-b+1, n+1):
  ans_b = ans_b*k%mod
bmother = 1
for k in range(2, b+1):
  bmother = bmother * k % mod  
ans_b = ans_b*modinv(bmother)%mod

print((ans-ans_a-ans_b-1)%mod)

Submission status: Accepted

Solution code:
MOD = pow(10, 9) + 7

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
def cmb(n, r, p):
    r = min(r, n - r)
    upper = 1
    for i in range(n, n - r, -1):
        upper = (upper * i) % p

    lower = 1
    for i in range(1, r + 1):
        lower = (lower * i) % p

    # フェルマーの小定理よりp素数ならupper**(p-2)は逆元
    return (upper * pow(lower, p - 2, p)) % p

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

Submission status: Accepted

Solution code:
from functools import reduce
def mycmb(n,r,p):
    r = min(r,n-r)
    if r == 0:
        return 1
    over = reduce(lambda x,y:x*y%p,range(n,n-r,-1))
    under = reduce(lambda x,y:x*y%p,range(1,r+1))
    return (over * pow(under,p-2,p))%p
    

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

syu = pow(2,n,p) - 1 - mycmb(n,a,p) - mycmb(n,b,p)
print(syu%p)

Submission status: Accepted

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

nCa=1
nCb=1

tmp=n
for i in range(a):
    nCa*=tmp
    tmp-=1
    nCa%=mod
nCa=nCa*pow(factorial(a),mod-2,mod)%mod
tmp=n
for i in range(b):
    nCb*=tmp
    tmp-=1
    nCb%=mod
nCb=nCb*pow(factorial(b),mod-2,mod)%mod

print(((pow(2,n,mod))-nCa-nCb-1)%mod)

Submission status: Accepted

Solution code:

n, a, b = map(int, input().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)

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

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

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

    return K * x % mod

n, a, b = MAP()
ans = pow_k(2,n,10**9+7) - 1

x0 = 1
y0 = 1
x1 = 1
y1 = 1
for i in range(1, max(a,b)+1):
    if i <= a:
        x0 = x0 * (n - i + 1) % (10**9+7)
        y0 = y0 * i % (10**9+7)
    if i <= b:
        x1 = x1 * (n - i + 1) % (10**9+7)
        y1 = y1 * i % (10**9+7)

ans -= x0*pow_k(y0,10**9+7-2,10**9+7) + x1*pow_k(y1,10**9+7-2,10**9+7)
print(ans % (10**9+7))

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = pow(10,9)+7
bunbo = 1
bunshi = 1
ans = pow(2, n, mod)

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

ans =(ans-bunshi*pow(bunbo, -1,mod)) % mod

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

ans = (ans-bunshi*pow(bunbo, -1,mod)) % mod

print(ans-1)

Submission status: Accepted

Solution code:
def comb_mod(n, r, mod):
    up = 1
    down = 1
    for i in range(r):
        up *= n - i
        up %= mod
        down *= i + 1
        down %= mod
    return ((up * pow(down, mod - 2, mod)) % mod)


def main():
    MOD = 10**9 + 7
    n, a, b = [int(x) for x in input().split()]

    result = pow(2, n, MOD) - 1
    a_cmb = comb_mod(n, a, MOD)
    b_cmb = comb_mod(n, b, MOD)

    result = (result - a_cmb) % MOD
    result = (result - b_cmb) % MOD

    print(result)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def cmb(N, x):
    numerator = 1
    for i in range(N-x+1, N+1):
        numerator = numerator * i % mod
    denominator = 1
    for j in range(1, x+1):
        denominator = denominator * j % mod
    d = pow(denominator, mod-2, mod)
    return numerator * d
 
a = cmb(n, a)
b = cmb(n, b)

total=(pow(2,n)-(1+a+b))%mod

print(total)

Submission status: Accepted

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


def combination(k, r, MOD):
    """kCrを求める"""
    if k < r:
        return 0
    r = min(r, k - r)
    numer, denom = 1, 1
    for l in range(r):
        numer *= (k - l)
        numer %= MOD
        denom *= l + 1
        denom %= MOD
    return numer * pow(denom, MOD - 2, MOD) % MOD


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


all_ptn = pow(2, n, MOD)
a_ptn = combination(n, a, MOD)
b_ptn = combination(n, b, MOD)

ans = (all_ptn - (a_ptn + b_ptn) - 1) % MOD
print(ans)

Submission status: Accepted

Solution code:

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

MAX = 2 * 10 ** 5 + 1
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1

# Inverse
inv = [0] * (MAX + 1)
inv[1] = 1

# Inverse factorial
finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1

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

# Factorial for large
facl = [0] * (MAX + 1)
facl[0] = N
for i in range(1, MAX + 1):
    facl[i] = facl[i - 1] * (N - i) % MOD

# Solution
ans = pow(2, N, MOD) - 1
ans -= facl[A - 1] * finv[A] % MOD
ans %= MOD
ans -= facl[B - 1] * finv[B] % MOD
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys,collections,math
input = sys.stdin.readline

n,a,b = list(map(int,input().split()))
m = 10**9+7
ans = pow(2,n,m)


la  = 1
laa = 1
for i in range(n,n-a,-1):
    la = (la*i)%m
for i in range(1,a+1):
    laa = (laa*i)%m

lb  = 1
lbb = 1
for i in range(n,n-b,-1):
    lb = (lb*i)%m
for i in range(1,b+1):
    lbb = (lbb*i)%m

la = (la*pow(laa,10**9+5,m))%m
lb = (lb*pow(lbb,10**9+5,m))%m

print((ans-la-lb-1)%m)

Submission status: Accepted

Solution code:
def mod_pow(a, n, mod):
    """
    二分累乗法による a^n (mod m)の実装
    :param a: 累乗の底
    :param n: 累乗の指数
    :param mod: 法
    :return: a^n (mod m)
    """

    result = 1
    a_n = a
    while n > 0:
        if n & 1:
            result = result * a_n % mod
        a_n = a_n * a_n % mod
        n >>= 1
    return result


def mod_inverse(a, mod):
    """
    フェルマーの小定理による a^-1 ≡ 1 (mod m)の実装
    aの逆元を計算する
    a^-1 ≡ 1 (mod m)
    a * a^-2 ≡ 1 (mod m)
    a^-2 ≡ a^-1 (mod m)
    :param a: 逆元を計算したい数
    :param mod: 法
    :return: a^-1 ≡ 1 (mod m)
    """

    return mod_pow(a=a, n=mod - 2, mod=mod)


def mod_combination(n, k, mod):
    fact_n = 1
    fact_k = 1
    for i in range(k):
        fact_n *= (n - i)
        fact_n %= mod
        fact_k *= (i + 1)
        fact_k %= mod

    fact_n *= mod_inverse(fact_k, mod)
    return fact_n % mod


N, A, B = map(int, input().split(' '))
MOD = 10 ** 9 + 7

print((mod_pow(2, N, MOD) - 1 - mod_combination(N, A, MOD) - mod_combination(N, B, MOD)) % MOD)

Submission status: Accepted

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

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

bunshi = 1
bunbo = 1

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

ans = (ans - bunshi*pow(bunbo,-1,10**9+7) - 1) % (10**9+7)

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


ans = (ans - bunshi*pow(bunbo,-1,10**9+7)) % (10**9+7)

print(ans)

Submission status: Accepted

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

def combo(n,k):
    c = 1
    for i in range(k):
        c *= n - i
        c %= MOD

    d = 1
    for i in range(1, k+1):
        d *= i
        d %= MOD

    return (c * pow(d, MOD-2, MOD)) % MOD

print((allpair - combo(n, a) - combo(n, b) - 1) % MOD)

Submission status: Accepted

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

MOD = 10**9 + 7

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

#n本からa本を選ぶ→繰り返し二乗法
x = 1
#x=n*(n-1)*...*(n-a+1)
for i in range(n-a+1, n+1):
    x *= i
    x %= MOD
#y=a*(a-1)*...*1
for j in range(1,a+1):
    x *= pow(j,MOD-2,MOD)
    x %= MOD
y = 1
#n本からb本選ぶ(aの時と同じ)
for i in range(n-b+1, n+1):
    y *= i
    y %= MOD
#y=a*(a-1)*...*1
for j in range(1,b+1):
    y *= pow(j,MOD-2,MOD)
    y %= MOD
    
ans -= x + y
ans %= MOD
print(ans)

Submission status: Accepted

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

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


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

Submission status: Accepted

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

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

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

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

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

res = (pow(2,n,mod)-binomial_coefficients_a(n,a)-binomial_coefficients_b(n,b)-1)%mod
print(res if res >= 0 else res+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
    w = w*(i+1)%m
  return (v*pow(w,m-2,m)%m)
print((pow(2,n,m)-1-c(a)-c(b))%m)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
p=10**9+7
q,res=divmod(n,10000)
n1=(2**10000)%p

total = 1
for i in range(q):
  total *= n1
  total %= p
total *= 2**res
total %= p

def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n&1:res=res*a%mod
        a = a * a % mod
        n>>=1
    return res

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

A = 1
for i in range(a//3):
  A = A*modinv((a-3*i)*(a-3*i-1)*(a-3*i-2), p)
  A = A*(n-3*i)*(n-3*i-1)*(n-3*i-2) % p
for j in range(a%3):
  A = A*modinv(a-3*(a//3)-j,p)
  A = A*(n-3*(a//3)-j)%p

B = 1
for i in range(b//3):
  B = B*modinv((b-3*i)*(b-3*i-1)*(b-3*i-2), p)
  B = B*(n-3*i)*(n-3*i-1)*(n-3*i-2) % p
for j in range(b%3):
  B = B*modinv(b-3*(b//3)-j,p)
  B = B*(n-3*(b//3)-j)%p

print((total-A-B-1)%p)

Submission status: Accepted

Solution code:

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

mod = 10**9+7

# (2**n-1)-nCa-nCb

sum_n = pow(2, n, mod)-1
# print(sum_n)
child = 1
mother = 1

for i in range(0, a):
    child *= (n-i)
    child %= mod  # 分子

    mother *= (i+1)
    mother %= mod
# print(mother)
# mod-2はフェルマーの小定理によるchild/mother ->child*(mother**(mod-2)) -2が出てくる理由はhttps://qiita.com/drken/items/3b4fdf0a78e7a138cd9a#3-4-fermat-%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86%E3%81%AB%E3%82%88%E3%82%8B%E9%80%86%E5%85%83%E8%A8%88%E7%AE%97
hate_a = child * pow(mother, mod-2, mod) % mod

child = 1
mother = 1

for i in range(0, b):
    child *= (n-i)
    child %= mod  # 分母

    mother *= (i+1)
    mother %= mod

hate_b = child * pow(mother, mod-2, mod) % mod

print((sum_n-hate_a-hate_b) % mod)

Submission status: Accepted

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

modp = mod

def cmb(n, r, p):
    r = min(r, n-r)
    upper = 1
    for i in range(n, n-r, -1):
        upper = (upper*i)%p
        
    lower = 1
    for i in range(1, r+1):
        lower = (lower*i)%p
    
    # フェルマーの小定理よりp素数ならupper**(p-2)は逆元
    return (upper*pow(lower, p-2, p))%p

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

Submission status: Accepted

Solution code:
N, A, B = [int(_) for _ in input().split()]
MOD = 10 ** 9 + 7
var1 = pow(2, N, MOD) - 1


def f(x):
    f1 = 1
    for i in range(N - x + 1, N + 1):
        f1 = (f1 * i) % MOD

    # 逆元
    f2 = 1
    for i in range(2, x + 1):
        f2 = (f2*i)%MOD
    f2 = pow(f2, MOD - 2, MOD)
    return (f1 * f2) % MOD


ans = var1 - f(A) - f(B)
print(ans % MOD)

Submission status: Accepted

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

mod = 10**9+7

ans = 1
r = 2
m = n
while(True):
    if(m%2 == 1):
        ans *= r
        ans %= mod
    r = r**2
    r %= mod
    m = m//2
    if(m == 0):
        break

a = max(a,n-a)
b = max(b,n-b)
base = []
rbase = [0,1]
c = min(a,b)
d = max(a,b)

bas = 1
for i in range(n,c,-1):
    bas *= i
    bas %= mod
    base.append(bas)

#0からn-cまでの逆元
rbase = [0,1]
for i in range(2,n-c+1):
    q = mod//i
    r = mod % i
    rbase.append(-q * rbase[r] % mod)
rbases = []
rbas = 1
for i in range(1,n-c+1):
    rbas *= rbase[i]
    rbas %= mod
    rbases.append(rbas)

a_ = base[n-c-1]*rbases[n-c-1]%mod
if(d == n):
    b_ = 1
else:
    b_ = base[n-d-1]*rbases[n-d-1]%mod
print((ans - a_ - b_ - 1)%mod)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = int(1e9) + 7
temp = pow(2, n, mod) - 1
fa, fb = 1, 1
tempa, tempb = 1, 1
for i in range(1, a+1):
    fa *= i
    fa %= mod

    tempa *= (n - i + 1)
    tempa %= mod
for i in range(1, b+1):
    fb *= i
    fb %= mod
    tempb *= (n - i + 1)
    tempb %= mod

a_t = tempa * pow(fa, mod-2, mod) % mod
b_t = tempb * pow(fb, mod-2, mod) % mod
ans = (temp - a_t - b_t) % mod
print(ans)

Submission status: Accepted

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

def comb(n, k):
    nCk = 1


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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, A, B = [int(_) for _ in input().split()]
mod = 10**9 + 7
c = [1, N]
for i in range(1, B + 1):
    c += [c[-1] * (N - i) * pow(i + 1, mod - 2, mod) % mod]
ans = pow(2, N, mod) - c[A] - c[B] - 1
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

mod = 10**9+7

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

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

def comb(n, k):
    c = 1
    for i in range(k):
        c *= n - i
        c %= mod

    d = 1
    for i in range(1, k + 1):
        d *= i
        d %= mod

    return (c * pow(d, mod - 2, mod)) % mod

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

Submission status: Accepted

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

MOD = 10**9 + 7

def comb(n, r, mod):
    if r > n-r:
        r = n - r
    
    res_X = 1
    for i in range(n-r+1, n+1):
        res_X = (res_X * i)%mod
    
    res_Y = 1
    for i in range(1, r+1):
        res_Y = (res_Y * i)%mod
    
    return (res_X * pow(res_Y, mod-2, mod))%mod

base = (pow(2, n, MOD) - 1)%MOD
a = comb(n, a, MOD)
b = comb(n, b, MOD)

print((base - a - b)%MOD)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

mod = 10**9+7

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

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

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

    return c

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

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
mod=10**9+7
def comb(n,k,mod):
  if k>n-k:
    k=n-k
  c=1
  for i in range(n-k+1,n+1):
    c*=i
    c%=mod
  d=1  
  for i in range(1,k+1):
    d*=i
    d%=mod
  return (c*pow(d,mod-2,mod))%mod

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

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def com_once(n, r, MOD):
    if n < r or n < 0 or r < 0:
        return 0
    r = min(r, n - r)
    numer = denom = 1
    for i in range(r):
        numer = numer * (n - i) % MOD
        denom = denom * (i + 1) % MOD
    return numer * pow(denom, MOD - 2, MOD) % MOD


def main():
    n, a, b = map(int, read().split())

    ans = (pow(2, n, MOD) - com_once(n, a, MOD) - com_once(n, b, MOD) - 1) % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 10**9+7

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

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

    d = 1
    for i in range(1, r+1):
        d *= i
        d %= mod

    return (c * pow(d, mod-2, mod)) % mod

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

ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def mod_com_once(n, r, MOD):
    if n < r or n < 0 or r < 0:
        return 0
    r = min(r, n - r)
    numer = denom = 1
    for i in range(n - r + 1, n + 1):
        numer = numer * i % MOD
    for i in range(1, r + 1):
        denom = denom * i % MOD
    return numer * pow(denom, MOD - 2, MOD) % MOD


def main():
    n, a, b = map(int, read().split())

    ans = (pow(2, n, MOD) - mod_com_once(n, a, MOD) - mod_com_once(n, b, MOD) - 1) % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()