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:
from functools import reduce

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

def f(A):
    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


ans = pow(2, N, MOD) - f(A) - f(B) - 1
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
mod = 10**9 + 7
N = 10**6 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2,N):
  inv += [inv[mod % i] * (mod - int(mod / i)) % mod]
  fac += [(fac[i-1] * i) % mod]
  finv += [(finv[i-1] * inv[i]) % mod]
t=(pow(2,n,mod)-1+mod)%mod
sa1,sa2,sb1,sb2=1,1,1,1
for i in range(1,a+1):
  sa1*=(n-i+1)
  sa1%=mod
sa=sa1*finv[a]%mod
for i in range(1,b+1):
  sb1*=(n-i+1)
  sb1%=mod
sb=(sb1*finv[b])%mod
print((t-sa-sb+mod)%mod)

Submission status: Accepted

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

X, Y = 1, 1
for i in range(min(a, b)):
    X *= n - i
    X %= t
    Y *= i + 1
    Y %= t
ans -= (X * pow(Y, t-2, t)) % t
if ans < 0:
    ans += t
for i in range(min(a, b), max(a, b)):
    X *= n - i
    X %= t
    Y *= i + 1
    Y %= t
ans -= (X * pow(Y, t-2, t)) % t
if ans < 0:
    ans += t

print(ans)

Submission status: Accepted

Solution code:
Q = 10**9+7

def cmb(n,r):
    if n-r < r: r = n-r
    if r == 0: return 1
    denominator = 1                       #分母
    numerator = 1                         #分子
    for i in range(r):
        numerator *= n-i
        numerator %= Q
        denominator *= i+1
        denominator %= Q
    return numerator*pow(denominator, Q-2, Q)%Q

def main():
    n, a, b = map( int, input().split())
    print( (pow(2,n,Q) - cmb(n,a) - cmb(n,b)-1)%Q)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
mod = 10**9+7
ans = pow(2,n,mod)-1
fact = [1]*(2*10**5+1)
for i in range(2,2*10**5+1):
  tmp = fact[i-1]*i
  tmp %= mod
  fact[i]=tmp
  
def comb(n,k):
  k = min(k,n-k)
  fa = 1
  for i in range(n,n-k,-1):
    fa*=i
    fa%=mod
  return fa*pow(fact[k],mod-2,mod)
mi = comb(n,a)+comb(n,b)
mi%=mod
ans-=mi
ans%=mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def ncr(n, r, p):
    # initialize numerator
    # and denominator
    num = den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den,
                      p - 2, p)) % p


def power(x, y, p):
    res = 1  # Initialize result

    # 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
p=1000000007
n,a,b=map(int,input().split())
t=pow(2,n,p)-1-ncr(n,a,p)-ncr(n,b,p)
print(t%p)

Submission status: Accepted

Solution code:
import math

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


def cmb(n, r, mod):
    c=1
    for i in range(1, r+1):
        c = (c * (n-i+1) * pow(i, mod-2, mod)) % mod
    return c


mod = 10**9+7

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp


def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

def main():
    n,a,b=mis()
    print((pow(2, n, N1097) - comb(n, a, N1097) - comb(n, b, N1097) - 1) % N1097)

main()

Submission status: Accepted

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

def nCk(N, K, m):
  ret = 1  
  for k in range(K):
    ret = (ret *(n - k)) %m
    
  inv = [1 for _ in range(K+1)]
  finv = [1 for _ in range(K+1)]
  for i in range(2, K+1):
    inv[i] = m - inv[m%i]*(m//i)%m
    finv[i] =finv[i-1] * inv[i]%m
    
  return (ret*finv[K])%m


print((pow(2,n,m)-nCk(n,a,m)-nCk(n,b,m)-1)%m)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
mod = 10**9 + 7
N = 10**6 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2,N):
  inv += [inv[mod % i] * (mod - int(mod / i)) % mod]
  fac += [(fac[i-1] * i) % mod]
  finv += [(finv[i-1] * inv[i]) % mod]
def pow(x, n):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = ans*x%mod
    x = x*x%mod
    n = n >> 1 #ビットシフト
  return ans
t=(pow(2,n)-1+mod)%mod
sa1,sa2,sb1,sb2=1,1,1,1
for i in range(1,a+1):
  sa1*=(n-i+1)
  sa1%=mod
