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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,a,b=MI()
    M=2*(10**5) + 5
    def cmb(n, r):
        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
        
    ans=pow(2,N,mod)-1
    ans-=cmb(N,a)
    ans-=cmb(N,b)
    
    print(ans%mod)

main()

Submission status: Accepted

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

# 二項係数 mod [検索]
mmm = 1000000000 + 7
fac = []
inv = []
inv_fac = []
def init(n):
    fac.append(1)
    fac.append(1)
    inv.append(0)
    inv.append(1)
    inv_fac.append(1)
    inv_fac.append(1)
    for i in range(2, n):
        fac.append(fac[-1] * i % mmm)
        inv.append(mmm - inv[mmm%i] * (mmm // i) % mmm)
        inv_fac.append(inv_fac[-1] * inv[-1] % mmm)

def choice(a, b):
    if a < b:
        return 0
    v = 1
    for i in range(b):
        v = (v * (a-i)) % mmm  # 偶然通っていたけどここはnではなくa (eの途中で気づいた)
    return v * inv_fac[b]

init(int(2e5) + 1)


ans = pow(2, n, mmm) - 1  # v, e, mod
bunshi = 1
for i in range(a):
    bunshi = (bunshi * (n-i)) % mmm
ans -= choice(n, a)
ans -= choice(n, b)
print(ans % mmm)

'''
4, 1, 3 => 4c2 + 4c4 -> 6+1 = 7
4 + 6 + 4 + 1 - 4c1 - 4c2 
1        1
11       2
121      4
1331     8
14641   16, 0が無いので-1, 大きい combination -> 二項係数 mod [検索]
'''

Submission status: Accepted

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

factinv = [1, 1]
inv = [0, 1]

for i in range(2, 10**6):
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

def comb(n, k):
    cmb = 1
    for i in range(n-k+1, n+1):
        cmb = cmb * i % p
    return cmb * factinv[k]


print(((2 ** N - 1) % p - comb(N, a) % p - comb(N, b) % p) % p)

Submission status: Accepted

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

# 二項係数 mod [検索]
mmm = 1000000000 + 7
fac = []
inv = []
inv_fac = []
def init(n):
    fac.append(1)
    fac.append(1)
    inv.append(0)
    inv.append(1)
    inv_fac.append(1)
    inv_fac.append(1)
    for i in range(2, n):
        fac.append(fac[-1] * i % mmm)
        inv.append(mmm - inv[mmm%i] * (mmm // i) % mmm)
        inv_fac.append(inv_fac[-1] * inv[-1] % mmm)

def choice(a, b):
    if a < b:
        return 0
    v = 1
    for i in range(b):
        v = (v * (n-i)) % mmm
    return v * inv_fac[b]

init(int(2e5) + 1)


ans = pow(2, n, mmm) - 1  # v, e, mod
bunshi = 1
for i in range(a):
    bunshi = (bunshi * (n-i)) % mmm
ans -= choice(n, a)
ans -= choice(n, b)
print(ans % mmm)

'''
4, 1, 3 => 4c2 + 4c4 -> 6+1 = 7
4 + 6 + 4 + 1 - 4c1 - 4c2 
1        1
11       2
121      4
1331     8
14641   16, 0が無いので-1, 大きい combination -> 二項係数 mod [検索]
'''

Submission status: Accepted

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

mod = 1000000007

def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

def inv(x):
    return pow(x, mod - 2)

def cmb(n, k):
    ret = 1
    for i in range(k):
        ret = (ret * (n - i) * inv(i + 1)) % mod
    return ret

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

def nCk(n, k):
    if k > n or min(n, k) < 0:
        raise Exception('Not correct input values!')
    res = 1
    for i in range(1, k + 1):
        res = (res * (n - i + 1) * pow(i, MOD - 2, MOD)) % MOD
    return res

n, a, b = map(int, input().split())
ret = (pow(2, n, MOD) - 1 - nCk(n, a) - nCk(n, b)) % MOD
print(ret)

Submission status: Accepted

Solution code:
import math

def main():
	n, a, b = [int(x) for x in input().split(" ")]
	# 2^n - 1 - nCa - nCb
	p = 1000000007
	a = min([a, n - a])
	b = min([b, n - b])
	M = max([a, b])
	f = [1, 1]
	finv = []
	for i in range(M):
		f.append((f[-1] * (i + 2)) % p)
	lf = len(f)
	finv.append(modpower(f[-1], p - 2, p))
	for i in range(lf - 1):
		finv.append((finv[-1] * (lf - i - 1)) % p)
	na = 1
	nb = 1
	for i in range(M):
		if a > i:
			na = (na * (n - i)) % p
		if b > i:
			nb = (nb * (n - i)) % p
	print((modpower(2, n, p) - 1 - (na * finv[lf - 1 - a]) % p - (nb * finv[lf - 1 - b]) % p) % p)


def modpower(a, p, d): # a^p % d
	pp = [a]
	for i in range(int(math.log2(p)) + 1):
		pp.append((pp[-1] ** 2) % d)
	b_p = format(p, 'b')
	m = 1
	for i in range(len(b_p)):
		if b_p[-i-1] == "1":
			m = (m * pp[i]) % d
	return m

main()

Submission status: Accepted

Solution code:
#より高速に
def pow(x, n ,p):
    """
    O(log n)
    """
    if n == 0:
        return 1

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

    return (K * x) % p




def cmb3(n,r,q):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)    
    s = 1
    for x in range(n,n-r,-1):
        s = (s*x) % q
    t = 1
    for x in range(1,r+1):
        t = (t*x) % q

    #割る数の剰余をどうするかが問題
    u = pow(t,q-2,q)
    return (u * s) % q
  
n,a,b = map(int,input().split())
A = pow(2,n,10**9+7)

if a <= n:
  B = cmb3(n,a,10**9+7)
else:
  B = 0
if b <= n:
  C = cmb3(n,b,10**9+7)
else:
  C = 0

print((A-B-C-1)%(10**9+7))

Submission status: Accepted

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


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


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


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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Sep 13 19:51:37 2020

@author: liang
"""

import math

key = 10**9 + 7

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

ans = 1
tmp = 2
N = math.ceil(math.log2(n))

#繰り返し二乗法
for i in range(N+1):
    if n>>i&1 == 1:
        #print(i,tmp)
        ans *= tmp
    tmp *= tmp
    tmp %= key
    ans %= key
ans -= 1
#print("1",ans)

def comb(r):
    #permutation
    perm = 1
    for i in range(0,r):
        perm *= n - i
        perm %= key
    
    #factorial
    fact = 1
    for i in range(1,r+1):
        fact *= i
        fact %= key
    
    ans = 1
    tmp = fact
    p = key -2
    N = math.ceil(math.log2(p))
    #繰り返し二乗法
    for i in range(N):
        if  p >>i&1 == 1:
            #print(i,tmp)
            ans *= tmp
        tmp *= tmp
        tmp %= key
        ans %= key
    ans *= perm
    ans %= key
    return ans

ans -= comb(a)
ans -= comb(b)
ans %= key
#print("2",comb(a))
#print("3",comb(b))
print(ans)

Submission status: Accepted

Solution code:
def ncr(n, r, p):
    num = 1
    den = 1

    for i in range(r):
        num = (num*(n-i)) % p
        den = (den*(i+1)) % p

    return (num*pow(den, p-2, p)) % p

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

m = 1000000007
print((pow(2, n, m) - 1 - ncr(n, a, m) - ncr(n, b, m)) % m)

Submission status: Accepted

Solution code:
def main():
    #input data
    import sys
    input = lambda:sys.stdin.readline().strip()
    
    N,A,B = map(int,input().split())
    mod=10**9+7
    #solve
    #二項係数の和=2**n
    #2**n-1-nCa-nCb
    def pow(x, y, mod):
        res = 1
        if y > 0:
            res = pow(x, y // 2, mod)
            if y % 2 == 0:
                res = (res * res) % mod
            else:
                res = (((res * res) % mod) * x) % mod
        return res
        
    def cmb(n, r, mod=10**9+7):
        c = 1
        m = 1
        r = min(n - r, r)
        for i in range(r):
            c = c * (n - i) % mod
            m = m * (i + 1) % mod
        return c * pow(m, mod - 2, mod) % mod
                
    ans = pow(2,N,mod)-1-cmb(N,A,mod)-cmb(N,B,mod)
    print(ans%mod)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    #input data
    import sys
    input = lambda:sys.stdin.readline().strip()
    
    N,A,B = map(int,input().split())
    mod=10**9+7
    #solve
    #二項係数の和=2**n
    #2**n-1-nCa-nCb
    
    def cmb(n, r, mod=10**9+7):
        c = 1
        m = 1
        r = min(n - r, r)
        for i in range(r):
            c = c * (n - i) % mod
            m = m * (i + 1) % mod
        return c * pow(m, mod - 2, mod) % mod
                
    ans = pow(2,N,mod)-1-cmb(N,A,mod)-cmb(N,B,mod)
    print(ans%mod)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    #input data
    import sys
    input = lambda:sys.stdin.readline().strip()
    
    N,A,B = map(int,input().split())
    mod=10**9+7
    #solve
    #二項係数の和=2**n
    #2**n-1-nCa-nCb
    def cmb(n, r, mod=10**9+7):
        r = min(r, n-r)
        res = 1
        for i in range(r):
            res = res * (n - i) * pow(i+1, mod-2, mod) % mod
        return res
                
    ans = pow(2,N,mod)-1-cmb(N,A,mod)-cmb(N,B,mod)
    print(ans%mod)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    #input data
    import sys
    input = lambda:sys.stdin.readline().strip()
    
    N,A,B = map(int,input().split())
    mod=10**9+7
    #solve
    #二項係数の和=2**n
    #2**n-1-nCa-nCb
    def modinv(a, mod=10**9+7):
        return pow(a, mod-2, mod)
    def cmb(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 = pow(2,N,mod)-1-cmb(N,A,mod)-cmb(N,B,mod)
    print(ans%mod)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import functools
import operator

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

def nCr(n, r):
    r = min(r, n-r)
    if r == 0:
        return 1
    num = functools.reduce(lambda x, y: x*y%mod, range(n, n-r, -1))
    den = functools.reduce(lambda x, y: x*y%mod, map(lambda x: pow(x, mod-2, mod), range(1, r+1)))
    return num * den % mod

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
mod = 10**9+7
def cmb(x, y):
  ret = 1
  for i in range(1, y+1):
    ret = (ret * (x+1-i)) % mod
    ret = (ret * pow(i, mod-2, mod)) % mod
  return ret

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

Submission status: Accepted

Solution code:
# ABC156 D

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



def nCr_init(L,p):
    for i in range(L+1):
        if i<=1:
            inv[i]=1
        else:
            inv[i]=(p-inv[p%i]*(p//i))%p


def pow_k(x,n,p=10**9+7):
    if n==0:
        return 1
    K=1
    while n>1:
        if n%2!=0:
            K=(K*x)%p
        x=(x*x)%p
        n//=2
    return (K*x)%p


nck=[0]*(b+10)
inv=[1]*(b+15)
nck[0]=1

nCr_init(b+10,p)
for i in range(b+5):
    nck[i+1]=(nck[i]*(n-i)*inv[i+1])%p

print((pow_k(2,n,p)-nck[a]-nck[b]-1)%p)

Submission status: Accepted

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

mod = 10**9+7

all_combi = pow(2,n,mod)




p = 1
q = 1

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

        
ans = all_combi -nca -ncb -1
ans %= (10**9+7)
    
print(ans)

Submission status: Accepted

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

mod = 10**9+7

all_combi = pow(2,n,mod)




p = 1
q = 1

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

        
ans = all_combi -nca -ncb -1
ans %= (10**9+7)
    
print(ans)

Submission status: Accepted

Solution code:
def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = 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 nCk(N, k, mod):
    ret_val = 1
    for i in range(k):
        ret_val *= (N - i)
        ret_val %= mod
        ret_val *= modinv(i + 1, mod)
        ret_val %= mod
    return ret_val


n, a, b = map(int, input().split())
MOD = 10 ** 9 + 7
all_cnt = pow(2, n, MOD) - 1
a_cnt = nCk(n, a, MOD)
b_cnt = nCk(n, b, MOD)
ans = all_cnt - a_cnt - b_cnt
print(ans % MOD)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
import bisect
from functools import reduce
def main():
    def comb(n, r):
        numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
        denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
        return numerator * pow(denominator, mod - 2, mod) % mod

    mod = 10 ** 9 + 7
    N, A, B = MI()
    p = pow(2, N, mod) - 1
    a = comb(N, A)
    b = comb(N, B)
    ans = (p - a - b) % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

mod = 10**9 + 7

def nck(k):
    y, z = 1, 1
    for i in range(1, k+1):
        y = (y * (n+1-i)) % mod
        z = (z * pow(i, mod-2, mod)) % mod
    return (y*z) % mod

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

Submission status: Accepted

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

from functools import lru_cache

MOD = 10**9+7
fact = [1]
fact_inv = [1]
fact_rev = [1]

for i in range(1, max(a,b)+1):
    fact.append(fact[i-1] * i % MOD)
    fact_inv.append(pow(fact[i], MOD-2, MOD))
    fact_rev.append(fact_rev[i-1] * (n-i+1) % MOD)

@lru_cache(maxsize=None)
def combi(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fact_rev[n] * fact_inv[k] % MOD

pattern = pow(2, n, MOD) - 1 
if a==b:
    pattern -= (combi(a, a))
else:
    pattern -= (combi(a, a) + combi(b, b))

print(pattern%MOD)

Submission status: Accepted

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

def genCombinationFunction(max_k,mod):
    modinv_table = [-1] * (max_k+1)
    modinv_table[1] = 1
    for i in range(2, max_k+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
    return binomial_coefficients

  
max_k = 2 * 10 ** 5
mod = 10**9 + 7
f=genCombinationFunction(max_k,mod)


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

Submission status: Accepted

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

# In[1]:


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


# In[2]:


def nCk(n, k, mod):
    a = 1
    for i in range(n, n-k, -1):
        a *= i
        a %= mod
    b = 1
    for i in range(1, k+1):
        b *= i
        b %= mod
    a *= pow(b, mod-2, mod)
    return a


# In[3]:


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


# In[ ]:

Submission status: Accepted

Solution code:
def main():
    n, a, b = map(int, input().split())
    mod = 10 ** 9 + 7 #素数
    
    def modpow(x, n, mod):
        res = 1
        while n:
            if n % 2:
                res *= x % mod
            x *= x % mod
            n >>= 1
        return res
    
    def cmb(n, r, mod):
        # 分子(n*(n-1)*...*(n-r+1))
        nume = 1
        for i in range(n-r+1, n+1):
            nume = nume * i % mod
        # 分母（1*2*...*r）
        deno = 1
        for j in range(1, r+1):
            deno = deno * j % mod
        d = modpow(deno, mod-2, mod)
        return nume * d % mod
    
    all_cmb = pow(2, n, mod) - 1
    bad_a = cmb(n, a, mod)
    bad_b = cmb(n, b, mod)    
    print((all_cmb-bad_a-bad_b) % mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

mod=10**9+7

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

na=1
nb=1

ansa=1
ansb=1

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

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

ans-=ansa
ans-=ansb

ans%=mod


print(ans)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
mod=1000000007
c=[1]*(b+1)
def com(n,b):
    for i in range(1,b+1):
        c[i]=c[i-1]*((n-i+1)*pow(i,mod-2,mod))%mod
com(n,b)
ans=(pow(2,n,mod)-c[a]-c[b]-1)%mod

print(ans)

Submission status: Accepted

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

mod = 10**9 + 7

ans = pow(2, n, mod)

ans -= 1

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

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

ans = (ans - aa - bb) % mod

print(ans)

Submission status: Accepted

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

C = n
ans = 0
if a == 1: Ca = n
for r in range(1, n + 1):
    C = (((C * (n - r)) % mod )* pow(r + 1, mod - 2, mod)) % mod
    if r == a - 1:
        Ca = C
    if r == b - 1:
        Cb = C
        break

print((pow(2, n, mod) - Ca - Cb - 1) % mod)

Submission status: Accepted

Solution code:
N,A,B=map(int,input().split())
M=10**9+7

def cmb(N,R,M):
    C=[1]*(R+1)
    for i in range(1,R+1):
        C[i]=(C[i-1]*(N+1-i)*pow(i,M-2,M))%M
    return C

C=cmb(N,B,M)
ans=pow(2,N,M)-1
ans-=C[A]+C[B]
print(ans%M)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

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

    def comb_mod(n, r):
        res = 1
        r = min(n - r, r)

        for i in range(r):
            res *= (n - i)
            res %= MOD
            res *= pow((r - i), MOD - 2, MOD)

        return res

    ans -= comb_mod(N, a)
    ans -= comb_mod(N, b)
    ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
def fact(n,p):
    a=1
    for i in range(1,n+1):
        a=(a*i)%p
    return a
def bfact(n,x,p):
    a=1
    for i in range(n-x+1,n+1):
        a=(a*i)%p
    return a
p=10**9+7
na=bfact(n,a,p)%p
nb=bfact(n,b,p)%p
aa=fact(a,p)%p
bb=fact(b,p)%p
aaa=pow(aa,-1,p)
bbb=pow(bb,-1,p)
ans=pow(2,n,p)-1
ans-=(na*aaa+nb*bbb)
print(ans%p)

Submission status: Accepted

Solution code:
max_n=10**6
mod=10**9+7

inv=[1,1]
inv_frac=[1,1]
for i in range(2,max_n):
  inv.append((mod-inv[mod%i]*(mod//i))%mod)
  inv_frac.append((inv_frac[-1]*inv[-1])%mod)


n,a,b=map(int,input().split())
s=pow(2,n,mod)
ca=inv_frac[a]
for i in range(a):
  ca=(ca*(n-i))%mod

cb=inv_frac[b]
for i in range(b):
  cb=(cb*(n-i))%mod
print((s-ca-cb-1)%mod)

Submission status: Accepted

Solution code:
#powは繰り返し2乗法により指数計算を行う関数
mod=10**9+7
n,a,b=map(int,input().split())

ans=pow(2,n,mod)-1 #n種類の花を使って花束を作る総数は2^n-1通り

comb1=1 #nCaの計算
for i in range(n-a+1,n+1): #n*(n-1)*…*(n-a+1)を計算
    comb1*=i
    comb1%=mod
for i in range(1,a+1): #1/a!=1/(1*2*…*a)=1^(p-2)*2^(p-2)*…*a^(p-2) (p=10**9+7)を計算
    comb1*=pow(i,mod-2,mod) # iの逆元 →　1/iした際に かける(iの逆元)とすればあまりが求まる
    comb1%=mod

comb2=1
for i in range(n-b+1,n+1): #n*(n-1)*…*(n-b+1)を計算
    comb2*=i
    comb2%=mod
for i in range(1,b+1): #1/b!=1/(1*2*…*b)=1^(p-2)*2^(p-2)*…*b^(p-2) (p=10**9+7)を計算
    comb2*=pow(i,mod-2,mod)
    comb2%=mod

ans-=(comb1+comb2) #nCa、nCbを総数から引く
ans%=mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

ans = pow(2,n,MOD)-1
a,b = min(a,b),max(a,b)

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

print(ans)

Submission status: Accepted

Solution code:
def modpow(a, n, p):
    if n == 1:
        ans = a % p
    else:
        if n % 2 == 0:
            ans = (modpow(a, n // 2, p) ** 2) % p
        else: # n % 2 == 1
            ans = (a * (modpow(a, n // 2, p) ** 2)) % p

    return ans

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

tot = modpow(2, n, p)

Xa, Ya = 1, 1
for i in range(a):
    Xa = (Xa * (n - i)) % p
    Ya = (Ya * (i + 1)) % p
Za = modpow(Ya, p - 2, p)
nCa = (Xa * Za) % p

Xb, Yb = 1, 1
for i in range(b):
    Xb = (Xb * (n - i)) % p
    Yb = (Yb * (i + 1)) % p
Zb = modpow(Yb, p - 2, p)
nCb = (Xb * Zb) % p

ans = (tot - nCa -nCb - 1) % p

print(ans)

Submission status: Accepted

Solution code:
MOD = 1_000_000_007
def calc_combi(n,k):
    frac=1
    denomi=1
    for i in range(n-k+1,n+1):
        frac=frac*i%MOD
    for i in range(1,k+1):
        denomi=denomi*i%MOD
    return frac*pow(denomi,MOD-2,MOD)

n, a, b = map(int,input().rstrip().split())
nca = calc_combi(n,a)
ncb = calc_combi(n,b)
print((pow(2,n,MOD)-1-nca-ncb)%MOD)

Submission status: Accepted

Solution code:
def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = 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 nCk(N, k, mod):
    ret_val = 1
    for i in range(k):
        ret_val *= (N - i)
        ret_val %= mod
        ret_val *= modinv(i + 1, mod)
        ret_val %= mod
    return ret_val


n, a, b = map(int, input().split())
MOD = 10 ** 9 + 7
all_cnt = pow(2, n, MOD) - 1
a_cnt = nCk(n, a, MOD)
b_cnt = nCk(n, b, MOD)
ans = all_cnt - a_cnt - b_cnt
while ans < 0:
    ans += MOD
print(ans)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
def POW(x, y):
  bin_ = []
  while y:
    bin_.append(y % 2)
    y >>= 1
  ret = 1
  for j in reversed(bin_):
    ret = (ret * ret) % mod
    if j == 1:
      ret = (ret * x) % mod
  return ret
def comb(x, y):
  ret = 1
  for i in range(1, y+1):
    ret = (ret * (x+1-i)) % mod
    ret = (ret * POW(i, mod-2)) % mod
  return ret
print((POW(2, n) - 1 - comb(n, a) - comb(n, b)) % mod)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

# C,Pを求める前処理
m = 2*10**5+10
mod = 10**9 + 7


fact = [0]*(m+5)
fact_inv = [0]*(m+5)
inv = [0]*(m+5)

fact[0] = fact[1] = 1
fact_inv[0] = fact_inv[1] = 1
inv[1] = 1

for i in range(2,m+5):
    fact[i] = fact[i-1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod


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

print((pow(2,N,mod)-1-cmb_large(N,a,mod)-cmb_large(N,b,mod)) % mod)

Submission status: Accepted

Solution code:
import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def nCr(n, r):
    a, b = 1, 1
    for i in range(r):
        a = a * (n - i) % MOD
        b = b * (i + 1) % MOD
    
    return a * pow(b, MOD - 2, MOD) % MOD

def Main():
    n, a, b = read_ints()
    num = pow(2, n, MOD) - 1

    print((num - nCr(n, a) - nCr(n, b)) % MOD)   

if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
mod = 1000000007

def mod_cmb(n: int, k: int, p: int) -> int:
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if (k > n - k):
        return mod_cmb(n, n - k, p)
    c = d = 1
    for i in range(k):
        c *= (n - i)
        d *= (k - i)
        c %= p
        d %= p
    return c * pow(d, -1, p) % p

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

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

    tmp_a = mod_cmb(n , a, mod)
    tmp_b = mod_cmb(n , b, mod)

    print((ans-tmp_a-tmp_b)%mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    from math import factorial

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

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

    print(max(0, (pow(2, n, mod) - ((calc(a) + calc(b)) % mod) - 1) % mod))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def nCk(n, k):
    a = 1
    for i in range(n, n-k, -1):
        a *= i
        a %= mod
    b = 1
    for i in range(1, k+1):
        b *= i
        b %= mod
    a *= pow(b, mod-2, mod)
    return a

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

Submission status: Accepted

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

def nCr(n, r):
    global mod
    ans = 1
    for i in range(r):
        ans = (ans * (n-i)) % mod
    return (ans * pow(factorial(r), mod-2, mod)) % mod

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

Submission status: Accepted

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

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

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

for i in range(1, b+1):
    c2 *= pow(i, mod-2, mod)
    c2 %= mod
    
res -= (c1+c2)
res %= mod
print(res)

Submission status: Accepted

Solution code:
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 power_func(a,n,p):
    bi = str(format(n,"b"))#2進表現に
    res = 1
    for i in range(len(bi)):
        res = (res*res) %p
        if bi[i] == "1":
            res = (res*a) %p
    return res



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

print((power_func(2,n,mod)-1-combination(n, a, mod)-combination(n, b, mod))%mod)

Submission status: Accepted

Solution code:
def pow(a,b,c):
    ans = 1
    while b > 0:
        if b & 1:
            ans = ans*a % c
        a = a*a % c
        b = b >> 1
    return ans
def cmb(a,b,c):
    b = min(b,a-b)
    num = 1
    for i in range(b):
        num = num*(n-i) % c
    den = 1
    for i in range(b):
        den = den*(i+1) % c
    return num*pow(den,c-2,c) % c
mod = 10**9+7
n,a,b = map(int,input().split())
ans  = (pow(2,n,mod)-cmb(n,a,mod)-cmb(n,b,mod)-1) % mod
if ans < 0:
    ans = ans + mod
print(ans)