Problem:


Score : 400 points

Problem Statement

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

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

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

How many different bouquets are there that Akari can make?

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

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

Constraints

All values in input are integers.

2 \leq n \leq 10^9

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

Input

Input is given from Standard Input in the following format:

n a b

Output

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

Sample Input 1

4 1 3

Sample Output 1

7

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

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

Sample Input 2

1000000000 141421 173205

Sample Output 2

34076506

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



Sample input:
4 1 3


Sample output:
7

Submission status: Accepted

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

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

ans = pow(2,n,mod)-1-minus(n,a)-minus(n,b)
while ans<0:
    ans+=mod
print(ans)

Submission status: Accepted

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

def calculate_combination(n,k):
    x,y=1,1
    for i in range(k):
        x=x*(n-i)%MOD
        y=y*(k-i)%MOD
    return x*pow(y,MOD-2,MOD)%MOD

ans=pow(2,N,MOD)-1-calculate_combination(N,A)-calculate_combination(N,B)
while ans<0:
    ans+=MOD
print(ans)

Submission status: Accepted

Solution code:
def mpow(x, n):
    result = 1
    while n != 0:
        if n & 1 == 1:
            result *= x
            result %= 1000000007
        x *= x
        x %= 1000000007
        n >>= 1

    return result

def mcomb(n, k):
    a = 1
    b = 1
    for i in range(k):
        a *= n - i
        a %= 1000000007
        b *= i + 1
        b %= 1000000007

    return a * mpow(b, 1000000005) % 1000000007

def main():
    n, a, b = map(int, input().split())
    
    ans = mpow(2, n) - mcomb(n, a) - mcomb(n, b) - 1

    print(ans%1000000007)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
def cmb(n,k):
    x,y = 1,1
    for i in range(k):
        x = x * (n-i) % mod
        y = y * (k-i) % mod
    return x * pow(y, mod-2, mod) % mod
mod = 10**9+7
All = pow(2, n, mod)-1
ac = cmb(n, a)
bc = cmb(n, b)
ans = (All-ac-bc)%mod
print(ans)

Submission status: Accepted

Solution code:
def modinv(a, mod):
    b = mod
    u = 1
    v = 0
    while(b):
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u

    u %= mod
    return u


def modcmb(n, r, mod):
    X = 1
    for i in range(n-r+1, n+1):
        X = X * i % mod

    Y = 1
    for i in range(1, r+1):
        Y = Y * i % mod
        
    res = X * modinv(Y, mod) % mod
    return res


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

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

Submission status: Accepted

Solution code:
def modinv(a, mod):
    b = mod
    u = 1
    v = 0
    while(b):
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u

    u %= mod
    return u


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 modcmb(n, r, mod):
    X = 1
    for i in range(n-r+1, n+1):
        X = X * i % mod

    Y = 1
    for i in range(1, r+1):
        Y = Y * i % mod
        
    res = X * modinv(Y, mod) % mod
    return res


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

print((modpow(2, n, mod) - 1 - modcmb(n, a, mod) - modcmb(n, b, mod)) % mod)

Submission status: Accepted

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

def comb(n,a):
    x = 1
    for i in range(n-a+1, n+1):
        x *= i
        x %= mod
    y = 1
    for i in range(1, a+1):
        y *= i
        y %= mod
    return x*pow(y, mod-2, 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())
M=10**9+7

def comb(n,a):
    X = 1
    for i in range(n-a+1,n+1):
        X = X*i%M
    Y = 1
    for i in range(1,a+1):
        Y = Y*i%M
    return X*pow(Y,M-2,M)
    
ans = pow(2,n,M)-1-comb(n,a)-comb(n,b)
print(ans%M)

Submission status: Accepted

Solution code:
def combination(n,r,mod=10**9+7):
    n1 = n+1
    r = min(r,n-r)
    numer = denom = 1
    for i in range(1,r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom,mod-2,mod) % mod
 