sa=sa1*finv[a]%mod
for i in range(1,b+1):
  sb1*=(n-i+1)
  sb1%=mod
sb=(sb1*finv[b])%mod
print((t-sa-sb+mod)%mod)

Submission status: Accepted

Solution code:
import sys
from functools import reduce

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, A, B = lr()
MOD = 10 ** 9 + 7

def F(A):
    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

answer = pow(2, N, MOD) - F(A) - F(B) - 1
print(answer % MOD)

Submission status: Accepted

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

MOD = 1000000007
ans = (pow(2, n, MOD) - 1) % MOD

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

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

Submission status: Accepted

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

for i in range(k-1):
  fact[i+1] = (fact[i] * (n - i) * pow((i+1), mod -2 , mod))% mod


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

Submission status: Accepted

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

mod = 10**9 + 7


def cmb(n, r, mod):
    r = min(n-r, r)
    if r == 0:
        return 1
    over, under = 1, 1
    for i in range(1, r+1):
        over = over * (n-i+1) % mod
        under = under * i % mod
    inv = pow(under, mod-2, mod)
    return over * inv % mod


A = cmb(n, a, mod)
B = cmb(n, b, mod)

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

Submission status: Accepted

Solution code:
n,a,b=map(int, input().split())
 
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

mod=10**9+7

if n==2:
    print(0)
else:
    print((pow(2,n,mod)-1-comb(n,a,mod)-comb(n,b,mod))%mod)

Submission status: Accepted

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


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


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

Submission status: Accepted

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

mod = 1000000007

