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 comb(n, r):
    ret = 1
    for i in range(r):
        ret *= n - i
        ret *= pow(i+1, MOD-2, MOD)
        ret %= MOD
 
    return ret % MOD
    
 
ans = pow(2, n, MOD) - 1 - comb(n, a) - comb(n, b)
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n,a,b = [int(x) for x in input().split()]

ans = 0
mod = 10**9+7
ans = (pow(2,n,mod)-1)%mod

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

Submission status: Accepted

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

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


def pow(n, p,mod=10**9+7): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def large_conbination(n,k,mod=10**9+7): #needs pow method. return nCk.
    res1 = 1
    for i in range(n,n-k,-1):
        res1*=i
        res1%=mod
    res2 = 1
    for i in range(1,k+1):
        res2*= i
        res2%=mod
    return res1*pow(res2,mod-2)%mod

ans = pow(2,n)-1

ans -= large_conbination(n,a)
ans -= large_conbination(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 combination(p,k):
    a,b=1,1  
    for i in range(k):
        a*=(p-i)
        a%=mod
        b*=(i+1)
        b%=mod
    return (a*pow(b,mod-2,mod))%mod
print((pow(2,n,mod)-1-combination(n,a)-combination(n,b))%mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
#import numpy as np
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#N = int(input())
#S = str(input())
  
MOD = pow(10, 9) + 7
n, a, b = map(int, input().split())
 
#   (2^n -1 - nCa - nCb) mod MOD
# = ( (2^n - 1 mod MOD) - (nCa mod MOD) - (nCb mod MOD ) ) mod MOD
#   (nCr mod MOD) = ( n*(n-1)*...*(n-r+1) * (a!)^-1 ) mod MOD
# = ( (n mod MOD) * ((n-1) mod MOD) * ... * ((n-r+1) mod MOD) * (r!)^(MOD-2) )  mod MOD

a = min(a, n-a)
b = min(b, n-b)
rMAX = max(a, b)

#分子のmod
nCr_Mol_ModList = [1 for _ in range(rMAX+1)]
#分母（rの階乗）のmod
fac_ModList = [1 for _ in range(rMAX+1)]

nCr_Mol_ModList[1] = n % MOD
fac_ModList[1] = 1 % MOD

for i in range(2, rMAX+1) :
  nCr_Mol_ModList[i] = (nCr_Mol_ModList[i-1] * (n-i+1)) % MOD
  fac_ModList[i] = (fac_ModList[i-1] * i) % MOD

#(2^n - 1 mod MOD) = X
#(nCa mod MOD) = Y
#(nCb mod MOD ) = Z とする

X = pow(2,n,MOD)-1%MOD
Y = ( nCr_Mol_ModList[a] * pow(fac_ModList[a], MOD-2, MOD) )%MOD
Z = ( nCr_Mol_ModList[b] * pow(fac_ModList[b], MOD-2, MOD) )%MOD

ans = (X - Y - Z) % MOD
print (ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
#import numpy as np
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#N = int(input())
#S = str(input())
  
MOD = pow(10, 9) + 7
n, a, b = map(int, input().split())
 
#   (2^n - nCa - nCb) mod MOD
# = ( (2^n - 1 mod MOD) - (nCa mod MOD) - (nCb mod MOD ) ) mod MOD
#   (nCr mod MOD) = ( n*(n-1)*...*(n-r+1) * (a!)^-1 ) mod MOD
# = ( (n mod MOD) * ((n-1) mod MOD) * ... * ((n-r+1) mod MOD) * (r!)^(MOD-2) )  mod MOD

a = min(a, n-a)
b = min(b, n-b)
rMAX = max(a, b)

#分子のmod
nCr_Mol_ModList = [1 for _ in range(rMAX+1)]
#分母（rの階乗）のmod
fac_ModList = [1 for _ in range(rMAX+1)]
nCr_Mol_ModList[1] = n % MOD
fac_ModList[1] = 1 % MOD
for i in range(2, rMAX+1) :
  nCr_Mol_ModList[i] = (nCr_Mol_ModList[i-1] * (n-i+1)) % MOD
  fac_ModList[i] = (fac_ModList[i-1] * i) % MOD

#(2^n - 1 mod MOD) = X
#(nCa mod MOD) = Y
#(nCb mod MOD ) = Z とする

X = pow(2,n,MOD)-1%MOD
Y = ( nCr_Mol_ModList[a] * pow(fac_ModList[a], MOD-2, MOD) )%MOD
Z = ( nCr_Mol_ModList[b] * pow(fac_ModList[b], MOD-2, MOD) )%MOD

ans = (X - Y - Z) % MOD
print (ans)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
m = int(1e9) + 7
ans = (pow(2, n, m) -1) % m
val = 1
val2 = 1
for i in range(a):
    val = (val * (n - i)) % m
    val2 = (val2 * (i + 1)) % m
ans -= (val * (pow(val2, m-2, m)))
#print(((val % m) * (pow(val2, m-2, m))))
val = 1
val2 = 1
for i in range(b):
    val = (val * (n - i)) % m
    val2 = (val2 * (i + 1)) % m
ans -= val * (pow(val2, m-2, m))
#print(((val % m) * (pow(val2, m-2, m))))
print(ans % m)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
m = int(1e9) + 7
ans = (pow(2, n, m) -1) % m
val = 1
val2 = 1
for i in range(a):
    val = (val * (n - i)) % m
    val2 = (val2 * (i + 1)) % m
ans -= (val * (pow(val2, m-2, m)))
#print(((val % m) * (pow(val2, m-2, m))))
val = 1
val2 = 1
for i in range(b):
    val = (val * (n - i)) % m
    val2 = (val2 * (i + 1)) % m
ans -= val * (pow(val2, m-2, m))
#print(((val % m) * (pow(val2, m-2, m))))
print(ans % m)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
m = int(1e9) + 7
ans = (pow(2, n, m) -1) % m
val = 1
val2 = 1
for i in range(a):
    val = (val * (n - i)) % m
    val2 = (val2 * (i + 1)) % m
ans -= ((val % m) * (pow(val2, m-2, m)))
#print(((val % m) * (pow(val2, m-2, m))))
ans %= m
val = 1
val2 = 1
for i in range(b):
    val = (val * (n - i)) % m
    val2 = (val2 * (i + 1)) % m
ans -= ((val % m) * (pow(val2, m-2, m)))
#print(((val % m) * (pow(val2, m-2, m))))
print(ans % (int(1e9) + 7))

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0 
mod = 7+10**9

def expo(x,n):
  var = 1
  while n>0:
    if n%2 == 1:
      var = (var*x) % mod
    x = (x*x)%mod
    n = n>>1
  return var

def combi(n,k):
  N = 1
  K = 1
  for i in range(n-k+1,n+1):
    N = (N*i)%mod
  for i in range(1,k+1):
    K = (K * i)%mod
  return (N*expo(K,mod-2))%mod

print((expo(2,N)-1-combi(N,A)-combi(N,B))%mod)

Submission status: Accepted

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

def ie(n,r,mod):
  if r==1:
    return n
  elif r%2==0:
    return (ie(n,r//2,mod)**2)%mod
  else:
    return n*((ie(n,(r-1)//2,mod))**2)%mod
    
  
for i in range(1,b):
  ors.append(ors[-1]*(n-i)%mod)
  rev.append(rev[-1]*(i+1)%mod)  
N=ie(2,n,mod)
A=ors[a-1]*ie(rev[a-1],mod-2,mod)
B=ors[b-1]*ie(rev[b-1],mod-2,mod)
print((N-A-B-1)%mod)

Submission status: Accepted

Solution code:
def comb_mod(n, k, p):
    """
    nCk mod p
    """
    numerator = 1
    denominator = 1
    for i in range(k):
        numerator *= n - i
        numerator %= p
        denominator *= i + 1
        denominator %= p
    return numerator * pow(denominator, p-2, p) % p

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

for i in (a, b):
    result -= comb_mod(n, i, mod)
result %= mod

print(result)

Submission status: Accepted

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

M = 10**9+7

def pow(x,n,M):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return pow((x % M)**2, n // 2, M)
    if n % 2 == 1:
        return (x % M) * pow((x % M)**2, n // 2, M)

def inv(x,M): #法Mでのxの逆元,Mは素数
    return pow(x,M-2,M) % M

#2**n - 1 - C(n,a) - C(n,b)
Cna_nume,Cna_deno,Cnb_nume,Cnb_deno = 1,1,1,1
for i in range(1,a+1):
    Cna_nume *= (n-i+1)
    Cna_nume %= M
    #まとめてCna_nume *= (n-i+1)%Mとかすると重くなるようだ
    Cna_deno *= i
    Cna_deno %= M
for i in range(1,b+1):
    Cnb_nume *= (n-i+1)
    Cnb_nume %= M
    Cnb_deno *= i
    Cnb_deno %= M
Cna = (Cna_nume * inv(Cna_deno,M)) % M
Cnb = (Cnb_nume * inv(Cnb_deno,M)) % M

print((pow(2,n,M) - 1 - Cna - Cnb) % M)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
mod=10**9+7
A=1
for i in range(n,n-a,-1):
    A*=i
    A%=mod
y=1
for i in range(1,a+1):
    y*=i
    y%=mod
A*=pow(y,10**9+5,mod)
A%=mod
B=1
for i in range(n,n-b,-1):
    B*=i
    B%=mod
y=1
for i in range(1,b+1):
    y*=i
    y%=mod
B*=pow(y,10**9+5,mod)
B%=mod


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

Submission status: Accepted

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

#nCx % mod
def f(x):
  N = 1
  D = 1
  for i in range(x):
    N *= n - i
    N %= mod
    D *= i + 1
    D %= mod
  return N * pow(D, mod-2, mod) % mod

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

Submission status: Accepted

Solution code:

def bigmod(a,n,p):
    if n==0:
        return 1
    elif n%2 == 1:
        return (a*bigmod(a,n-1,p))%p
    else:
        ret = bigmod(a,n//2, p)
        return (ret*ret)%p
p = 10**9+7
def ncr(n,r):
    if n-r<r:
        r = n-r
    den = 1
    for i in range(1,r+1):
        den = (den * i)%p
    den = bigmod(den, p-2, p)

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


if __name__ == "__main__":
    n,a,b = (int(x) for x in input().split())
    ans = bigmod(2,n, p) - 1
    ans -= ncr(n,a)  
    # print(ncr(n,a))  
    ans -= ncr(n,b)
    # print(ncr(n,b)) 

    ans %= p
    if ans<0:
        ans += p

    print(ans)

Submission status: Accepted

Solution code:
import math
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y
def combination(n, r, mod=10**9+7):
  r = min(r, n-r)
  res = 1
  for i in range(r):
      res = res * (n - i) * modinv(i+1, mod) % mod
  return res

def COMint():
  fac[0]=1
  fac[1]=1
  finv[0]=1
  finv[1]=1
  inv[1]=1
  for i in range(2,N+1):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD
def com(n,k):
  if n<k:
    return 0
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
MOD=10**9+7
#繰り返し２乗法を使う場合
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n,a,b=[int(x) for x in input().split()]
ans1 = pow(2,n,MOD)
N = n
a1=combination(n,a)
b1 = combination(n,b)
if ans1-a1%MOD-b1%MOD<0:
  print(((ans1-a1%MOD-b1%MOD)%MOD+MOD)%MOD-1)
else:
  print(ans1-a1%MOD-b1%MOD-1)

Submission status: Accepted

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

for i in range(1,n+1):
    numerator = (numerator*(n-i+1))%mod
    denominator = (denominator*i)%mod
    if i == a or i == b:
        ans = ans - (numerator*pow(denominator,mod-2,mod))%mod
        if i == b:
            break

print(ans%mod)

Submission status: Accepted

Solution code:
# def fac(n):
#     if n == 0:
#         return 1
#     else:
#         return n*fac(n-1)

# def com(n, r):
#     return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
# 繰り返しx乗法x^n
def modpow(x, n, mod):
    ans = 1
    while n > 0:
        if (bin(n & 1) == bin(1)):
            ans = ans * x % mod
        x = x * x % mod
        n = n >> 1
    return ans

def modnc(n, a, mod):
    X = 1
    Y = 1
    for i in range(a):
        X = (X*(n - i)) % mod
        Y = (Y*(a - i)) % mod
    return X, Y

# # フェルマーの小定理
# set p as primary num
# set a as not multiple num of p
# a^(p-1) (mod p) = 1 (mod p)
# a^(p-2) (mod p) = a^(-1) (mod p)

# nCa = n! / (n-a)! * a! = n*n-1*...*n-(a-1)/ a*a-1*...*1 = X/Y
# nCa (mod p)  = X/Y (mod p) = X*Y^(p-2) (mod p) 

p = pow(10, 9) + 7

n, a, b = map(int, input().split())
xa, ya = modnc(n, a, p)
xb, yb = modnc(n, b, p)
ya %= p
yb %= p
nca = xa * modpow(ya, p-2, p) 
ncb = xb * modpow(yb, p-2, p)
ans = (modpow(2, n, p) - nca - ncb - 1) % p
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7
def pow(a, b):
    res = 1
    while b:
        if b & 1: res = res * a % MOD
        a = a**2 % MOD
        b >>= 1
    return res

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

ans = pow(2, n)-1

for X in [a, b]:
    x = 1
    y = 1
    for i in range(X):
        x = x * (n-i) % MOD
        y = y * (i+1) % MOD

    t = x * pow(y, MOD-2) % MOD
    ans -= t

while ans < 0: ans += MOD
print(ans)

Submission status: Accepted

Solution code:
mod=10 ** 9 + 7

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

def power(x,n):
    if n==0:
        return 1
    elif n%2==0:
        half=power(x,n//2)
        return half**2 %mod
    else:
        half=power(x,(n-1)//2)
        return  half**2 * x %mod

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

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

print(ans)

Submission status: Accepted

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


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


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

Submission status: Accepted

Solution code:
#binary exponentiation for 2^big number -1
#sum of n choose. ... 2^n -1
# how to compute n choose a
# euler's quotient theorem
# special case fermats little theoreom


#n kinds of flowers, 1 of each kind
# choose 1 more of each to make bouquet
# a b, total num of flowers cannot be a or b
# how many diff ouquets can she make?
# find the count modulo (10^9 + 7)

#two bouquets are considered different

# (x^y)%p
def powerMod(x,y,p):
    #initialize result
    res = 1
    #update x if it is more than or equal to p
    x = x%p
    
    while (y>0):
        #if y is odd, multiply x with result
        if ((y&1)==1):
            res = (res*x)%p
        
        #y must be even now
        y = y >> 1 #y = y/2
        x = (x*x)%p
    return res

def power(x,y):
    #initialize result
    res = 1
    while (y>0):
        #if y is odd, multiple x with result
        if((y&1)==1):
            res = res*x
        
        #y is even
        y = y >> 1 #divide y by 2
        x = x*x
    return res


input = [int(x) for x in input().split()]
numFlowers = input[0]
a = input[1]
b = input[2]

tenToNine = power(10,9)
allchoices = powerMod(2,numFlowers,tenToNine+7)-1

#compute n choose k in O(k) time and O(1) space
def binomial(n,k):
    #since C(n,k) = C(n,n-k)
    if(k>n-k):
        k = n=k
    
    #initialize result
    res = 1
    #calculate value of simplified n choose k expansion
    for i in range(k):
        res = res*(n-i)
        res = res/ (i+1)
    return res

aX = 1
aY = 1

#need to compute x and y for a and b, clearly separate them
for i in range(a):
    aX = aX*(numFlowers-i)%(tenToNine+7)
    aY = aY*(i+1)%(tenToNine+7)

bX = 1
bY = 1

#need to compute x and y for a and b, clearly separate them
for i in range(b):
    bX = bX*(numFlowers-i)%(tenToNine+7)
    bY = bY*(i+1)%(tenToNine+7)

#subtract and we're done

# countA = aX*powerMod(aY,tenToNine+7-2,tenToNine+7)
# countB = bX*powerMod(bY,tenToNine+7-2,tenToNine+7)
countA = aX*powerMod(aY,tenToNine+7-2,tenToNine+7)
countB = bX*powerMod(bY,tenToNine+7-2,tenToNine+7)
numBouquet = (allchoices-countA-countB)%(tenToNine+7)

print(numBouquet)

Submission status: Accepted

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

a_num = cmb_mod(n,a,mod)
b_num = cmb_mod(n,b,mod)
print((max_cate - a_num - b_num)%mod)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = 10**9+7
def Pow(a, n):
    fac = a
    res = 1
    for i in range(len(bin(n)[2:])):
        if n&1:
            res = res*fac%mod
        fac = fac*fac%mod
        n = n>>1
    return res
cnt = Pow(2, n) - 1
x = [0] * (b+1)
for i in range(1,b+1):
    x[i] = Pow(i, mod-2)
cmb = [0] * (b+1)
cmb[1] = n
for i in range(2, b+1):
    cmb[i] = cmb[i-1]*(n-i+1)%mod*x[i]%mod
cnt -= cmb[a]+cmb[b]
print(cnt%mod)

Submission status: Accepted

Solution code:
n = 10 ** 9
k = 2 * 10 ** 5
mod = 10**9 + 7

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

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

s,a,b = map(int, input().split())
sum = 0
if s == 2:
  pass
else:
  d = pow(2, s, mod) - 1
  sum = d - binomial_coefficients(s, a) - binomial_coefficients(s, b)
while sum < 0:
  sum = sum + mod
print(sum)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

mod=10**9+7

def pow_cal(x,n,mod):
    if n==0:
        return 1
    elif n==1:
        return x%mod
    elif n>=2:
        if n%2==0:
            return (pow_cal(x,n//2,mod)**2)%mod
        else:
            return (x*pow_cal(x,n//2,mod)**2)%mod

def find_power(n,mod):
    # 0!からn!までのびっくりを出してくれる関数(ただし、modで割った値に対してである）
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist

def find_inv_power(n,mod):
    #0!からn!までの逆元を素数modで割ったあまりリストを作る関数
    c=1
    uselist=[0 for i in range(n+1)]
    for i in range(1,n+1):
        c*=i
        c%=mod
    first=pow_cal(c,mod-2,mod)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist
A=find_power(2*10**5,mod)
B=find_inv_power(2*10**5,mod)

d=pow_cal(2,n,mod)-1
p=1
q=1

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

p=p*B[a]%mod

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

q=q*B[b]%mod

print((d-p-q)%mod)

Submission status: Accepted

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

mod=10**9+7

def pow_cal(x,n,mod):
    if n==0:
        return 1
    elif n==1:
        return x%mod
    elif n>=2:
        if n%2==0:
            return (pow_cal(x,n//2,mod)**2)%mod
        else:
            return (x*pow_cal(x,n//2,mod)**2)%mod

def find_power(n,mod):
    # 0!からn!までのびっくりを出してくれる関数(ただし、modで割った値に対してである）
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist

def find_inv_power(n,mod):
    #0!からn!までの逆元を素数modで割ったあまりリストを作る関数
    c=1
    uselist=[0 for i in range(n+1)]
    for i in range(1,n+1):
        c*=i
        c%=mod
    first=pow_cal(c,mod-2,mod)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist
A=find_power(2*10**5,mod)
B=find_inv_power(2*10**5,mod)

d=pow_cal(2,n,mod)-1
p=1
q=1

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

p=p*B[a]%mod

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

q=q*B[b]%mod

print((d-p-q)%mod)

Submission status: Accepted

Solution code:
def mulmod(x, y, p=10**9 + 7):
    return x * y % p


def combmod(n, k, p=10**9 + 7):
    from functools import reduce
    k = min(k, n - k)
    x = reduce(mulmod, range(n - k + 1, n + 1), 1)
    y = reduce(mulmod, range(1, k + 1), 1)
    return x * pow(y, p - 2, p) % p


def solve(string):
    n, a, b = map(int, string.split())
    return str((pow(2, n, 10**9 + 7) - 1 - combmod(n, a) - combmod(n, b)) % (10**9 + 7))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

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
print((pow(2, n, mod) - comb(n, a) - comb(n, b) - 1) % mod)

Submission status: Accepted

Solution code:
import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def comb(n,r,mod):
    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())
    #a,bの制約がなければ，2^n - 1通りだけ使える
    # 2^n ^ nCa - nCb
    mod = 10**9 +7
    nca = comb(n,a,mod)
    ncb = comb(n,b,mod)

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


    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def comb(n: int, k: int, MOD: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    k = min(k, n - k)
    if k == 0:
        return 1
    iinv = [1] * (k + 1)
    ans = n
    for i in range(2, k + 1):
        iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
        ans *= (n + 1 - i) * iinv[i] % MOD
        ans %= MOD
    return ans


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

Submission status: Accepted

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

#n種類の花を使って、花束を作る組み合わせは2^n-1通り
#pow(x,y,mod) : (x**y) % mod
ans = pow(2, n, mod)-1

#nCa
nCa = 1
#分子:n*(n-1)*...*(n-a+1)
for i in range(n-a+1, n+1):
    nCa *= i
    nCa %= mod
#分母:1/a! = 1/(1*2*...*a) = 1^(p-2)*2^(p-2)*,,,*a^(p-2)
for i in range(1, a+1):
    nCa *= pow(i, mod-2, mod)
    nCa %= mod
    
#nCb
nCb = 1
for i in range(n-b+1, n+1):
    nCb *= i
    nCb %= mod
for i in range(1, b+1):
    nCb *= pow(i, mod-2, mod)
    nCb %= mod

#2^n-1通りからnCaとnCbを引く
ans -= (nCa + nCb)
ans %= mod
print(ans)

Submission status: Accepted

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


def comb(n: int, k: int, MOD: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    k = min(k, n - k)
    if k == 0:
        return 1
    iinv = [1] * (k + 1)
    ans = n
    for i in range(2, k + 1):
        iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
        ans *= (n + 1 - i) * iinv[i] % MOD
        ans %= MOD
    return ans


ans = ((1 << n) - 1) % MOD
ans -= comb(n, a, MOD)
ans -= comb(n, b, MOD)
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce

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


def cmb(r):
    numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
    denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
    return numerator * pow(denominator, mod - 2, mod) % mod


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def fac(n,a):
  ans = 1
  for i in range(n,n-a,-1):
    ans *= i
    ans %= mod
  return ans
def cmb(n, a, mod):
    ans = fac(n,a)
    inv = fac(a,a-1)
    return (ans*pow(inv,mod-2,mod)) % mod

n,a,b = map(int,input().split())
mod = 10**9 + 7
#他人のコードパクったけど高速化の理由不明
"""
def pow(n,b,mod):
  if n == 0: return 1
  if n % 2: return 2 * pow(n//2,b,mod)**2 % mod
  else: return pow(n//2,b,mod)**2 % mod"""
print((pow(2,n,mod) - 1 - cmb(n,a,mod) - cmb(n,b,mod))%mod)

Submission status: Accepted

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


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

def inv_fac(n):
    ans=pow(fac(n,n-1),mod-2,mod)
    return ans%mod



ans=pow(2,n,mod)-fac(n,a)*inv_fac(a)-fac(n,b)*inv_fac(b)
print(ans%mod-1)

Submission status: Accepted

Solution code:
from functools import reduce

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


def cmb(r):
    numerator = reduce(lambda x, y: x * y % mod, range(n, n - r, -1))
    denominator = reduce(lambda x, y: x * y % mod, range(1, r + 1))
    return numerator * pow(denominator, mod - 2, mod) % mod


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

Submission status: Accepted

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

Submission status: Accepted

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

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

print((s-x-y)%(10**9+7))

Submission status: Accepted

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

f = 1
for i in range(1, 200001):
  f *= i
  f %= mod

finv = [1]*200001
finv[200000] = pow(f, mod-2, mod)
for i in range(199999, 0, -1):
  finv[i] = finv[i+1]*(i+1)%mod

nCa = 1
for i in range(a):
  nCa *= n-i
  nCa %= mod
nCa *= finv[a]
nCa %= mod
  
nCb = 1
for i in range(b):
  nCb *= n-i
  nCb %= mod
nCb *= finv[b]
nCb %= mod

print((ans-nCa-nCb)%mod)

Submission status: Accepted

Solution code:
MOD = 10**9+7
def comb(n, k):
  res = 1
  for i in range(k):
    res *= n-i
    res %= MOD
    res *= pow(i+1, MOD-2, MOD)
  return res

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

Submission status: Accepted

Solution code:
def pow_mod(a, b, p):
    res = 1
    mul = a
    for i in range(len(bin(b)) - 2):
        if (1 << i) & b:
            res = (res * mul) % p
        mul = (mul ** 2) % p
    return res


def perm_mod(n, r, p):
    res = 1
    for i in range(r):
        res = (res * (n - i)) % p
    return res


def comb_mod(n, r, p):
    r = min(r, n - r)
    return (perm_mod(n, r, p) * pow_mod(perm_mod(r, r, p), p - 2, p)) % p


def main():
    p = 10 ** 9 + 7
    n, a, b = map(int, input().split())
    print((pow_mod(2, n, p) - 1 - comb_mod(n, a, p) - comb_mod(n, b, p)) % p)


main()

Submission status: Accepted

Solution code:
import sys

class modNumber:
    prime = 10**9 + 7
    def __init__(self, num):
        self.num = num % modNumber.prime

    def __add__(self, other):
        if type(other) is int:
            return modNumber(self.num + other)
        return modNumber(self.num + other.num)

    def __sub__(self, other):
        if type(other) is int:
            return modNumber(self.num - other)
        return modNumber(self.num - other.num)

    def __mul__(self, other):
        if type(other) is int:
            return modNumber(self.num * other)
        return modNumber(self.num*other.num)

    def __truediv__(self, other):
        if type(other) is int:
            return modNumber(self.num + modNumber(other).reciprocal())
        return (self*other.reciprocal())

    def __pow__(self, power, modulo=None):
        if type(power) is int:
            answer = 1
            base = self.num
            while True:
                if power == 0:
                    return modNumber(answer)
                elif power%2 == 0:
                    power = power//2
                    base = base*base % modNumber.prime
                else:
                    power = power // 2
                    answer = answer * base % modNumber.prime
                    base = base*base % modNumber.prime
        return self.num.__pow__(power)

    def __str__(self):
        return str(self.num)

    def __int__(self):
        return self.num

    def reciprocal(self):
        ans = modNumber(1)
        buffer = modNumber(self.num)
        exp = modNumber.prime - 2
        while exp:
            if exp & 1:
                ans = ans * buffer
            buffer = buffer * buffer
            exp = exp >> 1
        return ans

if __name__ == '__main__':
    n, a, b = map(int, input().split())

    total = modNumber(2)**n - 1
    # a を引く
    denom = modNumber(1)  # 分母
    numer = modNumber(1)  # 分子
    for i in range(1, a+1):
        denom = denom*i
    for i in range(n-a+1, n+1):
        numer = numer*i
    total -= numer/denom
    # b を引く
    denom = modNumber(1)  # 分母
    numer = modNumber(1)  # 分子
    for i in range(1, b+1):
        denom = denom*i
    for i in range(n-b+1, n+1):
        numer = numer*i
    total -= numer/denom


    print(total)

Submission status: Accepted

Solution code:
from functools import reduce

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

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

    anu = reduce(lambda p1, p2: p1*p2%mod, range(n, n - a, -1))
    ade = reduce(lambda p1, p2: p1*p2%mod, range(1, a + 1))
    ans -= anu*pow(ade, mod - 2, mod)%mod

    bnu = reduce(lambda p1, p2: p1*p2%mod, range(n, n - b, -1))
    bde = reduce(lambda p1, p2: p1*p2%mod, range(1, b + 1))
    ans -= bnu*pow(bde, mod - 2, mod)%mod

    ans %= mod
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = pow(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:
def n_c_k(n, k):
    x = y = 1
    for i in range(k): 
        x *= n - i
        x %= mod
        y *= i + 1
        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 - n_c_k(n, a) - n_c_k(n, b)) % mod 
print(ans)