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=int(input())
n,a,b=map(int,input().split())
#l=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
mod=1000000007

#a!をmodで割ったあまりを求めるO(a)
def facmod(a,mod):
    res=1
    for i in range(1,a+1):
        res=(res*i)%mod
    return res

#a^nをmodでわったあまり 二分累乗法O(logn)
def modpow(a,n,mod):
    res=1
    while n>0:
        if n&1:
            res=(res*a)%mod
        a=(a*a)%mod
        n=n>>1
    return res

#フェルマーの小定理でaの逆元を求める
def modinv(a,mod):
    return modpow(a,mod-2,mod)

ans=(modpow(2,n,mod)-1)%mod

nca=1
ncb=1

#nCa
x=1;y=1
for i in range(n,n-a,-1):
    x=(i*x)%mod
y=facmod(a,mod)
yinv=modinv(y,mod)
nca=(x*yinv)%mod

#nCb
x=1;y=1
for i in range(n,n-b,-1):
    x=(i*x)%mod
y=facmod(b,mod)
yinv=modinv(y,mod)
ncb=(x*yinv)%mod

ans=(ans-nca-ncb)%mod

print(ans)

Submission status: Accepted

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

n,a,b=map(int,input().split())
comb=[1]

for i in range(max(a,b)):
    den=i+1
    num=n-i
    ans=comb[i]*num*pow(den,l-2,l)%l
    comb.append(ans)


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

Submission status: Accepted

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

c_table = [n] * max(a, b)

for i in range(1, len(c_table)):
    numer = n - i
    denom = i + 1
    c_table[i] = c_table[i-1] * numer * pow(denom, mod-2, mod) % mod

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

Submission status: Accepted

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

##逆元計算
N = max(a, b)  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

fact = [ 0 for i in range(N+1)]
factinv = fact.copy()
inv = fact.copy()
cmb_list = fact.copy()

fact[0], fact[1] = 1, 1
factinv[0], factinv[1] = 1, 1
inv[0], inv[1] = 0, 1

