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 = list(map(int, input().split()))
MAX = 510000
MOD = 1000000007


fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]
com = [0 for i in range(MAX)]
power = [2 for i in range(32)]

for i in range(1, 32) :
  power[i] = power[i-1] * power[i-1] % MOD

def cominit() :
  fac[0] = fac[1] = 1
  finv[0] = finv[1] = 1
  inv[1] = 1
  com[1] = n
  for i in range(2, MAX) :
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * int(MOD / i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD
    com[i] = com[i-1] * (n-(i-1)) * inv[i] % MOD
    
  return fac, finv, inv, com


def two_n_mod(n) :
  ans = 1
  temp_i = 0
  temp = [0 for i in range(32)]
    
  for i in range(32) :
    temp[i] += n%2
    n = int(n/2)
  ans = (2**n) % MOD
  for i in range(32) :
    ans = ans * (power[i] ** temp[i]) % MOD
  return ans

temp = cominit()
##print(two_n_mod(1000000000))
##print(2**n % MOD)
print((two_n_mod(n) - 1 - com[a] - com[b]) % MOD)

Submission status: Accepted

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

if __name__=="__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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


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

sumComb= pow(2, n, mod) 
# print(sumComb)
aComb = calcCombination(n, a, mod)
# print(aComb)
bComb = calcCombination(n, b, mod)
# print(bComb)
ans = ( sumComb - 1 - aComb - bComb ) % mod

print(int(ans))

Submission status: Accepted

Solution code:
from functools import reduce

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


def cmb(N, 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) - cmb(N, A) - cmb(N, B) - 1
ans = ans % MOD
print(ans)

Submission status: Accepted

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

from functools import reduce
 
def nCr(n,r,DIV):
  f=lambda x,y:x*y%DIV
  X=reduce(f,range(n-r+1,n+1))
  Y=reduce(f,range(1,r+1))
  return X*pow(Y,DIV-2,DIV)%DIV

DIV = 10**9+7

ans = pow(2, n, DIV)
ans -= 1
ans -= nCr(n,a,DIV)
ans -= nCr(n,b,DIV)

print(ans%DIV)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
M = 10**9 + 7
n, a, b = map(int, input().split())
r = pow(2, n, M) - 1
f = c = 1
for i in range(b):
  f = f * (i + 1) % M
  c = c * (n - i) % M
  if i + 1 == a:
    a = b
    r -= c * pow(f, M - 2, M)
print(r % M)

Submission status: Accepted

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

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

q = 1
for i in range(n,n-b,-1):
    q *=i
    q %= mod
q_inv = 1
for i in range(1,b+1):
    q_inv *= i
    q_inv %= mod
q *= pow(q_inv,mod-2,mod)

ans -= p
ans -= q
ans %= mod
print(ans-1)

Submission status: Accepted

Solution code:
import math

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

 
def comb(n,k,mod):
    """power_funcを用いて(nCk) mod p を求める"""
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    k=min(n-k,k)
    #分母
    deno=1
    #分子
    mole=1

    for i in range(1,k+1):
        mole=mole*(n-i+1)%mod
        deno=deno*i%mod

    return (mole*pow(deno,mod-2,mod))%mod


def power_func(a,b,p):
    """a^b mod p を求める"""
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
    return d*d %p
    
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p

mod=10**9+7
print((pow(2,n,mod)- 1 - comb(n,a,mod) - comb(n,b,mod))%mod)
#2**n - 1 -nCa -nCb

Submission status: Accepted

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

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

ans = pow(2,n,M) - 1
ans -= nCr(n,a,M)
ans -= nCr(n,b,M)
ans %= M
if ans<0: ans += M
print(ans)

Submission status: Accepted

Solution code:
def comb_mod(a: int, b: int, mod: int = 10**9+7) -> int:
    """Returns Comb(a, b) % mod
    Precondition: mod is prime
    Complexity: O(min(a-b, b))
    :param a:
    :param b:
    :param mod: a prime number
    :return:
    """
    b = min(b, a-b)

    res = 1
    for x in range(a-b+1, a+1):
        res = res * x % mod

    # Using Fermat's little theorem
    # a^{p-1} = 1 mod p
    # a^{p-2} = a^{-1} mod p
    for x in range(1, b+1):
        res = res * pow(x, mod-2, mod) % mod

    return res


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def cmb(n, r, mod):
    if r < 0 or n < r:
        return 0
    r = min(r, n - r)
    numerator, denominator = 1, 1
    for i in range(1, r + 1):
        numerator = (numerator * (n + 1 - i)) % mod
        denominator = (denominator * i) % mod
    return numerator * pow(denominator, mod - 2, mod) % mod


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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def choose(n,r):
    res = 1
    fac = 1
    for i in range(r):
        res *= n-i
        res %= MOD
        fac *= i+1
        fac %= MOD
    return res*pow(fac,MOD-2,MOD)%MOD        

n,a,b = list(map(int,input().split()))
MOD = 10**9+7
t=0
ans = pow(2,n,MOD)-1


ans -= choose(n,a)
ans -= choose(n,b)

ans = ans % MOD
print(int(ans))

Submission status: Accepted

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

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

ans -= nCr(N,A)
ans -= nCr(N,B)

print(ans%MOD)

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, a, b = map(int, input().split())
    ans = pow(2, n, MOD)

    comb = 1
    for i in range(1,b+1):
        comb *= n-i+1
        comb *= pow(i, MOD-2, MOD)
        comb %= MOD
        if i == a or i ==b :
            ans -= comb

    print((ans-1)%MOD)
resolve()

Submission status: Accepted

Solution code:
import time
from math import factorial

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

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):
    a=1
    for i in range(n, n-k, -1):
        a=a * i % mod
    b=framod(k, mod)
    return (a * power(b, mod-2, mod)) % mod

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

