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

Submission status: Accepted

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

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	m=10**9+7
	n,a,b=MI()
	f=[1]
	for i in range(b+5):
		t=f[-1]*(n-i)*pow(i+1,m-2,m)
		t%=m
		f.append(t)
	#print(f)

	ans=pow(2,n,m)-1-f[a]-f[b]
	ans%=m
	print(ans)




























if __name__ == "__main__":
	main()

Submission status: Accepted

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

MOD = 10 ** 9 + 7

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

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

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce


def combinations_count(n, r, P):
    r = min(r, n - r)
    inv_y = 1
    for i in range(1, r + 1):
        inv_y = (inv_y * i) % P
    inv_y = pow(inv_y, P - 2, P)
    x = 1
    for i in range(n - r + 1, n + 1):
        x = x * i % P
    return (x * inv_y) % P



n, a, b = map(int, input().split())
P = int(1e9+7)
ans = pow(2, n, P) - 1  # 1本以上の花束の種類


ans = (ans - combinations_count(n, a, P))
ans = (ans - combinations_count(n, b, P))
print(ans%P)

Submission status: Accepted

Solution code:
def factorial(a,n):
  # n*(n-1)*,,,,,*(n-a+1)
  ans=1
  for i in range(n,n-a,-1):
    ans=(ans*i)%M
  return ans


def pow(x, n):
  ans=1
  while n:
    if n % 2 == 1:
      ans = (ans*x)%M
    x = (x*x)%M
    n >>= 1
  return ans


def main():
  ans=pow(2,N) - 1
  ans-=(factorial(A,N)*pow(factorial(A,A),M-2))%M
  ans+= 0 if ans>=0 else M
  ans-=(factorial(B,N)*pow(factorial(B,B),M-2))%M
  print(ans if ans>=0 else ans+M)
  
  
if __name__=='__main__':
  N, A, B = map(int, input().split())
  M = 10**9 + 7
  main()

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,a,b = inpl()
dl = 1
for i in range(a):
    dl *= n-i
    dl %= mod
for i in range(a):
    dl *= pow(a-i,mod-2,mod)
    dl %= mod
# print(dl)
vv = 1
for i in range(b):
    vv *= n-i
    vv %= mod
for i in range(b):
    vv *= pow(b-i,mod-2,mod)
    vv %= mod
# print(vv)
res = pow(2,n,mod) - dl - vv - 1
print(res%mod)

Submission status: Accepted

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

X=1
Y=1

for i in range(1,a+1):
    X=X*(n+1-i)%MOD
    Y=Y*i%MOD
    if i==b:
        b_X=X
        b_Y=Y
a_X=X
a_Y=Y
def calc(X,Y,MOD):
    return X*pow(Y,MOD-2,MOD)

ans=pow(2,n,MOD)%MOD-1-calc(a_X,a_Y,MOD)-calc(b_X,b_Y,MOD)

print(ans%MOD)

Submission status: Accepted

Solution code:
def comb_mod(n,r):
    mod = 10**9+7
    ans = 1
    for i in range(r):
        ans *= n-i
        ans %= mod
    for i in range(1,r+1):
        ans *= pow(i,-1,mod)
        ans %= mod
    return ans

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

Submission status: Accepted

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

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

def c(n, k):
    ue, sita = 1, 1
    for i in range(0, k):
        ue = ue * (n - i) % mod
       	sita = sita * (i + 1) % mod
    return ue * inv(sita) % mod


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

Submission status: Accepted

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

n,a,b = map(int, input().split())
MOD = 10**9+7
ncnt = pow(2,n,MOD)-1
acnt = 1
for i in range(a):
    acnt *= (n-i)
    acnt *= modinv(i+1,MOD)
    acnt %= MOD

bcnt = 1
for i in range(b):
    bcnt *= (n-i)
    bcnt *= modinv(i+1,MOD)
    bcnt %= MOD

ans = ncnt - acnt - bcnt
print(ans%MOD)

Submission status: Accepted

Solution code:
def Li():
    return list(map(int, input().split()))


n, a, b = Li()
mod = pow(10, 9)+7
bunshi = 1
bunbo = 1
ans = pow(2, n, mod)-1
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)

Submission status: Accepted

Solution code:
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
n,a,b = map(int,input().split())
A = [1 for _ in range(2*10**5+1)]
for i in range(2,2*10**5+1):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(2*10**5+1)]
B[2*10**5] = pow(A[2*10**5],p-2)
for i in range(2*10**5-1,1,-1):
    B[i] = (B[i+1]*(i+1))%p
cnt = pow(2,n)-1
cnt1 = 1
for i in range(a):
    cnt1 = (cnt1*(n-i))%p
