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 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
ans=(2**n-1)%mod
aa=comb(n,a)%mod
bb=comb(n,b)%mod
ans-=aa+bb
print(ans%mod)

Submission status: Accepted

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

mod = 10 ** 9 + 7

ans = pow(2, n, mod) - 1
for i in [a, b]:
    num = 1
    den = 1
    for p in range(n, n-i, -1):
        num = num * p % mod
    for q in range(1, i+1):
        den = den * q % mod
    cmb = num * pow(den, mod-2, mod) % mod
    ans -= cmb
    ans %= mod
print(ans)

Submission status: Accepted

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

u = [1]
d = [1]
c = [1]
for i in range(1, b+1):
    u.append(u[-1] * (n-i+1) % MOD)
    d.append(d[-1] * i % MOD)
    # c.append(u[-1] // d[-1] % MOD)
    c.append(u[-1] * pow(d[-1], MOD-2, MOD) % MOD)

print((pow(2, n, MOD) - c[a] - c[b] - 1) % MOD)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
u, d, c = [1], [1], [1]
for i in range(1, b + 1):
    u.append(u[-1] * (n - i + 1) % mod)
    d.append(d[-1] * i % mod)
    c.append(u[i] * pow(d[i], mod - 2, mod) % mod)
print((pow(2, n, mod) - 1 - c[a] - c[b]) % mod)

Submission status: Accepted

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

mod = 10 ** 9 + 7

def frac_rev(n, r):
  x = 1
  for i in range(n, n-r, -1):
    x = x * i % mod
  return x

def frac(n):
  x = 1
  for i in range(1, n+1):
    x = x * i % mod
  return x

print(( pow(2, n, mod) - 1 - frac_rev(n, a) * pow(frac(a), mod-2, mod) % mod - frac_rev(n, b) * pow(frac(b), mod-2, mod) % mod) % mod)

Submission status: Accepted

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

mod = 10 ** 9 + 7
N = min(n, 2 * 10**5)
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]

def comb(n, r):
  return fac[n] * ( finv[r] * finv[n-r] % mod ) % mod
 