def modpow(a, p):
  if p == 0:
    return 1
    
  if p % 2 == 0:
    x = modpow(a, p//2) % mod
    ans = x * x % mod
  else:
    ans = a * modpow(a, p-1) % mod
  
  return ans

def modcombi(x, y):
  if x < y:
    return 0
  elif y == 0:
    return 1
  elif y > x-y:
    return modcombi(x, x-y)
  
  num = 1
  denom = 1
  
  for i in range(y):
    num *= (x-i)
    num %= mod
    denom *= (i+1)
    denom %= mod
  
  ans = num * modpow(denom, mod-2)
  return ans % mod

print( ( 2 * mod + modpow(2,n) - modcombi(n, a) - modcombi(n, b) ) % mod - 1)

Submission status: Accepted

Solution code:
n,a,b=map(int, input().split())
 
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

mod=10**9+7
    
A=comb(n,a,mod)
B=comb(n,b,mod)  
C=pow(2,n,mod)

if n==2:
    print(0)
else:
    print((C-1-A-B)%mod)

Submission status: Accepted

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

def nck(n,r,mod):
    r=min(n,r)
    if r==0:
        return 1
    num,inv_num=1,1
    for i in range(1,r+1):
        num=num*(n-i+1)%mod
        inv_num=inv_num*i%mod
    return num*pow(inv_num,mod-2,mod)%mod

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

Submission status: Accepted

Solution code:
import sys
import math
MOD = 10 ** 9 + 7

input = sys.stdin.readline
n,a,b = map(int,input().split())
x1 = 1

a = min(a,n-a)
b = min(b,n-b)
if a > b:
    a,b = b,a

for i in range(n-a+1,n+1):
    x1 = x1 * i % MOD
x11 = 1
for i in range(1,a+1):
    x11 = x11 * i % MOD
x1 = x1 * pow(x11,MOD-2,MOD) % MOD

x2 = x1
for i in range(n-b+1,n-a+1):
    x2 = x2 * i % MOD
x21 = 1
for i in range(a+1,b+1):
    x21 = x21 * i % MOD
x2 = x2 * pow(x21,MOD-2,MOD) % MOD

t = []
nn = n
while nn > 0:
    t.append(nn % 2)
    nn //= 2
x0 = 1
for i in range(len(t)):
    x0 = x0 ** 2
    x0 = x0 % MOD
    if t[len(t)-i-1] == 1:
        x0 *= 2
        x0 = x0 % MOD
print ((x0 - x1 - x2 - 1) % MOD)

Submission status: Accepted

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

Submission status: Accepted

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

s, l = min(a, b), max(a, b)
s_factorial_inv = s_factorial_upper = l_factorial_inv = l_factorial_upper = m = 1

while True:
    if m <= s:
        s_factorial_inv *= m
        s_factorial_inv %= LARGE
        s_factorial_upper *= n - s + m
        s_factorial_upper %= LARGE
    if m <= l:
        l_factorial_inv *= m
        l_factorial_inv %= LARGE
        l_factorial_upper *= n - l + m
        l_factorial_upper %= LARGE
    else:
        break
    m += 1

nCs = pow(s_factorial_inv, LARGE - 2, LARGE) * s_factorial_upper
nCl = pow(l_factorial_inv, LARGE - 2, LARGE) * l_factorial_upper

print((pow(2, n, LARGE) - nCs - nCl - 1 + LARGE) % LARGE)

Submission status: Accepted

Solution code:
class Combination:
    '''MOD上の
    計算量：階乗・逆元テーブルの作成O(N)
    nCkを求めるO(1)'''

    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [pow(self.fact[i], MOD - 2, MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

    def combination2(self, k, r):
        """kCrを求める O(r)
        kが大きいときに使える
        """
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.MOD
        return (res * self.inv_fact[r]) % self.MOD

n, a, b = list(map(int, input().split()))
MOD = 10 ** 9 + 7
comb = Combination(2 * 10 ** 5 + 10, MOD)

ptn_a = comb.combination2(n, a)
ptn_b = comb.combination2(n, b)
ptn_n = pow(2, n, MOD) - 1

print((ptn_n - ptn_a - ptn_b) % MOD)

Submission status: Accepted

Solution code:
p = 10 ** 9 + 7
n,a,b = map(int,input().split())
k=max(a,b)
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
com=[0]*(k+1)
com[0]=1
for i in range(1, k+1):
  com[i]=((com[i-1]*(n-i+1))*modinv(i,p))%p
print((pow(2,n,p)-1-com[a]-com[b])%p)

Submission status: Accepted

Solution code:
def cmb(n, r):
	if n - r < r:
		r = n - r
	if r == 0:
		return 1
	if r == 1:
		return n
	
	num = [n - r + k + 1 for k in range(r)] #numerator(分子)
	den = [k + 1 for k in range(r)] #denominator(分母)
	
	for p in range(2, r + 1):
		pivot = den[p - 1]
		if pivot > 1:
			offset = (n - r) % p
			for k in range(p - 1, r, p):
				num[k - offset] /= pivot
				den[k] /= pivot
	
	result = 1
	for k in range(r):
		if num[k] > 1:
			result *= int(num[k])
			result = result % mod
	
	return result

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

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

Submission status: Accepted

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

INF = (10**9 + 7)

def c(n,r,p):
    r = min(r,n-r)
    numer = 1
    denom = 1
    for i in range(1,r+1):
        numer = numer * (n+1-i) % p
        denom = denom * i % p
    return numer * pow(denom,p-2,p) % p

ans = pow(2,n,INF) - 1 - c(n,a,INF) - c(n,b,INF)

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

Submission status: Accepted

Solution code:

N, a, b=(int(i) for i in input().split())
import math
p = 10 ** 9 + 7
def binary(n):
    return bin(n)[2:]

# バイナリ法
def pow_by_binary_exponentiation(k, x, n): # a^x mod n
    x = [int(l) for l in binary(x)]
    y = k
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * k) % n
    return y

ans=(pow_by_binary_exponentiation(2,N,p)-1)
combA=1
combB=1
for i in range(a):
    combA*=(N-i)
    combA%=p
for i in range(b):
    combB*=(N-i)
    combB%=p

print((ans - combA*pow_by_binary_exponentiation(math.factorial(a), p-2, p) - combB*pow_by_binary_exponentiation(math.factorial(b), p-2,p))%p)

Submission status: Accepted

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


def binary(n):
    return bin(n)[2:]


# a^x mod n : ans = pow_by_binary_exponentiation(2, 1000, 10**9+7)
def pow_by_binary_exponentiation(a, x, n):
    x = [int(b) for b in binary(x)]
    y = a
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * a) % n
    return y


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


ac = combination(n, a, mod)
bc = combination(n, b, mod)
ans = pow_by_binary_exponentiation(2, n, mod)
print(((ans - ac - bc - 1) % mod)//1)

Submission status: Accepted

Solution code:
def comb(a, b, p=10 ** 9 + 7):
    if (b > a - b):
        return comb(a, a - b, p)
    c = d = 1
    for i in range(b):
        c *= (a - i)
        d *= (b - i)
        c %= p
        d %= p
    return c * modpow(d, p - 2, p) % p


def modpow(n, p, m=10 ** 9 + 7):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (modpow(n, p // 2, m) ** 2) % m
    return (modpow(n, p - 1, m) * n) % m


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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

  inv_b=mod_inv(b,mod)
  # print(a,inv_b)
  return a*inv_b

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
            K%=mod
        x *= x
        n //= 2
        x%=mod

    return (K * x)%mod

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

def main():
  n,a,b=LI()
  if n==2:
    if a!=b:
      return 0
    else:
      return 1

  ans=pow_k(2,n)

  ans-=(cmb(n,a,mod)%mod)
  ans-=(cmb(n,b,mod)%mod)

  ans-=1
  ans%=mod

  if ans<0:
    ans+=mod

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)]) 

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

def main():
    n,a,b = inpm()
    ans = pow(2,n,mod) - 1
    ans += mod
    ans -= combination(n,a,b)
    print(ans%mod)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

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

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

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

print(ans % MOD)

Submission status: Accepted

Solution code:
def pow2(n, mod):
    p = 2
    r = 1
    while n:
        if n % 2:
            r = r * p % mod
        p = (p * p) % mod
        n //= 2
    return r

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

def nCr(n, r, mod):
    t = 1
    r = min(r, n - r)
    for i in range(n - r + 1, n + 1):
        t = t * i % mod
    return t * g2[r] % mod



def prep(n, mod):
    for i in range(2, n):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

def main():
    n, a, b = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    prep(2 * (10 ** 5) + 1, mod)
    print((pow2(n, mod) - 1 - nCr(n, a, mod) - nCr(n, b, mod))% mod)


main()

Submission status: Accepted

Solution code:
import sys
import math
MOD = 10 ** 9 + 7

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a):
    x = extgcd(a,MOD)[0]
    return (MOD+x%MOD)%MOD