mod = int(1e9+7)
n,a,b= map(int,input().split())
 
S = (pow(2,n,mod) - 1)%mod
A = combination(n,a)
B = combination(n,b)
ans = (S-A-B)%mod
 
print(ans)

Submission status: Accepted

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

mod = 10 ** 9 + 7
MAX = 2 * 10 ** 5

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

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

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


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

    return ret


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

Submission status: Accepted

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

# 乗法のmod逆元 (mod-2乗)
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

# nCr mod m
# modinvが必要
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    x = 1
    y = 1
    for i in range(r):
        x *= (n - i)
        y *= (i + 1)
        x %= mod
        y %= mod
    return (x * modinv(y, mod)) % mod

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

print(ans % mod)

Submission status: Accepted

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

# 乗法のmod逆元 (mod-2乗)
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

# nCr mod m
# modinvが必要
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

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

print(ans % mod)

Submission status: Accepted

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

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

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

Submission status: Accepted

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


def combination(n, r, mod=10**9+7):
    """
    nCr mod m
    """
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


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

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

__MAX_N = 300000
fac = [0] * __MAX_N
finv = [0] * __MAX_N
inv = [0] * __MAX_N

def combinit(m):
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1

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

def modpow(n, p, m):
	if p == 0:
		return 1
	if p % 2 == 0:
		t = modpow(n, p // 2, m)
		return t * t % m
	return n * modpow(n, p - 1, m) % m

def comb(n, k, m):
    if n == 0 and k == 0:
        return 1
    if n < k or n < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % m) % m

def comb2(n, k, m):
    if n == k or k == 0:
        return 1
    if n < k:
        return 0

    res = 1
    for i in range(k):
        res *= (n - i)
        res %= m
        res *= modpow(i + 1, m - 2, m)
        res %= mod
    
    return res

n, a, b = na()
ans = modpow(2, n, mod) - 1
ans -= comb2(n, a, mod)
ans -= comb2(n, b, mod)
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#TLE