cnt1 = (cnt1*B[a])%p
cnt2 = 1
for i in range(b):
    cnt2 = (cnt2*(n-i))%p
cnt2 = (cnt2*B[b])%p
cnt = (cnt-cnt1-cnt2)%p
print(cnt)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def nCr(n, r, MOD):
    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
n, a, b = map(int,input().split())
ans = pow(2,n,MOD)-1-nCr(n,a,MOD)-nCr(n,b,MOD)
while ans < 0:
    ans += MOD
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
# 全通り - nCa - nCb
mod = 10 ** 9 + 7


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

# n ~ n - k + 1


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


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

Submission status: Accepted

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

def power_func(a,n,mod):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res)%mod
    if bi[i]=='1':
      res=(res*a)%mod
  return res

def cmb1(x,y,mod):
  l=1
  for g in  range(x+1-y,x+1):
    l*=g
    l%=mod
  for k in range(1,y+1):
    l*=power_func(k,mod-2,mod)
    l%=mod
    
  return l
    
  return ans

ans=power_func(2,n,mod)-1
ans1=cmb1(n,a,mod)
ans2=cmb1(n,b,mod)

print((ans-ans1-ans2)%mod)

Submission status: Accepted

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

def perm(a,b):
    tmp=1
    for i in range(b):
        tmp*=a-i
        tmp=tmp%C
    return tmp

cta=perm(n,a)*pow(perm(a,a),C-2,C)
ctb=perm(n,b)*pow(perm(b,b),C-2,C)

ans=pow(2,n,C)-1-cta-ctb
print(ans%C)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

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

modinv_table = [-1] * (b+1)
for i in range(1, b+1):
    modinv_table[i] = modinv(i, MOD)

def comb(n, k, mod):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans
  
ans = (pow(2, n, MOD) - comb(n, a, MOD) - comb(n, b, MOD)) % MOD - 1

print(ans)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = pow(10, 9) + 7
total = pow(2, n, mod)
#print(total)
def comb(m, x):
  numerator = 1
  for i in range(m - x + 1, m + 1):
    numerator = numerator * i % mod
  denominator = 1
  for i in range(1, x + 1):
    denominator = denominator * i % mod
  d = pow(denominator, mod - 2, mod)
  return numerator * d
a = comb(n, a)
b = comb(n, b)
print((total - a - b - 1) % mod)

Submission status: Accepted

Solution code:
MOD=10**9+7
def pow(x,n,mod):
    ans = 1
    while n>0:
        if n&1==1:
            ans*=x
            ans%=mod
        x = x*x
        x%=mod
        n = n>>1
    return ans

N,a,b=map(int,input().split())
xa=1
for i in range(N,N-a,-1):
  xa*=i
  xa%=MOD
xb=xa
for i in range(N-a,N-b,-1):
  xb*=i
  xb%=MOD
ya=1
for i in range(2,a+1):
  ya*=i
  ya%=MOD
yb=ya
for i in range(a+1,b+1):
  yb*=i
  yb%=MOD
ans=(pow(2,N,MOD)-1
     -(xa*pow(ya,MOD-2,MOD)%MOD)
     -(xb*pow(yb,MOD-2,MOD)%MOD))%MOD
print(ans)

Submission status: Accepted

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

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

def com(n,r):
    s = 1
    for i in range(n-r+1, n+1):
        s *= i
        s %= MOD

    t = 1
    for j in range(1,r+1):
        t *= j
        t %= MOD


    return s * pow(t,MOD-2, MOD) % MOD

print((N - com(n, a) - com(n, b) - 1) % (MOD))

Submission status: Accepted

Solution code:
'''
pow(base, exp[, mod])
base の exp 乗を返します; 
mod があれば、base の exp 乗に対する mod の剰余を返します 
(pow(base, exp) % mod より効率よく計算されます)。
二引数の形式 pow(base, exp) は、冪乗演算子を使った base**exp と等価です。
'''

url = 'https://tane-no-blog.com/976/'

# pow を実装したコード
# def pow(x,n):
    # res = 1
    # while n > 0:
        # if n&1 == 1:
            # res *= x
        # x *= x
        # n >>= 1
    # return res

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