fn=2*10**5
fac=[0]*fn
fac[1]=n

print((power(2, n, mo)-1-comb(n,a,mo)-comb(n,b,mo))%mo)

Submission status: Accepted

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

ans=pow(2,n,mod_num)

def get_combi_mod(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

ans-=1
ans-=get_combi_mod(n,a,mod_num)
ans-=get_combi_mod(n,b,mod_num)
print(ans%mod_num)

Submission status: Accepted

Solution code:
import time



n,a,b = map(int,input().split())
start = time.time() # 時間計測開始

M = 10**9+7

# 2**n
twon = pow(2,n,M)

# nCr+1 = nCr * (n-r)/(r+1)
# nCr = A(r)とおくと ※nは固定
# A(r+1) = A(r) * (n-r)/(r+1)
# ここでmod M では、フェルマーの小定理より
# 1/(r+1) === (r+1)**(M-2) ※===は合同記号の意味
# よって　A(r+1) = A(r) * (n-r) * (r+1)**(M-2)
# L = [0] * (2*(10**5) + 1)
# L[0] = 1
# for i in range(len(L)-1):
#     L[i+1] = ( L[i] * (n-i) * pow(i+1,M-2,M) ) % M

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



# nCa
# nCa = L[a]
nCa = comb_mod(n,a,M)
# nCb
# nCb = L[b]
nCb = comb_mod(n,b,M)

ans = twon - 1 - nCa - nCb

elapsed_time = time.time() - start # 時間計測終了
# print(elapsed_time)
print(ans % M)

Submission status: Accepted

Solution code:

mod = 1000000007


def sub(a, b):
    return (a - b + mod) % mod


def mul(a, b):
    return a * b % mod


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


def comb(n, r):
    """ nCr % mod
    Equivalent to comb(n, r) in Python 3.8
    """
    num = 1
    den = 1
    for i in range(r):
        num = mul(num, n - i)
        den = mul(den, i + 1)
    return div(num, den)


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

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

Submission status: Accepted

Solution code:

import sys,math
import numpy as np

#n=int(sys.stdin.readline())
n,a,b=map(int,sys.stdin.readline().split())
#a=np.array([sys.stdin.readline().split() for i in range(n)],np.int64)

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


def C(N,K):
    if N<K:
        return 0
    else:
        c=1
        d=1
        for i in range(1,K+1):
            c=c*(n-i+1)%p
            d=d*i%p
        return c*pow(d,p-2,p)%p
print((to-C(n,a)-C(n,b))%p)

Submission status: Accepted

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

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

MOD = 10 ** 9 + 7

def myPow(x, n, MOD):
    if n == 0:
        return 1

    res = 1
    while(n > 0):
        if n & 1 == 1:
            res = res * x % MOD

        x = x * x % MOD
        n = n >> 1

    return res


ans = pow(2, N, MOD)
ans -= 1

def cumprod(arr, MOD):
    L = len(arr)
    Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]
        arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]
        arr[n] %= MOD
    return arr.ravel()[:L]