for i in range(2, N + 1):
  fac.append( ( fac[-1] * i ) % mod )
  inv.append( mod - ( inv[mod % i] * (mod // i) % mod ) )
  finv.append( finv[-1] * inv[-1]  % mod )

def frac_rev(n, r):
  x = 1
  for i in range(n, n-r, -1):
    x = x * i % mod
  return x

if n <= 2 * 10**5:
  print(( pow(2, n, mod) - 1 - comb(n, a) -comb(n, b) ) % mod)
else:
  print(( pow(2, n, mod) - 1 - frac_rev(n, a) * finv[a] % mod - frac_rev(n, b) * finv[b] % mod) % mod)

Submission status: Accepted

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

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

print((M-comb(a)-comb(b))%mod)

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
import bisect as bs
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

#整数問題セット
def gcd(numbers): return func.reduce(frac.gcd, numbers)
def lcm(numbers): return func.reduce(LCM, numbers)
def inv(a): return pow(a, MOD-2, MOD) #逆元
def comb(n,r):
    ans = 1
    for i in range(r): ans *= n-i; ans *= inv(r-i); ans %= MOD
    return ans

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

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
import bisect as bs
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

#整数問題セット
def gcd(numbers): return func.reduce(frac.gcd, numbers)
def lcm(numbers): return func.reduce(LCM, numbers)
def inv(a): return pow(a, MOD-2, MOD) #逆元
def comb(n,r):
    ans = 1
    for i in range(r): ans *= n-i; ans *= inv(r-i); ans %= MOD
    return ans

n,a,b = imap()
div,mod = divmod(n,10000)
allEvents = (2**10000%MOD)**div%MOD * 2**mod%MOD
ans = allEvents - comb(n,a) - comb(n,b) - 1
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

def lcm(a, b): return a * b // math.gcd(a, b)
def extgcd(a, b):
    if b:
        d, y, x = extgcd(b, a%b)
        y -= (a/b)*x
        return d, x, y
    else:
        return a, 1, 0


sys.setrecursionlimit(1000000)
MOD = 1000000007



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

    a1, a2 = 1, 1
    for i in range(1, a+1):
        a1 = a1 * (n - i + 1) % MOD
        a2 = a2 * i % MOD
    b1, b2 = 1, 1
    for i in range(1, b+1):
        b1 = b1 * (n - i + 1) % MOD
        b2 = b2 * i % MOD
    nca = a1 * pow(a2, MOD-2, MOD) % MOD
    ncb = b1 * pow(b2, MOD-2, MOD) % MOD

    print((pow(2, n, MOD) - 1 - nca - ncb) % MOD)

main()

Submission status: Accepted

Solution code:
from functools import reduce

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

#combination高速化の裏技
def comb(N, A, MOD):
    num = reduce(lambda x, y: x * y % MOD, range(N, N - A, -1))
    den = reduce(lambda x, y: x * y % MOD, range(1, A + 1))
    return num * pow(den, MOD - 2, MOD) % MOD

#powはmodを引数にしてあまりを計算してくれる
print((pow(2, n, mod = mod) - 1 - comb(n, a, mod) - comb(n, b, mod)) % mod)

Submission status: Accepted

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

def comb(N, A, MOD):
    num = reduce(lambda x, y: x * y % MOD, range(N, N - A, -1))
    den = reduce(lambda x, y: x * y % MOD, range(1, A + 1))
    return num * pow(den, MOD - 2, MOD) % MOD

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

Submission status: Accepted

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

# 1!からmax(a, b)!までの逆元をMODで割ったあまりと
# nからn-max(a*b)までをかけてMODで割ったあまりを求めます。
fact = {}
fact[n] = n
fact[n - 1] = fact[n] * (n - 1) % MOD

inv_fact = [0] * (max(a, b) + 1)
inv_fact[1] = 1

for i in range(2, max(a, b) + 1):
    fact[n - i] = fact[n - i + 1] * (n - i) % MOD
    inv_fact[i] = inv_fact[i - 1] * pow(i, -1, MOD) % MOD

subtrahend = 1 + fact[n - a + 1] * inv_fact[a] + fact[n - b + 1] * inv_fact[b]
minuend = pow(2, n, MOD)

print((minuend + 2 * MOD - subtrahend) % MOD)

Submission status: Accepted

Solution code:
from functools import reduce

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

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

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())
MOD=10**9+7
afac=1
for i in range(1,a+1):
  afac=(i*afac)%MOD
afac=pow(afac,MOD-2,MOD)
bfac=1
for i in range(1,b+1):
  bfac=(i*bfac)%MOD
bfac=pow(bfac,MOD-2,MOD)
thing1=1
for i in range(n,n-a,-1):
  thing1=(i*thing1)%MOD
thing2=1
for i in range(n,n-b,-1):
  thing2=(i*thing2)%MOD
print((pow(2,n,MOD)-1-thing1*afac-thing2*bfac)%MOD)

Submission status: Accepted

Solution code:
class Modulo_Error(Exception):
    pass

class Modulo():
    def __init__(self,a,n):
        self.a=a%n
        self.n=n

    def __str__(self):
        return "{} (mod {})".format(self.a,self.n)

    #+,-
    def __pos__(self):
        return self

    def __neg__(self):
        return  Modulo(-self.a,self.n)

    #等号,不等号
    def __eq__(self,other):
        if isinstance(other,Modulo):
            return (self.a==other.a) and (self.n==other.n)
        elif isinstance(other,int):
            return (self-other).a==0

    def __neq__(self,other):
        return not(self==other)
    
    #加法
    def __add__(self,other):
        if isinstance(other,Modulo):
            if self.n!=other.n:
                raise Modulo_Error("異なる法同士の演算です.")
            return Modulo(self.a+other.a,self.n)
        elif isinstance(other,int):
            return Modulo(self.a+other,self.n)

    def __radd__(self,other):
        if isinstance(other,int):
            return Modulo(self.a+other,self.n)
        
    #減法
    def __sub__(self,other):
        return self+(-other)

    def __rsub__(self,other):
        if isinstance(other,int):
            return -self+other
        
    #乗法
    def __mul__(self,other):
        if isinstance(other,Modulo):
            if self.n!=other.n:
                raise Modulo_Error("異なる法同士の演算です.")
            return Modulo(self.a*other.a,self.n)
        elif isinstance(other,int):
            return Modulo(self.a*other,self.n)
        
    def __rmul__(self,other):
        if isinstance(other,int):
            return Modulo(self.a*other,self.n)
        
    #Modulo逆数
    def Modulo_Inverse(self):
        x0, y0, x1, y1 = 1, 0, 0, 1
        a,b=self.a,self.n
        while b != 0:
            q, a, b = a // b, b, a % b
            x0, x1 = x1, x0 - q * x1
            y0, y1 = y1, y0 - q * y1

        if a!=1:
            raise Modulo_Error("{}の逆数が存在しません".format(self))
        else:
            return Modulo(x0,self.n)
        
    #除法
    def __truediv__(self,other):
        return self*other.Modulo_Inverse()

    #累乗
    def __pow__(self,m):
        u=abs(m)

        r=Modulo(1,self.n)

        while u>0:
            if u%2==1:
                r*=self
            self*=self
            u=u>>1

        if m>=0:
            return r
        else:
            return r.Modulo_Inverse()

#-------------------------------------------------------------------------
M=10**9+7
n,a,b=map(int,input().split())
C=[Modulo(1,M)]*(b+1)

for k in range(1,b+1):
    C[k]=C[k-1]*Modulo(n-(k-1),M)/Modulo(k,M)

print((Modulo(2,M)**n-(C[a]+C[b])-1).a)

Submission status: Accepted

Solution code:
from math import factorial

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

up=[1]
down=[1]
comb=[1]
for i in range(1,b+1):
    up.append(up[i-1]*(n-i+1)%mod)
    down.append(down[i-1]*i%mod)
    comb.append(up[i]*pow(down[i],mod-2,mod)%mod)

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")




n,a,b = map(int, input().split())
M = 10**9+7
N = 2*10**5+3 # 必要なテーブルサイズ

def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

def cmb2(n,r,M):
    res = 1
    for i in range(r):
        res *= (n-i)
        res %= M
#     print(res)
    res *= g2[r]
    res %= M
    return res
    
ans = pow(2, n, M) - cmb2(n,a,M) - cmb2(n,b,M) - 1
print(ans%M)

Submission status: Accepted

Solution code:
MOD=10**9+7

def powmod(a,n,m): #a^n mod m
    ans=1
    while n!=0:
        if n&1: ans=ans*a%m
        a=a*a%m
        n>>=1
    return ans%m

def fact(a,b):
    ans=1
    for i in range(a,b+1): ans=ans*i%MOD
    return ans

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

ans=powmod(2,n,MOD)-1
ta1=fact(n-a+1,n)
tb1=fact(n-b+1,n)
ta2=pow(fact(1,a),MOD-2,MOD)
tb2=pow(fact(1,b),MOD-2,MOD)
a=ta1*ta2%MOD
b=tb1*tb2%MOD
print((ans-a-b)%MOD)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
num9=10**9+7
num2=pow(2,n,num9)-1
def cul(num1,num2):
    num=1
    for i in range(num1-num2+1,n+1):
        num*=i
        num%=num9
    for i in range(1,num2+1):
        num*=pow(i,num9-2,num9)
        num%=num9
    return num
print((num2-cul(n,a)-cul(n,b))%num9)

Submission status: Accepted

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

up = 1
bo = 1
for i in range(b):
    up = up*(n-i)%mod
    bo = bo*(i+1)%mod
    if i == a-1:
        acombs = up*pow(bo, mod-2, mod)%mod

bcombs = up*pow(bo, mod-2, mod)%mod

print((ans - acombs - bcombs)%mod)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
n, a, b = map(int, input().split())
mod = 10**9 + 7
s = pow(2, n, mod) - 1
def cal(n, r):
  p = 1
  q = 1
  for i in range(r):
    p = p*(n-i)%mod
    q = q*(i+1)%mod
  return p*pow(q, mod-2, mod)%mod
print((s - cal(n, a) - cal(n, b))%mod)

Submission status: Accepted

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

mod = pow(10,9)+7
ans = pow(2,n,mod)
ans -= 1
def choose(n,k):
    x,y = 1,1
    for i in range(1,k+1):
        x *= (n-i+1)
        x %= mod
        y *= i
        y %= mod
    
    x *= pow(y,mod-2,mod)
    x %= mod
    return x

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

Submission status: Accepted

Solution code:
from functools import reduce

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

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

    print((ans - comb(n,a,p) - comb(n,b,p)) % p)

def comb(n, r, p):
    r = min(r, n-r)
    if r == 0:
        return 1
    
    num = reduce(lambda x, y: (x * y) % p, range(n, n - r, -1))
    den = reduce(lambda x, y: (x * y) % p, range(1, r + 1))

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# フェルマーの小定理
def mcomb(n, k):
    a = 1
    b = 1
    for i in range(k):
        a *= n - i
        a %= m
        b *= i + 1
        b %= m
    return a * pow(b, m - 2, m) % m


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

m = 1000000007

result = pow(2, n, m) - 1
result -= mcomb(n, a)
result %= m
result -= mcomb(n, b)
result %= m
print(result)

Submission status: Accepted

Solution code:
# フェルマーの小定理
def mcomb(n, k):
    a = 1
    b = 1
    for i in range(k):
        a *= n - i
        a %= m
        b *= i + 1
        b %= m
    return a * pow(b, m - 2, m) % m


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

m = 1000000007

result = pow(2, n, m) - 1
result += m - mcomb(n, a)
result %= m
result += m - mcomb(n, b)
result %= m
print(result)

Submission status: Accepted

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

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

x = 1
y = 1
for i in range(a):
  x = x*(n - i)%mod
  y = y*(i + 1)%mod
ans -= x*pow(y, mod - 2, mod)%mod
  
x = 1
y = 1
for i in range(b):
  x = x*(n - i)%mod
  y = y*(i + 1)%mod
ans -= x*pow(y, mod - 2, mod)%mod
  
print(ans%mod)

Submission status: Accepted

Solution code:
def main():
    n, a, b = map(int, input().split())
    p = 10 ** 9 + 7
    r = pow(2, n, p) - 1
    if (n - a) < a:
        a = n - a
    if (n - b) < b:
        b = n - b
    fac_na = 1
    for i1 in range(n, n - a, -1):
        fac_na = (fac_na * i1) % p
    fac_nb = 1
    for i1 in range(n, n - b, -1):
        fac_nb = (fac_nb * i1) % p
    fac_a = 1
    for i1 in range(1, a+1):
        fac_a = (fac_a * i1) % p
    fac_b = 1
    for i1 in range(1, b+1):
        fac_b = (fac_b * i1) % p

    an = fac_na * pow(fac_a, p-2, p)
    bn = fac_nb * pow(fac_b, p-2, p)
    an = an % p
    bn = bn % p
    r -= an
    if r < 0:
        r += p
    r -= bn
    if r < 0:
        r += p
    if r < 0:
        r += p
    print(int(r))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def combination_mod(n, r, mod):
    x = 1
    y = 1

    for i in range(r):
        x *= n - i
        y *= r - i
        x %= mod
        y %= 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
ans %= mod
ans -= combination_mod(n, a, mod)
ans %= mod
ans -= combination_mod(n, b, mod)
ans %= mod

print(ans)

Submission status: Accepted

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

def repeatSquaring(N, P, M):
    if P <= 0:
        return 1
    if (P &0x01) == 0:
        ans = repeatSquaring(N, (P>>1), M)
        return ans*ans % M

    return N*repeatSquaring(N, P-1, M) % M

def seki(aa, bb):
    res = 1
    for k in range(aa, bb+1):
        res *= k
        if res >= modz:
            res %= modz
    return res

def CC(aa, nn):
    ss = repeatSquaring(seki(1, aa), modz - 2, modz)
    return seki(nn-aa + 1, nn)*ss % modz

total = repeatSquaring(2, N, modz) - 1
total -= CC(a, N)
if total < 0: total += modz

total -= CC(b, N)
if total < 0: total += modz

print(int(total))

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
def main():
    from functools import reduce
    def a_comb_mod(n, r):
        mod = 1000000007
        r = min(n-r,r)
        if r == 0: return 1
        numer = reduce(lambda x, y: x * y % mod, range(n, n - r, -1), 1)
        denom = reduce(lambda x, y: x * y % mod, range(1,r + 1), 1)
        denom_inv = pow(denom, mod - 2, mod)
        return numer * denom_inv % mod

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
k = 72
kk = k // 4
K = 1<<k
nu = lambda L: int("".join([hex(K+a)[3:] for a in L[::-1]]), 16)
st = lambda n: hex(n)[2:]
li = lambda s, l, r: [int(a, 16) % P if len(a) else 0 for a in [s[-(i+1)*kk:-i*kk] for i in range(l, r)]]

def grow(d, v, h):
    h += [0] * d
    f = [(-1 if (i+d) % 2 else 1) * fainv[i] * fainv[d-i] % P * h[i] % P for i in range(d+1)]
    nuf = nu(f)
    a = d * inv[v] % P
    t = [1] * (3*d+3)
    for i in range(1, 3*d+3): t[i] = t[i-1] * (a - d + i - 1) % P
    ti = [1] * (3*d+3)
    ti[-1] = pow(t[-1], P-2, P)
    for i in range(1, 3*d+3)[::-1]: ti[i-1] = ti[i] * (a - d + i - 1) % P
    iv = [1] * (3*d+3)
    for i in range(1, 3*d+3):
        iv[i] = ti[i] * t[i-1] % P

    ###
    g = [inv[i] for i in range(1, 2*d+2)]
    fg = li(st(nuf * nu(g)), d, d * 2 + 1)
    for i in range(d):
        h[i+d+1] = fg[i] * fa[d+i+1] % P * fainv[i] % P

    ###
    g = [iv[i] for i in range(1, 2*d+2)]
    fg = li(st(nuf * nu(g)), d, d * 2 + 1)
    for i in range(d+1):
        h[i] = h[i] * (fg[i] * t[d+i+1] % P * ti[i] % P) % P

    ###
    g = [iv[i] for i in range(d+2, 3*d+3)]
    fg = li(st(nuf * nu(g)), d, d * 2 + 1)
    for i in range(d):
        h[i+d+1] = h[i+d+1] * (fg[i] * t[2*d+i+2] % P * ti[d+i+1] % P) % P

    return h

# Create a table of the factorial of the first v+2 multiples of v, i.e., [0!, v!, 2v!, ..., (v(v+1))!]
def create_table(v):
    s = 1
    X = [1, v+1]
    while s < v:
        X = grow(s, v, X)
        s *= 2

    table = [1]
    for x in X:
        table.append(table[-1] * x % P)
    return table

def fact(i, table):
    a = table[i//v]
    for j in range(i//v*v+1, i+1):
        a = a * j % P
    return a

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

v = 1 << (N.bit_length() + 1) // 2
fa = [1] * (2*v+2)
fainv = [1] * (2*v+2)
for i in range(2*v+1):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(2*v+1)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P
inv = [0] * (2*v+2)
for i in range(1, 2*v+2):
    inv[i] = fainv[i] * fa[i-1] % P

T = create_table(v)
C = lambda n, k: fact(n, T) * pow(fact(k, T) * fact(n-k, T), P-2, P) % P
 
print((pow(2, N, P) - 1 - C(N, A) - C(N, B)) % P)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from functools import reduce

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

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

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = 10**9+7
sum = pow(2, n, mod) - 1 #(2**n-1)%modと同じ

def comb(m):
    x = 1
    y = 1
    for i in range(m):
        x = x*(n-i)%mod #コンビネーションの分子
        y = y*(i+1)%mod #コンビネーションの分母
    return (x * pow(y, mod-2, mod) % mod)

print((sum-comb(a)-comb(b))%mod)

Submission status: Accepted

Solution code:
mod=10**9+7
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
n,a,b=mi()
c=pow(2,n,mod)-1
fact=[1]*(2*10**5+1)
for i in range(1,2*10**5+1):
  fact[i]=(fact[i-1]*i)%mod
def nCk(n,k):
  h=1
  for i in range(k):
    h=(h*(n-i))%mod
  x=h*pow(fact[k],mod-2,mod)
  return(x)
print((c-nCk(n,a)-nCk(n,b))%mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def modinv(a):
    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
    if u < 0:
        u += MOD
    return u


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


def solve():
    N, A, B = Scanner.map_int()
    ans = modpow(2, N) - 1
    c = 1
    for i in range(1, A + 1):
        c *= N - i + 1
        c %= MOD
        c *= modinv(i) % MOD
    ans -= c
    c = 1
    for i in range(1, B + 1):
        c *= N - i + 1
        c %= MOD
        c *= modinv(i) % MOD
    ans -= c
    ans += MOD
    ans %= MOD
    print(ans)


def main():
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from functools import reduce

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

MOD = 10**9 + 7


def comb(n, r, mod=float("inf")):
    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


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

Submission status: Accepted

Solution code:
from math import factorial

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

k1 = pow(2,n,MOD)
A = pow(factorial(a),MOD-2,MOD)
B = pow(factorial(b),MOD-2,MOD) 

for i in range(a):
  xa = xa*(n-i)%MOD
for j in range(b):
  xb = xb*(n-j)%MOD

ans = (k1 - (A*xa) - (B*xb) - 1)%MOD 

print(ans)

Submission status: Accepted

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

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)%MOD


#実際に使うときは、MOD=10000007 などの剰余計算を組み込んで使うこと！
def repeated_square(x,n):
    #nを2進数で表して順序反転
    bit_n=bin(n)[2:][::-1]

    ans=1
    ni=x

    if(bit_n[0]=="1"):
        ans*=ni

    for i in range(1,len(bit_n)):
        ni=((ni%MOD)*(ni%MOD))%MOD

        #i桁目が1なら、x^(2^i)を加える
        if(bit_n[i]=="1"):
            ans=((ans%MOD)*(ni%MOD))%MOD

    return ans

alln=(repeated_square(2, n)-1)%MOD
print((alln-comb(n, a)-comb(n, b))%MOD)

Submission status: Accepted

Solution code:

# 組み合わせの総数 p=10**9+7 で割ったあまりを求める 
"""n<10**9 ,r<10**7  ,p は素数"""
def comb(n,r):
    if n-r < r:
        r=n-r
    p=1
    q=1
    for i in range(r):
        p *=n-i #=n(n-1)・・(n-r+1)
        p %= mod
        q *=i+1 #=1・2・・r =r!
        q %=mod
    return p*pow(q,mod-2,mod)


# 初期入力
N,a,b = (int(x) for x in input().split())
mod =10**9 +7

#N種類の花1本以上の組み合わせ全て(0本選ぶは×なので-1)
all = pow(2,N,mod)-1

#嫌いな本数の組み合わせ
comb_a =comb(N,a)
comb_b =comb(N,b)

ans =(all -comb_a -comb_b)% mod
print(ans)

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
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)%mod
al = pow(2,n,mod)-1
ac =comb(n,a)
bc =comb(n,b)
print((al-ac-bc)%mod)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
def sum_product_mod(a, n, m):
    """aから一つずつ引いたのをn回掛ける"""
    res = a
    for i in range(1, n):
        res = res * (a - i) % m
    return res

def pow_mod(n, p, m):
    res = 1
    while p > 0:
        if p & 1:
            res = res * n % m
        p >>= 1
        n = n * n % m
    return res

MOD = 10 ** 9 + 7
all_comb = pow_mod(2, n, MOD) - 1
a_comb = sum_product_mod(n, a, MOD) * pow_mod(sum_product_mod(a, a, MOD), MOD-2, MOD)
b_comb = sum_product_mod(n, b, MOD) * pow_mod(sum_product_mod(b, b, MOD), MOD-2, MOD)
ans = (all_comb - a_comb - b_comb) % MOD
# print(all_comb, a_comb, b_comb)
print(ans)

Submission status: Accepted

Solution code:

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


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

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

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