#comb_mod(n, r, mod) = nCr % mod
def comb_mod(n, r, mod):
    ans = 1
    if r <= n/2:
        for i in range(n-r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    else:
        for i in range(r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, n-r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    return ans

n, a, b = map(int, input().split())
ans = pow(2, n, 10**9+7) - comb_mod(n, a, 10**9+7) - comb_mod(n, b, 10**9+7) - 1
if ans < 0:
    ans += 10**9 + 7
if ans < 0:
    ans += 10**9 + 7

print(int(ans))

Submission status: Accepted

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
#import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

#nが大きいがa,bが小さいので、a,bを個別に計算する

def main():
  n, a, b = map(int, readline().split())
  def nCr(r):
    bunshi = 1
    bunbo = 1
    for i in range(r):
      bunshi = (bunshi * (n-i)) % MOD
      bunbo = (bunbo * (i+1)) % MOD
    return bunshi * pow(bunbo, MOD - 2, MOD) % MOD
  
  if n==2:
    print(0)
  else:
    total = pow(2, n, MOD) %MOD
    nca = nCr(a)
    ncb = nCr(b)
    ans = (total-nca-ncb-1)%MOD
    print(int(ans))
  
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

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

    res = (2**n - 1)%mod
    x = nCr(n, a, mod)
    y = nCr(n, b, mod)
    print((res-x-y)%mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

#制限なしで全ての花束の作り方
wa = pow(2, n, 10 ** 9 + 7) - 1

#a本の花束の作り方
#val1 = comb(n, a, exact=True)
#val2 = comb(n, b, exact = True)

x = 1
y = 1
for i in range(a):
    x = (x * (n-i)) % (10 ** 9 + 7)
    y = (y * (i+1)) % (10 ** 9 + 7)
val1 = (x * pow(y, 10 ** 9 + 7 - 2, 10 ** 9 + 7)) % (10 ** 9 + 7)

x = 1
y = 1
for i in range(b):
    x = (x * (n-i)) % (10 ** 9 + 7)
    y = (y * (i+1)) % (10 ** 9 + 7)

val2 = (x * pow(y, 10 ** 9 + 7 - 2, 10 ** 9 + 7)) % (10 ** 9 + 7)

ans = wa - val1 - val2
for i in range(100):
    if ans < 0:
        ans += 10 ** 9 + 7
print(ans)

Submission status: Accepted

Solution code:
def modpow(a,n,p):
    l = len(bin(n))-2
    res = 1
    for i in range(l):
        if n>>i &1:
            res = (res*a) % p
        a = (a**2) % p
    return res

def ncr_1(n,r,p):##　n>>r の場合のncr　O(r)
    x = 1
    y = 1
    for i in range(r):
        x*=(n-i)
        y*=(i+1)
        x%=p
        y%=p
    return x*modinv(y,p) %mod

def modinv(a,p):
    b,u,v = p,1,0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -=t*v
        u,v = v,u
    u %=p
    return u


nmax = 10**6
mod = 10**9+7

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

Submission status: Accepted

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

def comb(n, r, m):
  X, Y = 1, 1
  for i in range(r):
    X *= n-i
    Y *= i+1
    X %= m
    Y %= m
  return int(X * pow(Y, m-2, m))

out = pow(2, n, m) - 1 - comb(n, a, m) - comb(n, b, m)
print(out%m)

Submission status: Accepted

Solution code:
from functools import reduce

def cmb(n, r, p):
    r = min(n - r, r)
    if r == 0:
        return 1
    numer = reduce(lambda x, y: (x*y)%p, range(n, n - r, -1))
    denom = reduce(lambda x, y: (x*y)%p, range(1, r + 1))
    return (numer * pow(denom, p-2, p)) % p

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

ans = pow(2, n, p) - 1
ans -= cmb(n, a, p) + cmb(n, b, p)
print(ans % p)

Submission status: Accepted

Solution code:
def cmb(n, r, p):
    r = min(r, n - r)
    res = 1
    for i in range(r):
        res *= pow(i+1, p-2, p)  # 分母の逆元(フェルマーの定理)
        res *= n-i  # 分子
        res %= p
    return res

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

Submission status: Accepted

Solution code:
def cmb(n, r, p):
    r = min(r, n - r)
    res = 1
    for i in range(r):
        res *= pow(i+1, p-2, p)
        res *= n-i
        res %= p
    return res

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

Submission status: Accepted

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

M = pow(2, N, m)

def nCr(n,r):
    if r*2>n:
        return nCr(n,n-r)
    else:
        a = b = 1
        for i in range(r):
            a = a * (n - i) % m
            b = b * (r - i) % m
        return (a * pow(b,m-2,m)) % m
 
ans = M - 1 - nCr(N,a) - nCr(N,b)
print(ans%m)

Submission status: Accepted

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

def nCr(n,r):
    if r*2>n:
        return nCr(n,n-r)
    else:
        a = b = 1
        for i in range(r):
            a = a * (n - i) % mod
            b = b * (r - i) % mod
        return (a * pow(b,mod-2,mod)) % mod

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

Submission status: Accepted

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

#(a*x)をmで割った余りが1になるようなxを求める
#aで割ったときの余りはa^(-1)をかけた余りと同じ
#逆元a^(-1)を求める
#aとmが互いに素であることが条件

def gyakugen( a, m ):
  b = m
  x, y = 1, 0
  while b>0:
    q = a // b
    a, b = b, a-q*b
    x, y = y, x-q*y
  return x if x>0 else x+m

#nPrをmで割った余りを求める(ただしn<m、mは素数)
import sys
sys.setrecursionlimit(10**9)#再帰の回数の上限を設定

def perm_remainder(n,r,m):
    if r>=1:
        return (perm_remainder(n-1,r-1,m)*n)%m
    else:
        return 1

#nCrをmで割った余りを求める(ただしn<m,mは素数)

def comb_remainder(n,r,m):
    r=min(r,n-r)
    return (perm_remainder(n,r,m)*gyakugen(perm_remainder(r,r,m),m))%m

#(a**n)を素数mで割った余りを求める
#当然aはmで割り切れない整数

def power_remainder(a,x,m):
    a=a%m
    bi=str(format(x,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %m
        if bi[i]=="1":
            res=(res*a) %m
    return res

#2^n-nCa-nCb-1を計算
print((power_remainder(2,n,m)-1-comb_remainder(n,a,m)-comb_remainder(n,b,m))%m)

Submission status: Accepted

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

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


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


comb_a = C(n,a,mod)
comb_b = C(n,b,mod)

print((res-(comb_a+comb_b))%mod)

Submission status: Accepted

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

INF = float('inf')
MOD = 10 ** 9 + 7


def nCr_mod(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


def main():
    N, A, B = map(int, input().split())
    total = pow(2, N, MOD)
    print((total - nCr_mod(N, A) - nCr_mod(N, B) - 1) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 10**9 + 7
 
def C(n, r, mod):
    x=y=1
    for i in range(r):
        x *= n; y *= r
        x %= mod; y %= mod
        n -= 1; r -= 1
    return x * pow(y, mod - 2, mod) % mod
 
 
n, a, b = map(int, input().split())
 
print((pow(2, n, mod) - 1 - C(n, a, mod) - C(n, b, mod)) % mod)

Submission status: Accepted

Solution code:
def main():
    n, a, b = map(int, input().split())
    c = 1
    d = 1
    MOD = 10 ** 9 + 7
    for i in range(a):
        c *= n - i
        d *= i + 1
        c %= MOD
        d %= MOD

    nca = c * pow(d, MOD - 2, MOD)
    nca %= MOD

    c = 1
    d = 1
    for i in range(b):
        c *= n - i
        c %= MOD
        d *= i + 1
        d %= MOD

    ncb = c * pow(d, MOD - 2, MOD)
    ncb %= MOD
    ans = pow(2, n, MOD)
    ans -=  nca + ncb
    ans %= MOD
    print(ans-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math


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

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

num_1 = 1
num_2 = 1

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

for j in range(1, b+1):
    num_2 = num_2 * (n-b+j) % MOD

gyakugen_a = pow(math.factorial(a), MOD-2, MOD)
gyakugen_b = pow(math.factorial(b), MOD-2, MOD)

num_1 *= gyakugen_a
num_2 *= gyakugen_b

print((sum - num_1 - num_2)%MOD)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

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

def make_nCk_tables(n):
  M = min(n, 2*10**5)
  nCk = [0]*(M+1)
  nCk[0], nCk[1] = 1, n
  inv = [0]*(M+1)
  inv[0], inv[1] = 0, 1
  for k in range(2, M+1):
    inv[k] = MOD + (-inv[MOD % k] * (MOD//k)) % MOD
    nCk[k] = ((nCk[k-1] * (n-k+1)) % MOD) * inv[k] % MOD
  return nCk

nCk = make_nCk_tables(n)
ans = modpow(2, n)-1
ans = (ans - nCk[a]) % MOD
ans = (ans - nCk[b]) % MOD
print(ans)

Submission status: Accepted

Solution code:
n,a,b = map(int, input().split())
M = 10**9 + 7
from math import factorial
from functools import reduce
A = pow(2,n,M) - 1

q = r = 1
for i in range(a):
    q = q * (n - i) %  M
for j in range(b):
    r = r * (n - j) %  M

B = q * pow(factorial(a), M - 2, M) % M
C = r * pow(factorial(b), M - 2, M) % M
print((A-B-C)%M)

Submission status: Accepted

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

n, a, b = map(int, input().split())
al = pow(2, n, mod) -1
acr = ncr(n, a, mod)
bcr = ncr(n, b, mod)
print( (al-(acr+bcr))%mod )

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = 7+10**9
def comb(n,c,mod):
  x = 1
  y = 1
  for i in range(n-c+1,n+1):
    x = x*i%mod
  for j in range(1,c+1):
    y = y*j%mod
  return (x * pow(y, mod-2, mod)) % mod
c_a = comb(n,a,mod)
c_b = comb(n,b,mod)
print((pow(2,n,mod)-1 -(c_a+c_b))%mod)

Submission status: Accepted

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

def f(c,d):
  i = 1
  while d > 0:
    if d % 2 == 1:
      i *= c
      i = i % (10**9+7)  
    c *= c
    c = c % (10**9+7)
    d >>= 1
  return i

def p(c,d):
  i = 1
  for j in range(c,c-d,-1):
    i *= j
    i = i % (10**9+7)
  return i

A = p(n,a)*f(p(a,a),10**9+5) % (10**9+7)
B = p(n,b)*f(p(b,b),10**9+5) % (10**9+7)

print((f(2,n)-1-A-B) % (10**9+7))

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return fn, invs
 
def ncr(n, r, invs, MOD):
    ret = invs[r]
    for i in range(n, n - r, -1):
        ret = ret * i % MOD
    return ret

fn, invs = prepare(max(a, b), mod)
ans = (pow(2, n, mod) - 1 - ncr(n, a, invs, mod) - ncr(n, b, invs, mod)) % mod
print(ans)

Submission status: Accepted

Solution code:
def inverse(n: int, mod: int) -> int:
    return pow(n, mod - 2, mod)

def cmb(n: int, m: int, mod) -> int:
    p, q = 1, 1
    for i in range(m):
        p = p * (n - i) % mod
        q = q * (i + 1) % mod
    return p * inverse(q, mod) % mod

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

Submission status: Accepted

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

mod = 10 ** 9 + 7
def extGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, y, x = extGCD(b, a%b)
    y -= a//b * x
    return g, x, y

def moddiv(a, b):
    _, inv, _ = extGCD(b, mod)
    return (a * inv) % mod

N = 2 * 10 ** 5 + 10
fact = [0] * (N)
fact[0] = 1
for i in range(1, N):
    fact[i] = (fact[i-1] * i) % mod

def comb(n, b):
    bunbo = 1
    for i in range(n-b+1, n+1):
        bunbo *= i
        bunbo %= mod
    return moddiv(bunbo, fact[b])

pow2 = [1] * 64
pow2[1] = 2
for i in range(2, 64):
    pow2[i] = pow2[i-1] ** 2 % mod

def pow(b):
    ret = 1
    for i in range(1, 64):
        if b & 1:
            ret *= pow2[i]
            ret %= mod
        b //= 2
    return ret

ans = pow(n) - 1

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

Submission status: Accepted

Solution code:
def choose(n, m, mod):
    x, y = 1, 1
    for i in range(m):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    return x * pow(y, mod - 2, mod) % mod

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

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

Submission status: Accepted

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

Submission status: Accepted

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

mod = 10 ** 9 + 7
#a本、b本の制限を無視すると、2^n - 1の選び方が存在する。
ans = pow(2, n, mod) - 1 

def choose(n, a):
    x, y = 1, 1
    for i in range(a):
        y = y * (i + 1) % mod
        x = x * (n - i) % mod
    return x * pow(y, mod - 2, mod) % mod 
#上記で求めた値から、a本を選んだ時とb本を選んだ時の組み合わせ数を引く
ans -= choose(n, a)
ans -= choose(n, b)

print(ans % mod)

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
mod = 10**9+7
a = min(a,n-a)
b = min(b,n-b)
m = max(a,b)
X = [0]*(m+1)
Y = [0]*(m+1)
X[0] = 1
X[1] = n
Y[0] = Y[1] = 1

for i in range(2,m+1):
    X[i] = X[i-1]*(n-i+1)%mod
    Y[i] = Y[i-1]*i%mod
    
ans = (((pow(2,n,mod)-1)%mod-X[a]*pow(Y[a],mod-2,mod)%mod)%mod-X[b]*pow(Y[b],mod-2,mod)%mod)%mod
print(ans)

Submission status: Accepted

Solution code:
def comb(n,k):
    nCk = 1
    mod = 10**9+7
    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

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

Submission status: Accepted

Solution code:
mod=7+10**9
n,a,b=map(int,input().split())
def comb(n,c,mod):
  s=1
  t=1
  for i in range(1,c+1):
    s=s*i%mod
  for j in range(n-c+1,n+1):
    t=t*j%mod
  return (t*pow(s,mod-2,mod))%mod
ans=(pow(2,n,mod)-comb(n,a,mod)-comb(n,b,mod)-1)%mod
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7

def comb(n, r):
    x = 1
    y = 1
    if n-r<r:
        r = n-r
    for i in range(r):
        x *= n-i
        y *= (i+1)
        x %= mod
        y %= mod
    return x * pow(y, mod-2, mod) % mod

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

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

Submission status: Accepted

Solution code:
p = 7+10**9
def comb(n, r, p):
    numer = 1
    denom = 1
    for i in range(n-r+1, n+1):
        numer = numer * i % p
    for i in range(1, r+1):
        denom = denom * i % p
    return numer * pow(denom, p-2, p) % p

n, a, b = map(int, input().split())
print(((pow(2, n, p) - comb(n, a, p) - comb(n, b, p) - 1)) % p)

Submission status: Accepted

Solution code:
# フェルマーの小定理，逆元，（繰り返し二乗法）

n,a,b = map(int, input().split())
mod = 10**9 + 7
s = pow(2,n,mod) - 1 # どんな花束の数でもいい時の場合の数（花束を渡さない選択肢はないから，その分は省略）

# nCr
def fur(n,r):
    # ここはnCrの分数の分子と分母を計算
    x,y = 1,1
    for i in range(r):
        x = x*(n-i)%mod
        y = y*(i+1)%mod
    return x * pow(y,mod-2,mod) % mod # フェルマーの小定理を使うことで，割り算のmod計算を掛け算のmod計算にできた(逆元？)

print((s - fur(n,a) - fur(n,b)) % mod)

Submission status: Accepted

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

def cmb(n, r, mod):
	a = 1
	b = 1
	r = min(r, n-r)
	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 = map(int, input().split())
    MOD = 10**9+7
    total = pow(2, n, MOD)
    a_ = cmb(n, a, MOD)
    b_ = cmb(n, b, MOD)

    print((total - a_ - b_ - 1) % MOD)

main()

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
MOD = int(1e9) + 7
ans = pow(2, n, MOD) - 1


def comb_fermat(n: int, r: int) -> int:

    if r > n:
        return 0
    if r > n-r:
        return comb_fermat(n, n-r)
    mul, div = 1, 1
    for i in range(r):
        mul *= n-i
        mul %= MOD
        div *= i+1
        div %= MOD

    ret = mul * pow(div, MOD-2, MOD) % MOD
    return ret


ans -= comb_fermat(n, a)
ans -= comb_fermat(n, b)
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

# permutation: n * (n-1) * …… * (n-k+1) (mod p)
def prm(n, k, p=10**9+7):
    res = 1
    for i in range(k):
        res = res * (n-i) % p
    return res

# note: p must be a prime number
# フェルマーの小定理より
def modinv(a, p):
  return pow( a, p-2, p )
  
# combination: nPk / k! (mod p), note: p must be a prime number
def cmb(n, k, p=10**9+7):
    k = min(k, n - k)
    return prm( n, k ) * modinv( prm(k, k), p ) % p

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

#何も選ばない1通りを除く
ans = pow(2,n,mod) - 1 - cmb(n,a) - cmb(n,b)
print(ans % mod)

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
mod = 10**9+7
def combination(N,K):
    bunsi = 1
    bunbo = 1
    for i in range(K):
        bunsi = bunsi*(N-i)%mod
        bunbo = bunbo*(i+1)%mod
    return bunsi*pow(bunbo,mod-2,mod)%mod
all_num = pow(2,n,mod)-1
ans = all_num-combination(n,a)-combination(n,b)
print(ans%mod)

Submission status: Accepted

Solution code:
M = 10**9+7
def comb(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

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

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

Submission status: Accepted

Solution code:
num = 10**9+7

def modpow(a, n, p):
    if n==1:
        return a%p
    if n%2 == 1:
        return (a*modpow(a, n-1, p))%p
    else:
        temp = modpow(a, n//2, p)
        return (temp*temp)%p

def combi(x, y):
    numer = 1
    denom = 1
    for i in range(y):
        numer *= x-i
        denom *= i+1
        numer %= num
        denom %= num
    return (numer*modpow(denom, num-2, num))%num

def main():
    n, a, b = map(int, input().split())
    out1 = modpow(2, n, num)
    print((out1 - combi(n, a) - combi(n, b) - 1)%num)

if __name__=='__main__':
    # import time
    # start = time.time()
    main()
    # print(f"{time.time()-start}[s]")

Submission status: Accepted

Solution code:
def f(x,r,p):
  ans=1
  for i in range(1,r+1):
    ans=(ans*(x-i+1))%p
  return ans
def comb(x,r,p):
  r=min(r,x-r)
  return (pow(f(r,r,p),p-2,p)*f(x,r,p))%p
n,a,b=map(int,input().split())
mod=10**9+7
print((pow(2,n,mod)-comb(n,a,mod)-comb(n,b,mod)-1)%mod)

Submission status: Accepted

Solution code:
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
def cmb(n, k, p):
    a = 1
    b = 1
    for i in range(k):
        a *= n-i
        a %= p
        b *= i+1
        b %= p
    return a*power_func(b, p-2, p)%p

MOD = 1000000007
ans1 = 1
n, a, b = map(int, input().split())
ans = power_func(2, n, MOD)-1-cmb(n, a, MOD)-cmb(n, b, MOD)
if ans < 0:
    ans += MOD
if ans < 0:
    ans += MOD
print(ans)

Submission status: Accepted

Solution code:
def cmb(n, r, p):
    A = 1
    B = 1
    r = min(r, n - r)
    for i in range(r):
        A = A * (n-i) % p
        B = B * (i+1) % p
    return A * pow(B, p-2, p) % p

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

Submission status: Accepted

Solution code:
mod=10**9+7
def nCr(n, r):
    mod=10**9+7
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

n,a,b=map(int,input().split())
w=pow(2, n, mod)-1

ans=w-nCr(n,a)-nCr(n,b)
while ans<0:
    ans+=mod
print(ans%mod)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
def cmb(n,r,mod):
	a=1
	b=1
	r = min(r,n-r)
	for i in range(r):
		a = a*(n-i)%mod
		b = b*(i+1)%mod
	return a*pow(b,mod-2,mod)%mod

n,a,b = map(int,input().split())
count = 0
all = pow(2,n,mod) + mod
nCa = cmb(n,a,mod)
nCb = cmb(n,b,mod)
ans = all - (nCa + nCb)
print((ans-1)%mod)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
def cmb(n,r,mod):
	a=1
	b=1
	r = min(r,n-r)
	for i in range(r):
		a = a*(n-i)%mod
		b = b*(i+1)%mod
	return a*pow(b,mod-2,mod)%mod

n,a,b = map(int,input().split())
count = 0
all = pow(2,n,mod) - 1
nCa = cmb(n,a,mod)
nCb = cmb(n,b,mod)
ans = all - (nCa + nCb)
while (ans < 0):
  ans += mod
print(ans)