def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64)
    x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64)
    x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv


fact, fact_inv = make_fact(B + 10, MOD)

arr = cumprod(list(range(N, N-B, -1)), MOD)

a = arr[A - 1] * fact_inv[A]
a %= MOD
b = arr[B-1] * fact_inv[B]
b %= MOD

# print(mb)
# print(fact_inv)

'''
a = ma * fact_inv[A]
a %= MOD

b = mb * fact_inv[B]
b %= MOD
'''

ans -= (a + b)
ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# submission # - User: herp_sy
# https://atcoder.jp/contests/
#
# lang: Python3 (3.4.3)

import math
import statistics
import numpy as np
import queue
import itertools
import functools 

# define
TBMod = int(1e+9 + 7)

# nCr(int, int, devider)
def nCr(n, r, mod):
	f = lambda x, y : x * y % mod
	x, y = functools.reduce(f, range(n - r + 1, n + 1)), \
		functools.reduce(f, range(1, r + 1))
	return x * pow(y, mod - 2, mod) % mod

n,a,b = map(int, input().split())
print((pow(2, n, TBMod) - (nCr(n, a, TBMod) + nCr(n, b, TBMod)) - 1) % TBMod)

Submission status: Accepted

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


def calc(n):
    ret = 1
    for i in range(n):
        ret = ret * (N - i) % MOD
    return ret * pow(factorial(n), MOD - 2, MOD) % MOD


print(max(0, (pow(2, N, MOD) - ((calc(A) + calc(B)) % MOD) - 1) % MOD))

Submission status: Accepted

Solution code:
def calc_mod_comb(x, y):
  numerator = 1
  for i in range(y):
    numerator = (numerator * (x-i))%modval
  denominator = 1
  for i in range(1, y+1):
    denominator = (denominator * i)%modval
  denominator = pow(denominator, modval-2, modval)
  return (numerator * denominator)%modval

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

a_combs = calc_mod_comb(n, a)
b_combs = calc_mod_comb(n, b)

ans = (pow(2, n, modval) - 1 - a_combs - b_combs)%modval

print(ans)

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

num = 1
den = 1
for i in range(a):
    den = (den * (i+1)) % mod
    num = (num * (n-i)) % mod
ans = (ans - (num * pow(den, mod-2, mod)) % mod ) % mod

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

print(ans)

Submission status: Accepted

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

M = 10**9+7

# 2**n
twon = pow(2,n,M)

# nCr+1 = nCr * (n-r)/(r+1)
# nCr = A(r)とおくと ※nは固定
# A(r+1) = A(r) * (n-r)/(r+1)
# ここでmod M では、フェルマーの小定理より
# 1/(r+1) === (r+1)**(M-2) ※===は合同記号の意味
# よって　A(r+1) = A(r) * (n-r) * (r+1)**(M-2)
L = [0] * (2*(10**5) + 1)
L[0] = 1
for i in range(len(L)-1):
    L[i+1] = ( L[i] * (n-i) * pow(i+1,M-2,M) ) % M
# nCa
nCa = L[a]

# nCb
nCb = L[b]