# pow を用いた組み合わせ計算の高速化
mod = 10**9 + 7
def comb(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 = comb(n,a)
B = comb(n,b)

print((pow(2,n,mod)-1-A-B) % mod)

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
p = 10**9 + 7
def CC(n,k):
  X,Y = 1,1
  for i in range(n-k+1,n+1):
    X = X*i%p
  for j in range(1,k+1):
    Y = Y*j%p
  YY = pow(Y,p-2,p)
  return(X*YY%p)
A = CC(n,a)
B = CC(n,b)
ALL = pow(2,n,p)
ans = (ALL-1-A-B)%p
print(ans)

Submission status: Accepted

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

mod = 10**9+7

def combi(n,r):
    x, y = 1,1
    for i in range(n-r+1,n+1):
        x *= i
        x %= mod
        
    for j in range(1,r+1):
        y *= j
        y %= mod
    yinv = pow(y,mod-2,mod)
    
    return x*yinv%mod

def main():
    nca = combi(n,a)
    ncb = combi(n,b)
    ans = pow(2,n,mod)-1 - (nca + ncb)
        
    print(ans%mod)
    
main()

Submission status: Accepted

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


def comb(n, r, mod=10 ** 9 + 7):
    r = min(r, n-r)
    upper = 1

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

    lower = 1

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

    lower_inv = pow(lower, mod - 2, mod)

    return (upper * lower_inv) % mod


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


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


def main():
    n, a, b = MI()

    ttl = pow(2, n, 10**9+7) - 1

    a_ttl = comb(n, a)
    b_ttl = comb(n, b)

    print((ttl - a_ttl - b_ttl) % (10**9+7))


main()

Submission status: Accepted

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

Submission status: Accepted

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

def cmb(n, r):
  # 分子(n*(n-1)*...*(n-r+1))
  nume = 1
  for i in range(n-r+1, n+1):
    nume = nume * i % p
  # 分母（1*2*...*r）
  deno = 1
  for j in range(1, r+1):
    deno = deno * j % p
    d = pow(deno, p-2, p)
  return nume * d

nca = cmb(n, a)
ncb = cmb(n, b)
res = pow(2, n, p) - nca - ncb - 1
print(res%p)

Submission status: Accepted

Solution code:
from math import *
def modpow(a,n,m):
  res=1
  while n>0:
    if n&1:res=res*a%m
    a=a*a%m
    n//=2
  return res
n,a,b=map(int,input().split())
mod=10**9+7
ans=modpow(2,n,mod)-1
na=1
nb=1
for i in range(a):
  na*=(n-i)%mod
  na%=mod
fa=1
for i in range(1,a+1):
  fa*=i
  fa%=mod
na*=modpow(fa,mod-2,mod)
for i in range(b):
  nb*=(n-i)%mod
  nb%=mod
fb=1
for i in range(1,b+1):
  fb*=i
  fb%=mod
nb*=modpow(fb,mod-2,mod)
print((ans-nb-na)%mod)

Submission status: Accepted

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

def binom(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)

    res = factinv[r] % p
    for i in range(r):
        res = res * (n - i) % p

    return res % p

factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, min(n, 2*10**5) + 1):
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

res = pow(2, n, p)

res -= 1
res = (res - binom(n, a, p)) % p
res = (res - binom(n, b, p)) % p

print(res)

Submission status: Accepted

Solution code:
def cmb(n, r, p):
    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
    # 剰余の計算において、+-*は良いが、/は普通にやると成り立たない
    # 割るのではなく、「逆元」を掛けるとする
    # フェルマーの小定理より、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:
n,a,b = map(int, input().split())

def ruizyou(x,r,mod):
    sisuu=r
    kotae=1
    kake=x
    while sisuu:
        if sisuu&1==True:
            kotae*=kake
        sisuu>>=1
        kake**=2
        kake%=mod
        kotae%=mod
    return kotae

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

    sita=1

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

    sita=ruizyou(sita,mod-2,mod)

    return (ue*sita)%mod

mod=10**9+7

ans=ruizyou(2,n,mod)-conbi(n,a,mod)-conbi(n,b,mod)-1
ans%=mod
print(ans)

Submission status: Accepted

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

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