input = sys.stdin.readline
n,a,b = map(int,input().split())
x1 = 1

a = min(a,n-a)
b = min(b,n-b)
if a > b:
    a,b = b,a

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

x2 = x1
for i in range(n-b+1,n-a+1):
    x2 = x2 * i % MOD
x21 = 1
for i in range(a+1,b+1):
    x21 = x21 * i % MOD
x2 = x2 * mod_inv(x21) % MOD

t = []
nn = n
while nn > 0:
    t.append(nn % 2)
    nn //= 2
x0 = 1
for i in range(len(t)):
    x0 = x0 ** 2
    x0 = x0 % MOD
    if t[len(t)-i-1] == 1:
        x0 *= 2
        x0 = x0 % MOD
print ((x0 - x1 - x2 - 1) % MOD)

Submission status: Accepted

Solution code:
def ncr(n, r, p): 
    num = den = 1 
    for i in range(r): 
        num = (num * (n - i)) % p 
        den = (den * (i + 1)) % p 
    return (num * pow(den, p - 2, p)) % p
  
p = 10**9+7
n,a,b = map(int,(input().split()))

bb = ncr(n,a,p)+ncr(n,b,p)+1
print((pow(2,n,p)-(bb%p))%p)

Submission status: Accepted

Solution code:
M = 10 ** 9 + 7

def mod_combination(n, r, mod):
    numerator = 1
    for i in range(n-r+1, n+1):
        numerator = (i * numerator) % mod
    denominator = 1
    for i in range(1, r+1):
        denominator = (i * denominator) % mod
    fermat = pow(denominator, mod-2, mod)
    return (numerator * fermat) % mod

def solve(n, a, b):
    k = pow(2, n, M)
    ac = mod_combination(n, a, M)
    ab = mod_combination(n, b, M)

    ans = k - ac - ab - 1
    while ans < 0:
        ans += M
    return ans

if __name__ == "__main__":
    n, a, b = tuple(map(int, input().split(" ")))
    print(solve(n, a, b))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
n, a, b = [int(x) for x in input().strip().split()]
mod = 10 ** 9 + 7
ans = pow(2, n, mod) - 1

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