ans = twon - 1 - nCa - nCb

print(ans % M)

Submission status: Accepted

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

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

Submission status: Accepted

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

mod = 1000000007

def modpow(a,n,m):
    x = 1
    while n:
        if n%2: x *= a
        a *= a
        a %= m
        n //= 2
    return x

def nCr(n,r,m):
    a = b = 1
    for i in range(r):
        a *= n - i
        b *= r - i
        a %= m
        b %= m
    return a * modpow(b, m-2, m) % m

ans = modpow(2,n,mod) - 1
ans -= nCr(n,a,mod)
ans -= nCr(n,b,mod)
ans %= mod
if ans<0: ans += mod
print(ans)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = 10**9+7
s = pow(2, n, mod)-1
x = 1
y = 1
for i in range(1, b+1):
    x = x*(n-i+1)%mod
    y = y*i%mod
    if i==a or i==b:
        s -= x*pow(y, mod-2, mod)

print(s%mod)

Submission status: Accepted

Solution code:
def main():
    n, a, b = map(int, input().split())
    mod = 10**9+7
    s = pow(2, n, mod)-1
    x = 1
    y = 1
    for i in range(1, b+1):
        x = x*(n-i+1)%mod
        y = y*i%mod
        if i==a or i==b:
            s -= x*pow(y, mod-2, mod)

    print(s%mod)