ans = (pow(2, n, MOD)-1-comb(n,a)-comb(n,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 comb(n, k):
    def mul(a, b):
        return a*b%MOD
    x = reduce(mul, range(n, n-k, -1))
    y = reduce(mul, range(1, k+1))
    return x*pow(y, MOD-2, MOD) % MOD

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

print(ans)

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from functools import reduce

mod = 10**9 + 7


def cmb(n, r, m):
    def mul(a, b):
        return a * b % m

    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over * pow(under, m - 2, m)


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from functools import reduce

mod = 10**9 + 7


def cmb(n, r, m):
    mul = lambda a,b: a*b%m
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over * pow(under, mod - 2, mod)


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from functools import reduce
from operator import mul

mod = 10**9 + 7


def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(lambda a, b: a * b % mod, range(n, n - r, -1))
    under = reduce(lambda a, b: a * b % mod, range(1, r + 1))
    return over * pow(under,mod-2,mod)


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

Submission status: Accepted

Solution code:
def calc_comb(n,r):
    numerator=1
    for i in range(n-r+1,n+1):
        numerator=(numerator*i)%mod
    denominator=1
    for i in range(1,r+1):
        denominator=(denominator*i)%mod
    return (numerator*pow(denominator,mod-2,mod))%mod
n,a,b=map(int,input().split())
mod=1000000007
print((pow(2,n,mod)-1-calc_comb(n,a)-calc_comb(n,b)+mod)%mod)

Submission status: Accepted

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

# 全組み合わせ 2**n % (10**9 + 7) から1本も選択しない1パターンを引いている
x = pow(2, n, p) - 1

# nCa % (10**9 + 7)
y = 1
z = 1
for i in range(1, a+1):
  y = y * (n - i + 1) % p
  z = z * i % p
n_c_a = y * pow(z, p-2, p) % p

# nCb % (10**9 + 7)
y = 1
z = 1
for i in range(1, b+1):
  y = y * (n - i + 1) % p
  z = z * i % p
n_c_b = y * pow(z, p-2, p) % p

print((x - n_c_a - n_c_b) % p)

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):
        # 分子(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
    
    all_cmb = pow(2, n, mod) - 1
    bad_a = cmb(n, a)
    bad_b = cmb(n, b)    
    print((all_cmb-bad_a-bad_b) % mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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

def cmb2(n, r, mod):
    res = 1
    temp = 1
    for k in range(1, r+1):
        res *= (n-k+1)
        temp *= k
        res %= mod
        temp %= mod
    res *= pow(temp,(mod-2),mod)
    res %= mod
    return res

def power(a, n, mod):
    bi=str(format(n,"b")) #2進数
    res=1
    for i in range(len(bi)):
        res=(res*res) %mod
        if bi[i]=="1":
            res=(res*a) %mod
    return res

ans = power(2, n, mod) - cmb2(n, a, mod) - cmb2(n, b, mod) -1
ans %= mod
print(ans)

Submission status: Accepted

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

mod=10**9+7
def modpow(a,n):
    if n<1:
        return 1
    ans=modpow(a,n//2)
    ans=(ans*ans)%mod
    if n%2==1:
        ans*=a
    return ans%mod
    
def cmb(n,i):#逆元
    inv,ans=1,1
    for j in range(1,i+1):
        ans=ans*(n-j+1)%mod
        inv=inv*j%mod
    return (ans*modpow(inv,mod-2))%mod



ans_n=pow(2,n,mod)-1
ans_a=cmb(n,a)%mod
ans_b=cmb(n,b)%mod

print((ans_n-ans_a-ans_b)%mod)

Submission status: Accepted

Solution code:
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    n1, r = n+1, 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 = 10**9+7
N, A, B = map(int, input().split())
ans = pow(2, N, mod) - 1 - combination(N, A) - combination(N, B)
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    n, a, b = list(map(int, input().split()))
    MOD = 10**9+7
    ntoa = 1
    ato1 = 1
    ntob = 1
    bto1 = 1
    for i in range(a):
        ntoa *= (n-i)
        ntoa %= MOD
        ato1 *= (a-i)
        ato1 %= MOD
    for i in range(b):
        ntob *= (n-i)
        ntob %= MOD
        bto1 *= (b-i)
        bto1 %= MOD
    def pow(x, n, MOD=10**9+7):
        ret = 1
        while n > 0:
            if n & 1:
                ret = (ret*x)%MOD
            x = (x*x)%MOD
            n >>= 1
        return ret
    nca = ntoa*pow(ato1, MOD-2)%MOD
    ncb = ntob*pow(bto1, MOD-2)%MOD
    print((pow(2, n)%MOD-1-nca-ncb)%MOD)

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
import sys

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7

# ## COMBINATION (MOD) ## #
MOD = 10**9 + 7  # , N = 2*10**5 で 0.3s
N_MAX = 2 * 10**5  # 問題サイズに合わせて変えておく

fac = [1, 1]  # 元テーブル
facinv = [1, 1]  # 逆元テーブル
inv = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N_MAX + 1):
    fac.append((fac[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    facinv.append((facinv[-1] * inv[-1]) % MOD)


def fac(n, a):
    ans = 1
    for i in range(a):
        ans *= n
        ans %= MOD
        n -= 1
    return ans


def cmb(n, r):
    if (r < 0 or r > n):
        return 0
    # r = min(r, n-r)
    return fac[n] * facinv[r] * facinv[n - r] % MOD


def main():
    n, a, b = map(int, sys.stdin.readline().rstrip().split())

    # 全種類
    ans = pow(2, n, MOD) - 1  # -1 : 全部選ばない場合
    ans %= MOD

    # a種類になる場合
    ans -= fac(n, a) * facinv[a]
    ans %= MOD

    ans -= fac(n, b) * facinv[b]
    ans %= MOD

    print(ans)


main()

Submission status: Accepted

Solution code:
import sys
from functools import reduce
from operator import mul
from typing import Callable, ClassVar, Sequence, Type, TypeVar


T = TypeVar('T', bound='ModIntBase')


class ModIntBase:
    value: int
    mod: ClassVar[int]
    fac: ClassVar[Sequence[int]] = ()
    inv: ClassVar[Sequence[int]] = ()
    finv: ClassVar[Sequence[int]] = ()

    def __init__(self, value: int) -> None:
        self.value = value % self.mod

    def __hash__(self) -> int:
        return hash((self.value, self.mod))

    def __eq__(self, other) -> bool:
        if isinstance(other, self.__class__):
            return self.value == other.value
        else:
            return NotImplemented

    def __ne__(self, other) -> bool:
        if isinstance(other, self.__class__):
            return self.value != other.value
        else:
            return NotImplemented

    # TODO: Add type hints
    def __add__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__((self.value + other.value) % self.mod)
        else:
            return NotImplemented

    def __sub__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__((self.value - other.value) % self.mod)
        else:
            return NotImplemented

    def __mul__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__(self.value * other.value % self.mod)
        else:
            return NotImplemented

    def __truediv__(self, other):
        if isinstance(other, self.__class__):
            a = other.value
            b = self.mod
            u = 1
            v = 0
            while b:
                t = a // b
                a, b = b, a - t * b
                u, v = v, u - t * v
            return self.__class__(self.value * u % self.mod)
        else:
            return NotImplemented

    def __pow__(self, other):
        if isinstance(other, self.__class__):
            v = 1
            a = self.value
            b = other.value
            mod = self.mod
            while b > 0:
                if b & 1:
                    v = v * a % mod
                a = a * a % mod
                b >>= 1
            return self.__class__(v)
        else:
            return NotImplemented

    @classmethod
    def comb(cls, n: int, k: int):
        if n < k:
            return cls(0)
        if n < 0 or k < 0:
            return cls(0)

        if n < len(cls.fac):
            return cls(cls.fac[n] * (cls.finv[k] * cls.finv[n - k] % cls.mod) % cls.mod)
        else:
            k = min(k, n - k)
            a = reduce(mul, map(cls, range(n - k + 1, n + 1)), cls(1))
            b = reduce(mul, map(cls, range(1, k + 1)), cls(1))
            return a / b

    def __repr__(self) -> str:
        return f'{self.__class__.__name__}({self.value!r})'

    def __str__(self) -> str:
        return str(self.value)


class ModInt(ModIntBase):
    mod = 1000000007  # 10 ** 9 + 7



def resolve(in_):
    N, A, B = map(int, in_.readline().split())
    
    c = ModInt(2) ** ModInt(N) - ModInt(1)
    a = ModInt.comb(N, A)
    b = ModInt.comb(N, B)
    
    return c - a - b


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,a,b=list(map(int,input().split()))
#2^n-nCa-nCbを求める
#冪乗を求める関数を求める
#2のn乗をmで割ったあまりを求める
def pow(a,n,m):
  if n==0:
    return 1
  else:
    k=pow(a*a%m,n//2,m)
    if n%2==1:
      k=k*a%m
    return k
#次は組み合わせを計算する
#まずは前処理をする
inv=[0 for i in range(200001)]
finv=[0 for i in range(200001)]
inv[1]=1
finv[1]=1
for i in range(2,200001):
  #逆元の求め方p=(p//a)*a+p%a a^(-1)=-(p//a)*(p%a)^(-1)
  inv[i]=(-(1000000007//i)*inv[1000000007%i])%1000000007
  finv[i]=finv[i-1]*inv[i]%1000000007

#nが10^7程度であればnCk=n!*(k!)*((n-k)!)を求めればいい
#nがそれより大きい時は間に合わない。ここでkが小さいことに着目すると
#nCk=n*(n-1).....*(n-k+1)*(k!)^(-1)で求められることがわかる
a_num=1
b_num=1
for i in range(n-a+1,n+1):
  a_num=i*a_num%1000000007
for i in range(n-b+1,n+1):
  b_num=i*b_num%1000000007
print((pow(2,n,1000000007)-1-a_num*finv[a]-b_num*finv[b])%1000000007)