for i in range(2, N + 1):
    fact[i] = (fact[i-1] * i) % p##階乗のリスト
    inv[i] = (-inv[p % i] * (p // i)) % p
    factinv[i] =(factinv[i-1] * inv[i]) % p##階乗の逆数のリスト

#分子の計算
n_a_inf_product = 1
for i in range(0, a):
    n_a_inf_product=(n_a_inf_product*(n-i))%p

n_b_inf_product = 1
for i in range(0, b):
    n_b_inf_product=(n_b_inf_product*(n-i))%p

cmb_a = (n_a_inf_product * factinv[a])%p
cmb_b = (n_b_inf_product * factinv[b])%p

ans = (pow(2, n, p) - 1 - cmb_a - cmb_b)%p
print(ans)

Submission status: Accepted

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

c=10**9+7

def com(n,k,c):
    l=1
    m=1
    for i in range(k):
        l*=n-i
        m*=i+1
        l%=c
        m%=c
    return l*pow(m,c-2,c)%c

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

ans%=c

print(ans)

Submission status: Accepted

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

c=10**9+7

nca=1
ncb=1

for i in range(a):
    nca*=(n-i)*pow(i+1,c-2,c)
    nca%=c

for i in range(b):
    ncb*=(n-i)*pow(i+1,c-2,c)
    ncb%=c

ans=pow(2,n,c)-1-(nca+ncb)

ans%=c

print(ans)

Submission status: Accepted

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

c=10**9+7

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

nca=1
ncb=1

for i in range(a):
    nca*=(n-i)*pow(i+1,c-2,c)
    nca%=c

for i in range(b):
    ncb*=(n-i)*pow(i+1,c-2,c)
    ncb%=c

ans-=(nca+ncb)

while ans<0:
    ans+=c

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:

N,a,b = map(int,input().split())
MOD = 10**9 + 7
def comb(n,k, mod):
    m = 1#分子
    l = 1#bunnbo
    for i in range(k):
        m *= n - i
        l *= (i + 1)
        m %= mod
        l %= mod
    return m * pow(l, mod-2, mod) % mod

Sum = pow(2, N, 10**9+7) -1 - comb(N, a, MOD) - comb(N, b, MOD)
Sum = Sum % (10**9+7)
print(Sum)

Submission status: Accepted

Solution code:
#abc156d
m=10**9+7
def com(x,y):
 c=1
 for i in range(1,y+1):
  c=(c*(x-i+1)*pow(i,m-2,m))%m
 return c
n,a,b=map(int,raw_input().split())
print (pow(2,n,m)-1-com(n,a)-com(n,b))%m

Submission status: Accepted

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

def sq(a, b, mod):  # aのb乗を剰余
    if b == 0:
        return 1
    elif b % 2 == 0:
        return sq(a, b // 2, mod)**2 % mod
    else:
        return sq(a, b - 1, mod) * a % mod
  
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 modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
      
mod=10**9+7    
tot=sq(2,n,mod)
prev=1
for i in range(1,min(n+1,2*10**5+1)):
  v=(prev * (n+1-i) % mod * modinv(i, mod) % mod)
  prev=v
  if i==a or i==b:
    tot-=v
    
print((tot-1)%mod)

Submission status: Accepted

Solution code:
#abc156 d

import itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(4100000)
INF = 1 << 60
MOD = 10 ** 9 + 7

#ここから書き始める
def mod_pow(a, n, mod):
    if n == 1:
        return a % mod
    elif n % 2 == 0:
        return mod_pow(a, n/2, mod)**2 % mod
    else:
        return (a * mod_pow(a, n-1, mod)) % mod

def mod_combination(n, r, mod):
    # X = n * n-1 * ... * max(r, n - r)+1
    # Y = min(r, n - r)!
    # nCr = X / Y

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

    Y = math.factorial(min(r, n - r)) % mod
    # フェルマーの小定理 a^(p-1) = 1 (mod p) より
    # a^(-1) = a^(p-2)

    rec_Y = mod_pow(Y, mod - 2, mod)

    return (X * rec_Y) % mod


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

Submission status: Accepted

Solution code:
import math

n,a,b = map(int,input().split())
mod = 10 ** 9 + 7
Xa = 1
Xb = 1
Ya = 1
Yb = 1

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

for i in range(1,a+1):
    Ya = (Ya * i) % mod

for i in range(n,n-b,-1):
    Xb = (Xb * i) % mod

for i in range(1,b+1):
    Yb = (Yb * i) % mod

l = int(math.log2(mod)+1)

P = [0] * l
Q = [0] * l
R = [0] * l
P[0] = 2
Q[0] = Ya
R[0] = Yb

for i in range(1,l):
    P[i] = (P[i-1]**2) % mod
    Q[i] = (Q[i-1]**2) % mod
    R[i] = (R[i-1]**2) % mod

#print(P)
#print(Q)
#print(R)

v2 = 1
vYa = 1
vYb = 1
for i in range(l):
    if n & (2**i) == 2**i:
        v2 *= P[i]
        v2 %= mod
    if ((mod-2) & (2**i)) == 2**i:
        vYa *= Q[i]
        vYa %= mod
        vYb *= R[i]
        vYb %= mod

#print(v2,Xa,Ya,vYa,Xb,Yb,vYb)
print((v2-Xa*vYa-Xb*vYb-1)%(10**9+7))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math

def mod_pow(a, n, mod):
    if n == 1:
        return a % mod
    elif n % 2 == 0:
        return mod_pow(a, n/2, mod)**2 % mod
    else:
        return (a * mod_pow(a, n-1, mod)) % mod

def mod_combination(n, r, mod):
    # X = n * n-1 * ... * max(r, n - r)+1
    # Y = min(r, n - r)!
    # nCr = X / Y

    X = 1
    for i in range(n, max(r, n - r), -1):
        X *= i
        X %= mod
    
    Y = math.factorial(min(r, n - r)) % mod
    # フェルマーの小定理 a^(p-1) = 1 (mod p) より
    # a^(-1) = a^(p-2)

    rec_Y = mod_pow(Y, mod - 2, mod)

    return (X * rec_Y) % mod

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

total = mod_pow(2, n, mod) - 1

comb_a = mod_combination(n, a, mod)

comb_b = mod_combination(n, b, mod)

ans = (total - comb_a - comb_b) % mod

print(int(ans))

Submission status: Accepted

Solution code:
def sq(a, b, mod):  # aのb乗を剰余,kは初期値#20191116-D-Knight
    if b == 0:
        return 1
    elif b % 2 == 0:
        return sq(a, b // 2, mod)**2 % mod
    else:
        return sq(a, b - 1, mod) * a % mod


def nCk(n, k, mod=10 ** 9 + 7):
    x = max(k, n - k)
    y = min(k, n - k)
    kkai = 1
    for i in range(2, y + 1):
        kkai = (kkai * i) % mod
    nkkai = 1
    for i in range(x + 1, n + 1):
        nkkai = (nkkai * i) % mod
    answer = sq(kkai, mod - 2, mod) * nkkai % mod
    return answer

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline


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

    all_case = pow(2, n, mod) - 1
    nCa = conbination(n, a, mod)
    nCb = conbination(n, b, mod)
    result = all_case - nCa - nCb
    while (result < 0):
        result = result + mod
    print(result)


def conbination(n, r, mod):
    a = 1
    b = 1
    for i in range(1, r + 1):
        # print(a, b, i)
        a = (a * (n - i + 1)) % mod
        b = (b * i) % mod
    b = pow(b, mod - 2, mod)

    return (a * b) % mod


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


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


N, A, B = map(int, input().split())
MOD = 10**9+7
print((pow(2, N, MOD)-1-comb(N, A)-comb(N, B)+MOD) % MOD)

Submission status: Accepted

Solution code:
import math

mod = 10**9 + 7
n2 = 2**100 % (mod)
n4 = n2**100 % (mod)
n6 = n4**100 % (mod)
n8 = n6**100 % (mod)


def iip():
    return [int(i) for i in input().split()]

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

def conbination(n, r):
    #print("conbination")
    ret = 1
    for i in range(1, r+1):
        ret *= (i+n-r)
        ret = ret % mod

    ret *= power(math.factorial(r), mod-2)
    ret = ret % mod

    #print(f"conbination {n}, {r} = {ret}")
    return ret

def binaly(n):
    return power(2, n)


def raw(n, a, b):
    d = binaly(n)
    c1 = conbination(n, a)
    c2 = conbination(n, b)
    return d - c1 - c2 - 1

def answer(n, a, b):
    return raw(n, a, b) % (10**9+7)

n, a, b = iip()

#print(factorial(1000000))
#print(math.factorial(1000000)%mod)
print(answer(n, a, b))

Submission status: Accepted

Solution code:
p = int(1e9+7)
def modpow(a, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % p
        a = a * a % p
        n >>= 1
    return res

n, a, b = map(int, input().split())
h = max(a, b)
l = min(a, b)

x = n
y = 1
c_low = x*modpow(y, p-2, p) % p
for i in range(1, h):
    x = x*(n-i) % p
    y = y*(i+1) % p
    if i+1 == l:
        c_low = x*modpow(y, p-2, p) % p
c_high = x*modpow(y, p-2, p) % p

print((modpow(2, n, p) -1 -c_low - c_high) % p)

Submission status: Accepted

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

p = 10**9+7

def f(x, n, p):
    if n == 1:
        return x % p
    if n % 2 == 1:
        return (x * f(x, n-1, p)) % p
    y = f(x, n//2, p)
    return (y**2) % p

def ff(n, m):
    x = 1
    for i in range(n-m+1, n+1):
        x *= i
        x %= p
    return x

res = f(2, n, p) - 1
res -= (ff(n, a) * f(ff(a, a), p-2, p)) % p
res -= (ff(n, b) * f(ff(b, b), p-2, p)) % p

while res < 0:
    res += p

print(res)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n,a,b = nm()
mod = 10**9 + 7
s = pow(2,n,mod) - 1

def fur(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((s - fur(n,a) - fur(n,b)) % mod)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split());k=10**9+7;c=(1<<n)%k-1;X=Y=1
for i in range(b):X=X*(n-i)%k;Y=Y*(i+1)%k;c-=X*pow(Y,k-2,k)if i+1in(a,b)else 0
print(c%k)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split());k=10**9+7;c=(1<<n)%k-1;X=Y=1
for i in range(b):X=X*(n-i)%k;Y=Y*(i+1)%k;c-=X*pow(Y,k-2,k)if i+1 in(a,b)else 0
print(c%k)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split());k=10**9+7;c=(1<<n)%k-1;X=Y=1
for i in range(b):X=X*(n-i)%k;Y=Y*(i+1)%k;c-=X*pow(Y,k-2,k)if i+1 in(a,b) else 0
print(c%k)

Submission status: Accepted

Solution code:
n,*A=map(int,open(0).read().split());k=10**9+7
c=(1<<n)%k-1
for l in A:
	X=Y=1
	for i in range(l):X=X*(n-i)%k;Y=Y*(i+1)%k
	c-=X*pow(Y,k-2,k)
print(c%k)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split());k=10**9+7
c=(1<<n)%k-1
for l in a:
	X=Y=j=Z=1;d=k-2
	for i in range(l):X=X*(n-i)%k
	while j<=l:Y=Y*j%k;j+=1
	while d>0:Z=Z*Y%k if d&1==1 else Z;Y=Y*Y%k;d>>=1
	c-=X*Z%k
print(c%k)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split());k=1000000007
c=(1<<n)%k-1
for l in a:
	X=Y=j=Z=1;d=k-2
	for i in range(l):X=X*(n-i)%k
	while j<=l:Y=Y*j%k;j+=1
	while d>0:Z=Z*Y%k if d&1==1 else Z;Y=Y*Y%k;d>>=1
	c-=X*Z%k
print(c%k)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split());k=1000000007
c=(1<<n)%k-1

X=1
for i in range(a):X=X*(n-i)%k
Y=j=1
while j<=a:Y=Y*j%k;j+=1
#Z=Y**(k-2)を計算，ビットワイズによる繰り返し２乗法の実装。
d=k-2;Z=1
while d>0:
  Z=Z*Y%k if d&1==1 else Z
  Y=Y*Y%k;d>>=1 #一周する度にY, Y^2, Y^4, Y^8となる; dのビット桁をずらす
c-=X*Z%k

X=1
for i in range(b):X=X*(n-i)%k
Y=j=1
while j<=b:Y=Y*j%k;j+=1
d=k-2;Z=1
while d>0:
  Z=Z*Y%k if d&1==1 else Z
  Y=Y*Y%k;d>>=1
c-=X*Z%k

print(c%k)

Submission status: Accepted

Solution code:




def fact(n, r, modp):
    """
    n ~ (n - r + 1)の積 % modpを求める
    """
    curr = n % modp
    for x in range(n - r + 1, n):
        curr *= x
        curr %= modp
    return curr


def power(x, n, modp):
    """
    modつき累乗
    return x^n % modp
    """
    if n == 0:
        return 1

    k = 1
    while n > 1:
        if n % 2:
            k *= x
            k %= modp
        x *= x
        x %= modp
        n //= 2

    return (k * x) % modp


def combination(n, r, modp):
    """
    modつき組み合わせ計算
    return n_C_r % modp
    """ 
    # フェルマーの小定理を利用
    num = fact(n, r, modp)
    den = fact(r, r, modp)

    c = num * power(den, modp - 2, modp)
    return c % modp


def submit():
    n, a, b = map(int, input().split())
    modp = 1000000007
    ans = power(2, n, modp) - combination(n, a, modp) - \
          combination(n, b, modp) - 1
    print(ans % modp)


if __name__ == "__main__":
    submit()

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
p=1000000007
def pmod(N,K,p):
  s=1
  for i in range(K):
    s=(s*(N-i))%p
  return (s)

def bin(N):
    lists=[]
    t=0
    while N>0:
        lists.append(N%2)
        N=N//2
        t=t+1
    lists.append(t)
    return (lists)

def digb(N):
    t=0
    while N>0:
        N=N//2
        t=t+1
    return (t)

def mod(a,N,p):
    listm=[]
    for i in range(digb(N)):#2**(2**i)%pの余を記録
        listm.append(a*bin(N)[i])
        a=(a**2)%p
    s=1
    for i in range(digb(N)):
        if listm[i]!=0:
            s=(s*listm[i])%p
    return(s)

print ((mod(2,n,p)-pmod(n,a,p)*mod(pmod(a,a,p),p-2,p)-pmod(n,b,p)*mod(pmod(b,b,p),p-2,p)-1)%p)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def powmod(x, n,mod):
  if n == 0:
   return 1
  K = 1
  while n > 1:
   if n % 2 != 0:
    K = K * x%mod
    x = x ** 2%mod
    n = (n - 1) // 2
   else:
    x = x ** 2%mod
    n = n // 2%mod

  return K * x # 指数を割り続け n が 1 に至ったら終了

def cmbmod(n, r,mod):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result = result*int(numerator[k])%mod
    return result

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

c=powmod(2, n,10**9+7)
d=cmbmod(n,a,10**9+7)
e=cmbmod(n,b,10**9+7)
print((c-d-e-1)%(10**9+7))

Submission status: Accepted

Solution code:
MOD = 10**9+7

n,a,b = map(int,input().split())
x = []
y = []
tmp1 = 1
tmp2 = 1
for i in range(b+1):
    tmp1 *= (n-i)
    tmp1 %= MOD
    tmp2 *= (i+1)
    tmp2 %= MOD
    x.append(tmp1)
    y.append(tmp2)
A = x[a-1]*pow(y[a-1], MOD-2, MOD)%MOD
B = x[b-1]*pow(y[b-1], MOD-2, MOD)%MOD
print((pow(2,n,MOD)-A-B-1)%MOD)

Submission status: Accepted

Solution code:
class MathUtil:
    # calculate {m+n}C{n}
    def egcd(self, a: int, b: int):
        if a == 0:
            return b, 0, 1
        else:
            g, y, x = self.egcd(b % a, a)
            return g, x - (b // a) * y, y

    def modinv(self, a: int, m: int):
        g, x, y = self.egcd(a, m)
        if g != 1:
            raise Exception('modular inverse does not exist')
        else:
            return x % m

    def combination(self, n: int, r: int, mod: int = 10**9+7) -> int:
        r = min(r, n-r)
        res = 1
        for i in range(r):
            res = res * (n-i) * self.modinv(i+1, mod) % mod
        return res

    def pow(self, x: int, n:int, mod: int = 10**9+7):
        if n == 0:
            return 1

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

            if k >= mod:
                k %= mod
            if x >= mod:
                x %= mod

        return (k * x) % mod 

util = MathUtil()

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

m = 10**9 + 7

if n >= a:
    ca = util.combination(n,a)
else:
    ca = 0

if n >= b :
    cb = util.combination(n,b)
else:
    cb = 0

print( (2 * m + util.pow(2, n) -1 - ca - cb) % m)

Submission status: Accepted

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

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

mod = 10**9 + 7

sum = pow(2, n, mod) - 1
sum -= com(n, a, mod)
sum -= com(n, b, mod)

print(int(sum % mod))

Submission status: Accepted

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

n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
all_patern = pow(2, n, mod) - 1
minus_a = combination(n, a)
minus_b = combination(n, b)
print((all_patern - minus_a - minus_b) % mod)

Submission status: Accepted

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

def comb(n, r, M):
    x = 1
    y = 1
    for i in range(r):
        x = x * (n - i) % M
        y = y * (i + 1) % M
    return x * pow(y, M - 2, M)
M = 10 ** 9 + 7
print((pow(2, n, M) - comb(n, a, M) - comb(n, b, M) - 1) % M)

Submission status: Accepted

Solution code:

def power(x, y, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    二分累乗法でx ** yを求める
    
    2 ** n = 4 ** (n//2) = 16 ** (n//4)
    みたいなことをする
    """

    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2, mod)**2 % mod
    else            : return power(x, y//2, mod)**2 * x % mod


def mul(a, b, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    modを加味したかけ算を行う
    """
    return ((a % mod) * (b % mod)) % mod

def div(a, b, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    modを加味した割り算を行う    
    """
    if a == b:
        return 1
    return mul(a, power(b, mod-2, mod), mod)


def factorial_part(start, last, mod):
    """
    startからlastまでのかけ算を行う
    
    factorial_part(2, 4, mod) = 2 * 3 * 4 = 24    
    """
    assert(start <= last)
    x = 1
    for k in range(start, last+1):
        x *= k
        x %= mod
    return x


mod = int(1e9) + 7
n, a, b = map(int, input().split())

nCa = div(factorial_part(n - a + 1, n, mod), factorial_part(1, a, mod), mod)
nCb = div(factorial_part(n - b + 1, n, mod), factorial_part(1, b, mod), mod)
n2 = power(2, n, mod)
ans = n2 - nCa - nCb - 1
ans = ans % mod
if ans < 0:
    ans += mod
print(ans)

Submission status: Accepted

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

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

    MOD = int(1e9) + 7

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

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

    for t in [a, b]:
        tmp = 1
        for i in range(N-t+1, N+1):
            tmp = (tmp * i) % MOD
        tmp = (tmp * pow(kai[t], MOD-2, MOD)) % MOD
        ans = (ans - tmp) % MOD
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod = 10**9+7
n,a,b=map(int, input().split())
total = pow(2, n, mod) - 1
comb1 = 1
for i in range(n-a+1, n+1):
    comb1*=i
    comb1%=mod
for i in range(1, a+1):
    comb1*=pow(i, mod-2, mod)
    comb1%=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 = total - comb1 - comb2
print(ans%mod)

Submission status: Accepted

Solution code:
import functools

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

mod = 10**9+7

def mod_square(k):
    table = [False]*32
    squares = [1]*32
    base = 2
    for i in range(0, 32):
        squares[i] = base
        base = (base*base)%mod
    itr = 0
    while k > 0:
        if k & 1:
            table[itr] = True
            # print(itr)
        k >>= 1
        itr+=1
        
    # print(table, squares)
    return functools.reduce(lambda x,y:(x*y)%mod, [squares[i] if table[i] else 1 for i in range(32)])
    

def cmb(n, r, mod=mod):
    # g1[r]: nPr
    # g2[r]: nPr^{-1}
    if (r < 0 or r > n):
        return 0
    r = min(r, n - r)
    return g1[r] * g2[r]  % mod

N = max(a,b)
g1 = [1, n]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

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

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

Submission status: Accepted

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

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

mod = 10**9 + 7

sum = pow(2, N, mod) - 1
sum -= com(N, A, mod)
sum -= com(N, B, mod)

print(int(sum % mod))

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def nCr(n, r):
    if r > n - r:
        return nCr(n, n - r)
    numerator = denominator = 1
    for i in range(r):
        numerator = numerator * (n - i) % MOD
        denominator = denominator * (i + 1) % MOD
    return numerator * pow(denominator, MOD - 2, MOD)


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

Submission status: Accepted

Solution code:
import sys
from scipy.misc import comb
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
nl = lambda: list(map(int, stdin.readline().split()))

n,a,b = na()
mod = 10**9 + 7
s = pow(2,n,mod) - 1
 
def fur(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((s - fur(n,a) - fur(n,b)) % mod)

Submission status: Accepted

Solution code:
n, a, b =map(int, input().split())
p = 10**9 + 7
frac1 = [1]
frac2 = []
for i in range(max(a, b)):
  frac1.append(frac1[i] * (i + 1) % p)
  if i == 0:
    frac2.append(n)
  else:
    frac2.append(frac2[i-1] * (n-i) % p)

def comb(n, k, mod):
    x=frac2[k-1]
    y=frac1[k]
    return (x * pow(y, mod-2, mod)) % mod

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

Submission status: Accepted

Solution code:
import math
import itertools
import numpy as np
n,a,b=map(int,input().split())
mod=10**9+7
def comb(k, r):
    z=1
    for y in range(1,r+1):
        z=z*y%mod
    x=1
    for w in range(k-r+1,k+1):
        x=x*w%mod
    return x*pow(z,mod-2,mod)
c=comb(n,a)
d=comb(n,b)
e=pow(2,n,mod)
print((e-1-c-d)%mod)

Submission status: Accepted

Solution code:
mod = 10**9+7

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

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

print((ans)%mod)

Submission status: Accepted

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

def mpow(a,n):
  if n == 1:
    return a
  x = mpow(a,n//2)
  ans = x*x%mod
  if n%2==1:
    ans *= a
  return ans

def comb(n,a,b):
  if a < b:
    s, l = a, b
  else:
    s, l = b, a
  rs = 1
  for i in range(s):
    rs = rs*(n-i)%mod
  rl = rs
  for i in range(s,l):
    rl = rl*(n-i)%mod
  L = 1
  for i in range(1,s+1):
    L = L*mpow(i,mod-2)%mod
  rs = rs*L%mod
  rl = rl*L%mod
  for i in range(s+1,l+1):
    rl = rl*mpow(i,mod-2)%mod
  if a < b:
    nCa, nCb = rs, rl
  else:
    nCa, nCb = rl, rs
  return nCa, nCb
nCa,nCb = comb(n,a,b)
print((mpow(2,n)-1-nCa-nCb)%mod)
# print(nCa,nCb)

Submission status: Accepted

Solution code:
mod = 10**9+7
def cmb(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

def __main():
    n,a,b = map(int, input().split())
    sum = pow(2,n,mod) - 1
    elm1 = cmb(n,a)
    elm2 = cmb(n,b)
    ans = (sum-(elm1+elm2))%mod
    print(ans)
__main()

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
mod = 1000000007
ans = pow(2,n,mod) - 1

def solve(nu):
    res = 1
    for i in range(nu):
        res *= n-i
        res %= mod
        res *= pow(i+1,mod-2,mod)
        res%=mod
    return res

ans -=solve(a)
ans %= mod
ans -= solve(b)
ans %= mod

print(ans)

Submission status: Accepted

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

##############################################
#https://tane-no-blog.com/976/
mod = pow(10, 9) + 7
 
def comb(N, x):
    #n*(n-1)*…*(n-1+1)を計算
    numerator = 1
    for i in range(N-x+1, N+1):
        numerator = numerator * i % mod
    
    #a!を計算 
    denominator = 1
    for j in range(1, x+1):
        denominator = denominator * j % mod
        
    #最後の項 a!**((10**9+7)-2)を計算
    d = pow(denominator, mod-2, mod)
    
    return numerator * d

################################

comb_all = pow(2,n,mod) - 1 #(2**n) - 1
comb_a = comb(n,a)
comb_b = comb(n,b)

#print(comb_all,comb_a,comb_b)
print((comb_all-comb_a-comb_b)%mod)

Submission status: Accepted

Solution code:
import math
import time

MOD = 10 ** 9 + 7

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

start = time.time()
all_combi = pow(2, n, MOD) - 1


def calc_combi(m):
    x = 1
    for i in range(m):
        x = (x * (n - i)) % MOD
    return x * pow(math.factorial(m), MOD - 2, MOD) % MOD


print((all_combi - (calc_combi(a) + calc_combi(b))) % MOD)

Submission status: Accepted

Solution code:
import math


def comb(n, r, mod):
    # calculates C(n,r) mod p (assuming mod is prime).
    nc = n
    for rc in range(1, r):
        nc -= 1
        n = n*nc % mod
        r = r*rc % mod

    nCr = n*pow(r, mod - 2, mod)
    return nCr


def solve():
    n, a, b = list(map(int, input().split()))
    mod = int(pow(10, 9) + 7)

    total = pow(2, n, mod) - 1
    ac = comb(n, a, mod)
    bc = comb(n, b, mod)
    ans = int(total - ac - bc) % mod

    print(ans)


# Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from sys import stdin


def pow_mod(base, exp, mod):
    if exp == 0:
        return 1

    if exp % 2 == 0:
        t = pow_mod(base, exp/2, mod)
        return t*t % mod
    else:
        # ans=pow_mod(base, exp-1, mod)
        return (base*pow_mod(base, exp-1, mod)) % mod


def modinv(base, mod):
    return pow_mod(base, mod-2, mod)


def cmb(n, k, mod):
    p = 1
    for i in range(n-k+1, n+1):
        p = (p * i) % mod
    d = 1
    for i in range(1, k+1):
        d = (d * i) % mod
    return (p * modinv(d, mod)) % mod


mod = 7+10**9

# S = stdin.readline().rstrip().split()
# N = [int(x) for x in stdin.readline().rstrip().split()][0]
n, a, b = [int(x) for x in stdin.readline().rstrip().split()]
ans = pow_mod(2, n, mod)
ans = (ans-cmb(n, a, mod)) % mod
ans = (ans-cmb(n, b, mod)) % mod
print(ans-1)
# print(cmb(n, b, p))
# print()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:

# sum(nCm) 
# 1:1 1 = 2     2
# 2:1 2 1 = 4
# 3:1 3 3 1 = 8  (1+x)**3
# 4:1 4 6 4 1 = 16
# 5:1 5 10 10 5 1 = 32 (1+x)^5

MOD = 1000000007

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

def modinv(a):
    return modpow(a, MOD-2)

def fact(k):
    d = 1
    for i in range(1, k+1):
        d = (d * i) % MOD
    return d

def C(n, k):
    p = 1
    for i in range(n-k+1, n+1):
        p = (p * i) % MOD
    d = 1
    for i in range(1, k+1):
        d = (d * i) % MOD
    return (p * modinv(d)) % MOD
#for i in range(1, 13): print(modinv(i))
n, a, b = map(int, input().split())
base = modpow(2, n)
base = (base - C(n,a)) % MOD
base = (base - C(n, b)) % MOD
print(base-1)