main()

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = 10**9+7
"""
def factorial_mod(x, y, mod):
    factorial = 1
    for i in range(x,y+1):
        factorial *= i
        factorial %= mod
    return factorial


#conbinationを何回も求める場合はfactorial_k,nkをあらかじめ計算し, リストに入れておけば良い
def n_C_k(n,k,mod):
    factorial_nk = factorial_mod(n-k+1, n, mod)
    factorial_k = factorial_mod(1,k,mod)
    conbi=factorial_nk*pow(factorial_k, mod-2, mod)
    return conbi%mod

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

#n!を求める
def factorial_mod(n, mod):
    x = 1
    for i in range(1, n+1):
        x *= i
        x %= mod
    return x

#n_P_kを求める
def permutation_mod(n, k, mod):
    x = 1
    for i in range(n-k+1, n+1): #k回for文を回す
        x *= i
        x %= mod
    return x

#conbinationを何回も求める場合はfactorial_k,nkをあらかじめ計算し, リストに入れておけば良い
def n_C_k(n, k, mod): #O(min(k, n-k))
    k = min(k, n-k)
    n_P_k = permutation_mod(n, k, mod)
    factorial_k = factorial_mod(k, mod)
    conbi=n_P_k * pow(factorial_k, mod-2, mod)
    return conbi % mod

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

Submission status: Accepted

Solution code:
mod = 10**9+7
n,a,b = [int(i) for i in input().split()]
k = min(n,2*(10**5))
import sys
sys.setrecursionlimit(100000000)
def pow_k(a,n,mod):
    if n == 0:
        return 1
    if n % 2 ==0:
        return pow_k(a*a % mod,n//2,mod)
    else:
        return a * pow_k(a,n-1,mod) % mod
def modinv(a, mod):
    return pow(a, mod-2, mod)
def combination_list(n, mod):
    lst = [1]
    for i in range(1, k+1):
        lst.append(lst[-1] * (n+1-i) % mod * modinv(i, mod) % mod)
    return lst
ans = pow_k(2,n,mod)
cmb = combination_list(n,mod)
ans -=1
ans -= cmb[a]
if ans < 0:
    ans += mod
ans -= cmb[b]
if ans <0:
    ans += mod
print(ans)

Submission status: Accepted

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

MOD=10**9+7
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

print((pow(2,N,MOD) - comb(N , A) - comb(N , B) - 1 ) % MOD )

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = 10**9 + 7
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
c = comb(n, a)
d = comb(n, b)
answer = pow(2, n, mod) - 1
print((answer-c-d)%mod)

Submission status: Accepted

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

from functools import reduce

def nCr(n,r,DIV):
  f=lambda x,y:x*y%DIV
  X=reduce(f,range(n-r+1,n+1))
  Y=reduce(f,range(1,r+1))
  return X*pow(Y,DIV-2,DIV)%DIV

DIV=10**9+7

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

Submission status: Accepted

Solution code:
n, a, b = map(int,input().split())
mod = 10**9+7
total = pow(2, n, mod) - 1
def c(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

print((total - c(n, a) - c(n, b))%mod)

Submission status: Accepted

Solution code:
import sys
[n,a,b] = [int(s) for s in sys.stdin.read().split()] #リスト作成

mod = 10**9+7
def comb(p,q,A): #pCq modA
  X = 1
  Y = 1
  for i in range(1, q+1):
    X = (X*(p-i+1))%A
    Y = (Y*i)%A
  return (X*pow(Y, A-2, A))%A #X*Y^(-1) modA
print((pow(2,n,mod)-comb(n,a,mod)-comb(n,b,mod)-1)%mod)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

#output
mod = pow(10, 9) + 7

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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


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

print((ans-modComb(n,a,mod)-modComb(n,b,mod)) % mod)

Submission status: Accepted

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

def modComb(n,r,mod):
    tmp = 1
    # r = min(r,n-r)
    for i in range(1,r+1):
        tmp = tmp * (n-i+1) % mod
        tmp = tmp * pow(i,mod-2,mod)
    
    return tmp % mod


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

print((ans-modComb(n,a,mod)-modComb(n,b,mod)) % mod)

Submission status: Accepted

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

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


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

print((ans-modComb(n,a,mod)-modComb(n,b,mod)) % mod)

Submission status: Accepted

Solution code:
mod=10**9+7
import math

def co(n,r,mod):
    x=1
    y=1
    for i in range(1,r+1):
        x=(x*(n-i+1))%mod
        y=(y*i)%mod
    return (x*pow(y,mod-2,mod))%mod
    
n,a,b=map(int,input().split())
ans=pow(2,n,mod)-1-co(n,a,mod)-co(n,b,mod)
print(max(ans%mod,0))#ansにmod取らないと無理

Submission status: Accepted

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

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

cnt += pow(2,n,mod) - 1
cnt -= C(n,a)
cnt -= C(n,b)

print(max(0,cnt%mod))

Submission status: Accepted

Solution code:
def nrc_mod(n, r, mod=10**9+7):
    r = min(n - r, r)
    if r == 0:
        return 1
 
    over = 1
    for i in range(n, n - r, -1):
        over = over * i % mod
 
    under = 1
    for i in range(1, r + 1):
        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

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

Submission status: Accepted

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

def inv(a):
    return pow(a, (10**9 + 7) - 2, (10**9 + 7))
    
    
t = pow(2, n, 10**9 + 7) - 1
x = 1
y = 1
for i in range(a):
    x *= (n - i)
    x %= (10**9 + 7)
    y *= (a - i)
    y %= (10**9 + 7)
    
f = (x * inv(y)) % (10**9 + 7)
x = 1
y = 1

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

print((t - f - s + (10**9 + 7)) % (10**9 + 7))

Submission status: Accepted

Solution code:
def nrc_mod(n, r, mod=10**9+7):
    r = min(n - r, r)
    if r == 0:
        return 1

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

    under = 1
    for i in range(1, r + 1):
        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

# 0本を選ぶは無しなので-1
# 取るか取らないかの２択がn種類ある
ans = pow(2, n, MOD) - 1
ans -= nrc_mod(n, a, MOD)
ans -= nrc_mod(n, b, MOD)
while ans < 0:
    ans += MOD
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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


def comb_mod(n, k, mod):
    numerator = 1
    denominator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % mod
        denominator = (denominator * (i + 1)) % mod

    return (numerator * pow(denominator, mod - 2, mod)) % mod


n_c_a = comb_mod(n, a, mod)
n_c_b = comb_mod(n, b, mod)

result = (pow(2, n, mod) - 1 - n_c_a - n_c_b) % mod
print(result)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
MOD = 10**9+7

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


def cmb(n, r, mod):
    x = 1
    y = 1
    for i in range(1, r + 1):
        x = (x * (n - i + 1)) % MOD
        y = (y * i) % MOD

    return (x * pow(y, MOD - 2, MOD)) % MOD


ans = pow(2, n, MOD) - 1 - cmb(n, a, MOD) - cmb(n, b, MOD)
if ans < 0:
    while ans < 0:
        ans += MOD
print(ans)

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 = map(int, input().split())

MOD = 10 ** 9 + 7

def comb(n, r):
    ret = 1
    for i in range(r):
        ret *= n - i
        ret %= MOD
    for i in range(r):
        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 = map(int, input().split())
mod = 10 ** 9 + 7


def comb_mod(n, k, mod):
    numerator = 1
    denominator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % mod
        denominator = (denominator * (i + 1)) % mod

    return ((numerator % mod) * (pow(denominator, mod - 2, mod) % mod)) % mod


n_c_a = comb_mod(n, a, mod)
n_c_b = comb_mod(n, b, mod)

result = ((pow(2, n, mod) - 1) % mod - n_c_a - n_c_b) % mod
print(result)

Submission status: Accepted

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


def comb_mod(n, k, mod):
    numerator = 1
    denominator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % mod
        denominator = (denominator * (i + 1)) % mod

    return ((numerator % mod) * (pow(denominator, mod - 2, mod) % mod)) % mod


n_c_a = comb_mod(n, a, mod)
n_c_b = comb_mod(n, b, mod)

result = (pow(2, n, mod) - 1 - n_c_a - n_c_b) % mod
print(result)

Submission status: Accepted

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


def comb_mod(n, k, mod):
    numerator = 1
    denominator = 1
    for i in range(k):
        numerator = numerator * (n - i) % mod
        denominator = denominator * (i + 1) % mod

    return ((numerator % mod) * (pow(denominator, mod - 2, mod) % mod)) % mod


n_c_a = comb_mod(n, a, mod)
n_c_b = comb_mod(n, b, mod)

result = (pow(2, n, mod) - 1 - n_c_a - n_c_b) % mod
print(result)

Submission status: Accepted

Solution code:
def fermat_binom(n,k,p):
  if k > n:
    return 0
  num = 1
  for i in range(n,n-k,-1):
    num = (num*i)%p
  denom = 1
  for i in range(1,k+1):
    denom = (denom*i)%p
  return (num * pow(denom,p-2,p))%p

if __name__ == '__main__':
  n, a, b = map(int, input().split())
  mod = 1000000007 
  k = pow(2, n, mod)
  r = k- 1- fermat_binom(n, a, mod) - fermat_binom(n, b, mod)
  r = (r%mod+mod)%mod
  print(max(r, 0))

Submission status: Accepted

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

count=0
mod=1000000007

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

count+=pow(2,n,mod)
#print(count)
count-=1
count-=C(n,a)
#print(count)
count-=C(n,b)

print(max(0,(count)%mod))

Submission status: Accepted

Solution code:
def cmb(n, r, mod):
    p, q = 1, 1
    for i in range(r):
        p *= n - i
        p %= mod
        q *= i + 1
        q %= mod
    # 1/q!の逆元をかける(= q! ^ (mod-2) % mod)
    return p * pow(q, mod - 2, 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 = 1000000007

def pow(a, b):
    ret = 1
    while b > 0:
        if b%2 == 1:
            ret = ret*a%MOD
        a = a*a%MOD
        b //= 2
    return ret

def mul(s, e):
    ret = 1
    for i in range(s, e+1):
        ret = ret*i%MOD
    return ret

def fact(n):
    return mul(1, n)

def nCr(n, r):
    return mul(n-r+1, n) * pow(fact(r), MOD-2) % MOD

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

Submission status: Accepted

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

mod = 10 ** 9 + 7
k = max(a,b)
com = [1]

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

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