inv = [1] * (b + 1)
inv[-1] = pow(fact[-1], mod-2, mod)
for i in range(1, b):
    inv[-1-i] = (inv[-1-i+1] * (b-(i-1))) % mod

def nCr(n, r):
    ret = 1
    for i in range(r):
        ret = (ret * (n - i) % mod) % mod
    return (ret * inv[r]) % mod

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

Submission status: Accepted

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

class remainder():
    def __init__(self, mod=(10**9 + 7)):
        self.mod = mod
    
    def sub(self, a, b):

        return (a + self.mod - b) % self.mod
    
    def mul(self, a, b):

        return ((a % self.mod) * (b % self.mod)) % self.mod

    def pow(self, a, b):
        bp = []
        #bp.append(1)
        bp.append(a)

        n = len(bin(b)) - 2
        for x in range(n):
            bp.append(bp[x]**2 % self.mod)

        res = 1
        for x in range(n):
            if b >> x & 1:
                #res = re.mul(res, bp[x])
                res = (res * bp[x]) % self.mod
        
        return res

    def div(self, a, b):
        
        return self.mul(a, self.pow(b, self.mod - 2))

com = [0] * (B + 1)
com[0] = 1

re = remainder()

ans = re.pow(2, N) - 1
for x in range(1, B + 1):
    s = re.sub(N, x) + 1
    d = re.div(s, x)
    com[x] = re.mul(com[x - 1], d)


subA = com[A]
subB = com[B]

ans = re.sub(ans, subA)
ans = re.sub(ans, subB)

print(ans)

Submission status: Accepted

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

 
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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def cmb(n, r, mod):
    r = min(n-r, r)
    if r == 0:
        return 1
    over, under = 1, 1
    for i in range(1, r+1):
        over = over * (n-i+1) % mod
        under = under * i % mod
    inv = pow(under, mod-2, mod)
    return over * inv % mod


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

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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


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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

n,a,b=map(int,input().split())
MOD=10**9+7
def pos(x, n, m):
    if n == 0:
        return 1
    res = pos(x*x%m, n//2, m)
    if n%2 == 1:
        res = res*x%m
    return res

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

na=comb(n,a)
nb=comb(n,b)

ans=(pos(2,n,MOD)-na-nb-1)%MOD

print(ans)

Submission status: Accepted

Solution code:
N, a, b = map(int, input().split())
M = 1000000007


def mod_comb_k(n, k):
    n_P_n_k = 1
    fact_k = 1
    for i in range(k):
        n_P_n_k = n_P_n_k * (n - i) % M
        fact_k = fact_k * (i + 1) % M
    return n_P_n_k * pow(fact_k, M-2, M)

ans = (pow(2, N, M) - 1 - mod_comb_k(N, a) - mod_comb_k(N, b)) % M
print(ans)

Submission status: Accepted

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

MOD = 10 ** 9 + 7


def ncr(n, r, p):
    # initialize numerator
    # and denominator
    num = den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den, p - 2, p) + p) % p


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

Submission status: Accepted

Solution code:
def binary(n):
    return bin(n)[2:]

def pow_by_binary_exponentiation(a, x, n):  # a^x mod n
    x = [int(b) for b in binary(x)]
    y = a
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * a) % n
    return y

 # mを法とするaの乗法的逆元
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


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


mod = 10**9 + 7
X = combination(n,a)
Y = combination(n,b)
Z = pow_by_binary_exponentiation(2,n,mod) - 1
W = (Z - X - Y) % mod
if W < 0:
    W += mod
print(W % mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def ncr(n, r, p): 
  num = den = 1 
  for i in range(r): 
      num = (num * (n - i)) % p 
      den = (den * (i + 1)) % p 
  return (num * pow(den, p - 2, p)) % p
p=10**9+7
n,a,b = map(int,(input().split()))
bb = ncr(n,a,p)+ncr(n,b,p)+1
print((pow(2,n,p)-(bb%p))%p)

Submission status: Accepted

Solution code:
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
 
N,A,B = map(int,input().split())
if (N == 2):
    print(0)
else:
    print((2**N - 1 - combination(N, A) - combination(N, B)) % (10**9+7))

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

ans = 0
total = pow(2, n, MOD)


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


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

Submission status: Accepted

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


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


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