Problem:


Score : 400 points

Problem Statement

Akari has n kinds of flowers, one of each kind.

She is going to choose one or more of these flowers to make a bouquet.

However, she hates two numbers a and b, so the number of flowers in the bouquet cannot be a or b.

How many different bouquets are there that Akari can make?

Find the count modulo (10^9 + 7).

Here, two bouquets are considered different when there is a flower that is used in one of the bouquets but not in the other bouquet.

Constraints

All values in input are integers.

2 \leq n \leq 10^9

1 \leq a < b \leq \textrm{min}(n, 2 \times 10^5)

Input

Input is given from Standard Input in the following format:

n a b

Output

Print the number of bouquets that Akari can make, modulo (10^9 + 7). (If there are no such bouquets, print 0.)

Sample Input 1

4 1 3

Sample Output 1

7

In this case, Akari can choose 2 or 4 flowers to make the bouquet.

There are 6 ways to choose 2 out of the 4 flowers, and 1 way to choose 4, so there are a total of 7 different bouquets that Akari can make.

Sample Input 2

1000000000 141421 173205

Sample Output 2

34076506

Print the count modulo (10^9 + 7).



Sample input:
4 1 3


Sample output:
7

Submission status: Accepted

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

mod=10**9+7

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

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

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

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

ans = ans - x - y
ans %= mod

print(ans)

Submission status: Accepted

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

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

n, a, b = map(int, input().split())
mod = 10**9 + 7
ans = modpow(2, n, mod) - combination(n, a, mod) - combination(n, b, mod) - 1
while ans < 0:
    ans += mod
print(ans)

Submission status: Accepted

Solution code:
def cmb(n,r,mod):
    if r<0 or r>n:return 0
    return g1[r]*g2[r]%mod


mod=10**9+7
n,a,b=map(int,input().split())
k=max(a,b)
g1=[1,n]
g2=[1,1]
inverse=[0,1]

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

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

Submission status: Accepted

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

ans1, ans2 = 1, 1
N = 3 * 10 ** 5
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
p = MOD
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
    
for i in range(a):
    ans1 = ans1 * (n-i) * inv[1+i] %MOD 
for i in range(b):
    ans2 = ans2 * (n-i) * inv[1+i] %MOD 

print((pow(2, n, MOD) + 2*MOD - 1 - ans1 - ans2)%MOD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod=10**9+7
n,a,b=map(int,input().split())
ans=pow(2,n,mod)-1 #n種類の花を使って花束を作る総数は2^n-1通り
comb1=1 #nCaの計算
for i in range(n-a+1,n+1): #n*(n-1)*…*(n-a+1)を計算
 comb1*=i
 comb1%=mod
for i in range(1,a+1): #1/a!=1/(1*2*…*a)=1^(p-2)*2^(p-2)*…*a^(p-2) (p=10**9+7)を計算
 comb1*=pow(i,mod-2,mod)
 comb1%=mod
comb2=1
for i in range(n-b+1,n+1): #n*(n-1)*…*(n-b+1)を計算
 comb2*=i
 comb2%=mod
for i in range(1,b+1): #1/b!=1/(1*2*…*b)=1^(p-2)*2^(p-2)*…*b^(p-2) (p=10**9+7)を計算
 comb2*=pow(i,mod-2,mod)
 comb2%=mod
ans-=(comb1+comb2) #nCa、nCbを総数から引く
ans%=mod
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def cmbmod(n, r, k):
    #nCr mod kを求める（kは素数）
    p, q = 1, 1
    for i in range(r):
        p = p * (n-i) % k
        q = q * (r-i) % k
    return p * pow(q, k-2, k) % k

n, a, b = [int(_) for _ in input().split()]

const = 10**9 +7

ans = pow(2, n, const)
acmb = cmbmod(n, a, const)
bcmb = cmbmod(n, b, const)
ans = (ans-acmb-bcmb-1) %const

print(ans)

Submission status: Accepted

Solution code:
import sys

# フェルマーの小定理
# ・aはpの倍数ではない
# ・pは素数
# の場合に以下が成り立つ。
# a**(p-1) mod p = 1
def nCr(n, r, mod):
  p = 1
  q = 1
  for i in range(r):
    p = (p * (n - i)) % mod
    q = (q * (r - i)) % mod
  return p * pow(q, mod-2, mod)

n, a, b = map(int, sys.stdin.readline().split())
MOD = 10 ** 9 + 7
ans = pow(2, n, MOD) - 1
ans = (ans - nCr(n, a, MOD) - nCr(n, b, MOD)) % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys

# フェルマーの小定理
# ・aはpの倍数ではない
# ・pは素数
# の場合に以下が成り立つ。
# a**(p-1) = 1
def nCr(n, r, mod):
  p = 1
  q = 1
  for i in range(r):
    p = (p * (n - i)) % mod
    q = (q * (r - i)) % mod
  return p * pow(q, mod-2, mod)

n, a, b = map(int, sys.stdin.readline().split())
MOD = 10 ** 9 + 7
ans = pow(2, n, MOD) - 1
ans = (ans - nCr(n, a, MOD) - nCr(n, b, MOD)) % MOD
print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

# permutation: n * (n-1) * …… * (n-k+1) (mod p)
def prm(n, k, p=10**9+7):
    res = 1
    for i in range(k):
        res = res * (n-i) % p
    return res

# combination: nPk / k! (mod p), note: p must be a prime number
def cmb(n, k, p=10**9+7):
    return prm( n, k ) * pow( prm(k, k), p-2, p ) % p

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

#何も選ばない1通りを除く
ans = pow(2,n,mod) - 1 - cmb(n,a) - cmb(n,b)
print(ans % mod)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

# permutation
def prm(n,k,mod=10**9+7):
    res = 1
    for i in range(k):
        res = res * (n-i) % mod
    return res

def cmb(n,k,mod=10**9+7):
    return prm(n,k) * pow(prm(k,k),mod-2,mod) % mod

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

#何も選ばない1通りを除く
ans = pow(2,n,mod) - 1 - cmb(n,a) - cmb(n,b)
print(ans % mod)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

# permutation
def prm(n,k,mod=10**9+7):
    res = 1
    for i in range(k):
        res = res * (n-i) % mod
    return res

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

ans = pow(2,n,mod) - 1 #何も選ばない1通りを除く
ans = (ans - prm(n,a)*pow(prm(a,a),mod-2,mod)) % mod
ans = (ans - prm(n,b)*pow(prm(b,b),mod-2,mod)) % mod

print(ans)

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
  
answer = pow(2, N, MOD) - f(A) - f(B) - 1
answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

def fact(n,k,mod):
    res = 1
    for i in range(k):
        res = res * (n-i) % mod
    return res % mod

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

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

ans = (ans - fact(n,a,mod)*pow(fact(a,a,mod),mod-2,mod)) % mod
ans = (ans - fact(n,b,mod)*pow(fact(b,b,mod),mod-2,mod)) % mod

print(ans)

Submission status: Accepted

Solution code:
# refer to https://qiita.com/k_karen/items/653ba7025a92f5ac1363
 
# ONE = '1'.freeze
MOD = (10**9) + 7
 
# def inv(x)
#   res = 1 # 最終的に x^(MOD-2) になる変数です
#   beki = x # x^2^n を格納する変数です
#   # MOD-2の２進数展開を下位のbitから見ていきます。
#   (MOD - 2).to_s(2).reverse.chars do |digest|
#     # bitが立っている <=> digest == ONE 
#     # なら resにbekiを掛けます。
#     # ここで、掛け算は計算の都度MODを取れます
#     res = (beki * res) % MOD if digest == ONE
#     # 次のループに備えて、自乗を計算します。
#     # 計算の都度MODを取れます(とても大事なので二回言います)
#     beki = (beki * beki) % MOD
#   end
#   res
# end
 
# def fact(s, e)
#   (s..e).reduce(1) { |r, i| (r * i) % MOD }
# end
 
# def nCk(n, k)
#   k = n - k if k > n - k
#   (fact(k + 1, n) * inv(fact(1, n - k) % MOD)) % MOD
# end
 
def cmb(n, r, p):
    if r > n - r:
        r = n - r
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
 
p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
 
def f(t,k,mod):
    res = 1
    for i in range(k):
        res = res * t % mod
        t -= 1
    return res

def nCk(n,r):
    if r > n - r:
        r = n - r
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    res = 1
    for i in range(r):
      res *= n - i
      res /= i + 1
    return int(res)
    
def fact(n,k,mod):
    res = 1
    for i in range(k):
        res = res * (n-i) % mod
    return res % mod

def pow2(x, n):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = ans*x
    x = x*x
    n = n >> 1 #ビットシフト
  return ans
# A_inv = pow(A,P-2,P)
 
mod = 10 ** 9 + 7
# n = gets.to_i
# s = gets.chomp
# n,a,b = gets.split.map(&:to_i)
n, a, b = map(int, input().split())
cnt_a = cnt_b = 0

# def xgcd(a, b):
#     x0, y0, x1, y1 = 1, 0, 0, 1
#     while b != 0:
#         q, a, b = a // b, b, a % b
#         x0, x1 = x1, x0 - q * x1
#         y0, y1 = y1, y0 - q * y1
#     return a, x0, y0

# def modinv(a, m):
#     g, x, y = xgcd(a, m)
#     if g != 1:
#         raise Exception('modular inverse does not exist')
#     else:
#         return x % m
 
ans = pow(2,n,mod)
ans -= 1
# p [n,ans]
# print(ans)
# print(f(n,a,mod))
# print(f(n,b,mod))
# print(f(4,1,mod))
# p nCk(a,n)
# p fact(b,n)
ans = (ans - fact(n,a,mod)*pow(fact(a,a,mod),mod-2,mod)) % mod
ans = (ans - fact(n,b,mod)*pow(fact(b,b,mod),mod-2,mod)) % mod
# print(fact(n,a,mod)*pow(fact(a,a,mod),mod-2,mod))
# print(a)
# print(fact(a,a,mod))
# print(pow(n,b,mod))
# print(pow(n,b,mod)*modinv(pow(b,b,mod),mod))
 
print(ans)

Submission status: Accepted

Solution code:
import heapq
import sys
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

import functools
@functools.lru_cache(maxsize=None)
def tami(n, x):
	if x == 1:
		return n
	elif x%2 == 0:
		return tami(n, x//2)**2 %mod
	else:
		return tami(n, x-1)*n %mod

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

N,a,b = IL()

n = tami(2, N) -1
aa = nCr(N, a)
bb = nCr(N, b)
ans = n-aa-bb
while ans < 0:
	ans += mod
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

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

n, a, b = [int(x) for x in stdin.readline().rstrip().split()]

DIV = 10**9+7

_n = pow(2, n, MOD)
_a = modcmb(n, a, MOD)
_b = modcmb(n, b, MOD)
ans = _n - _a - _b - 1
print(ans % MOD)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
import math
import copy

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

    fac = [0 for _ in range(2*10**5+1)]
    fac[0],fac[1] = 1,1
    inv = copy.deepcopy(fac)
    invfac = copy.deepcopy(fac)
    
    for i in range(2,2*10**5+1):
        fac[i] = (fac[i-1]*i)%MOD
        inv[i] = MOD-(MOD//i)*inv[MOD%i]%MOD
        invfac[i] = (invfac[i-1]*inv[i])%MOD
        
    def coef(x,y):
        num = (((fac[x]*invfac[y])%MOD)*invfac[x-y]%MOD)
        return num

    def nume(N, r, mod):
        x = 1
        for i in range(1, r + 1):
            x = x * (N-i+1) % mod 
        return x

    s = pow(2,N,MOD) 
    a = nume(N,a,MOD)*invfac[a]
    b = nume(N,b,MOD)*invfac[b]
    ans = (s-1-a-b) % MOD

    print(int(ans))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from functools import reduce
from operator import mul

MOD = 1000000007

def power_func(a, b, mod):
    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, mod)
        return d * d % mod
    if b % 2 == 1:
        return (a * power_func(a, b - 1, mod)) % mod

def nCr(n, r, mod):

    min_r = min(r, n-r)

    if min_r == 1: return n
    if min_r == 0: return 1

    bunsi = reduce(lambda x, y: (x * y) % mod, range(n, n-min_r, -1))
    bunbo = reduce(lambda x, y: (x * y) % mod, range(1, min_r + 1))

    return bunsi * power_func(bunbo, mod - 2, mod) % mod


n, a, b = [int(i) for i in input().split()]

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

Submission status: Accepted

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

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

    s = pow(2,N,MOD) 
    a = Comb(N,a,MOD)
    b = Comb(N,b,MOD)
    ans = (s-1-a-b) % MOD

    print(int(ans))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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


MOD = 10**9 + 7

def getModInv(a, b):
    return 1 if (a == 1) else (1-b*getModInv(b%a, a))//a%b


def modPow(a, b):
    x = 1
    
    while b > 0:
        if b & 1:
            x = (x*a)%MOD

        a = (a**2)%MOD
        b //= 2

    return x


def modComb(n, r):
    p = 1
    q = 1

    for i in range(r):
        p = p*(n-i)%MOD
        q = q*(i+1)%MOD

    return p*getModInv(q, MOD)%MOD



N,A,B = map(int, input().split())
print((modPow(2,N) - modComb(N,A) - modComb(N,B) - 1)%MOD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def comb(n,r,mod=10**9+7):
    cnt = 1
    for i in range(1, r+1): #nCr = n*(n-1)*...(n-r+1)/r!で分母 = cnt
        cnt *= (n-i+1)*pow(i,mod-2,mod) #逆元法 X*Y**(mod-2)%mod。繰り返し2乗法powを使う
        cnt %= mod #値が大きくなるので全てmodで計算
    return cnt

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

ans = (pow(2,n,mod)-1-comb(n,a)-comb(n,b)) % mod #値が大きくなるので全てmodで計算
print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

def mod_combination(n, k, mod = 10 ** 9 + 7):
    def extended_gcd(a, b):
        if b == 0:
            return (a, 1, 0)
        d, x, y = extended_gcd(b, a % b)
        return (d, y, x - (a // b) * y)
    p, q = 1, 1
    for i in range(n - k + 1, n + 1):
        p = (p * i) % mod
    for i in range(2, k + 1):
        q = (q * i) % mod
    return p * (extended_gcd(q, mod)[1] % mod) % mod

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

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

print(ans % mod)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

def power(x, n, mod):
    """
    x**n mod in  O(log n)
    """
    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
    return K * x % mod
 
def nCrMOD(a,b,m):
    c = 1
    for i in range(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

m=10**9+7

ans = power(2,n,m) -1 - nCrMOD(n,a,m) -nCrMOD(n,b,m)
print(ans%m)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

bunbo = 1
bunsi = 1
for i in range(1,a+1):
    bunbo *= i
    bunbo = bunbo%1000000007
    bunsi *= (n+1-i)
    bunsi = bunsi%1000000007
bunbo = pow(bunbo,1000000005,1000000007)
nca = (bunsi*bunbo)%1000000007

bunbo = 1
bunsi = 1
for i in range(1,b+1):
    bunbo *= i
    bunbo = bunbo%1000000007
    bunsi *= (n+1-i)
    bunsi = bunsi%1000000007
bunbo = pow(bunbo,1000000005,1000000007)
ncb = (bunsi*bunbo)%1000000007

ans = (ans-1-nca-ncb)%1000000007
print(ans)

Submission status: Accepted

Solution code:
def combnk_mod(n, k, p):
    # pが素数かつaとpが互いに素であるとき
    # フェルマーの小定理より以下が成り立つ.
    # 1 / a = a ** (p - 2) (mod p)
    # これを使って (1 / k!) mod p を計算する.

    if  2 * k > n:
        k = n - k
    x = 1 # 分母にあたる数 1 / n! mod p
    y = 1 # 分子にあたる数. n! / (n - k)! mod p
    for i in range(1, k + 1):
        x *= pow(i, p - 2, p)
        y *= n - i + 1
        x %= p
        y %= p
    return (x * y) % p

if __name__ == '__main__':
    MOD = 10 ** 9 + 7
    n, a, b = map(int, input().split())
    ans = pow(2, n, MOD) - 1
    ans %= MOD
    for k in [a, b]:
        ans -= combnk_mod(n, k, MOD)
        ans %= MOD
    print(ans)

Submission status: Accepted

Solution code:
import math
n,c,d= map(int, input().split())
mod = pow(10,9)+7

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


ans=(pow(2,n,mod)-1-comb(n,c)-comb(n,d))%mod
print(ans)

Submission status: Accepted

Solution code:
import itertools

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


def ncr(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

sumc = pow(2, n, mod)-1
ac = ncr(n, a, mod)
bc = ncr(n, b, mod)

print((sumc - ac - bc)% mod)

Submission status: Accepted

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

print(ans%MOD)

Submission status: Accepted

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

MOD = 10**9 + 7
fact_inv, inv = [0]*10**6, [0]*10**6

def init_nCk():
    fact_inv[0] = fact_inv[1] = 1
    inv[1] = 1
    for i in range(2,10**6):
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        fact_inv[i] = fact_inv[i-1] * inv[i] % MOD

def nCk(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    ans = 1
    for i in range(n, n-k+1 - 1, -1):
        ans *= i
        ans %= MOD
    return ans * fact_inv[k] % MOD


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

Submission status: Accepted

Solution code:
def solve():
    n, a, b = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    
    for i in range(2, max(a, b)+1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)
    
    def ncr(n, r):
        ret = factinv[r]
        for i in range(n, n-r, -1):
            ret = ret * i % MOD
        return ret
        
    ans = pow(2, n, MOD)
    ans = (ans-ncr(n, a)-ncr(n, b)-1) % MOD
    return ans


print(solve())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from functools import reduce

MOD = 1000000007

def power_func(a, b, mod):
    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, mod)
        return d * d % mod
    if b % 2 == 1:
        return (a * power_func(a, b - 1, mod)) % mod

def nCr(n, r, mod):

    min_r = min(r, n-r)

    if min_r == 1: return n


    bunsi = reduce(lambda x, y: (x * y) % mod, range(n, n-r, -1))
    bunbo = reduce(lambda x, y: (x * y) % mod, range(r, 1, -1))

    return bunsi * power_func(bunbo, mod - 2, mod) % mod


n, a, b = [int(i) for i in input().split()]

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

Submission status: Accepted

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

# でっかい数の n C a
def comb(n, a):
	ret = 1
	# 分子部分の計算
	for i in range(n - a + 1, n + 1):
		ret *= i
		ret %= MOD
	# 分母部分の計算
	for i in range(1, a + 1):
		ret *= pow(i, MOD - 2, MOD)
		ret %= MOD
	return ret
	
ans = pow(2, n, MOD) - 1
ans -= comb(n, a)
ans -= comb(n, b)
print(ans % MOD)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

# from collections import defaultdict
# d = defaultdict(list)

# from itertools import combinations
# comb = combinations(range(N), 2)

# 累積和
# from itertools import accumulate
# _list = list(accumulate(a_list)

# from functools import lru_cache
# @lru_cache(maxsize=None)
# def setUp(self):
#     dp.cache_clear()


# factのstartを指定しとけば, 計算量O(k)になる
def comb(n, k, mod):
    a = factmod(n, n - k + 1, mod)
    b = factmod(k, 1, mod)

    div = pow(b % mod, mod - 2, mod)  # フェルマーの小定理

    return a * div % mod


def factmod(n, start, mod):
    val = 1
    for i in range(start, n + 1):
        val *= i
        val %= mod
    return val


def resolve():
    global dp

    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    # N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    n, a, b = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # h_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    # grid = [[int(x) for x in sys.stdin.readline().split()]
    #         for _ in range    (N)]  # int grid

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


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 1 3"""
        output = """7"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """1000000000 141421 173205"""
        output = """34076506"""
        self.assertIO(input, output)

Submission status: Accepted

Solution code:
MOD = 1000000007
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)
    def __int__(self):
        return self.x

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __mod__(self, other):
        return (
            ModInt(
                other.x
            ) if isinstance(other, ModInt) else
            self.x
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
    
    def __iadd__(self,other):
        self.x += other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self

    def __isub__(self,other):
        self.x += ModInt(MOD - other.x) if isinstance(other, ModInt) else ModInt(MOD - other)
        return self

    def __imul__(self, other):
        self.x *= other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self
    
    def factorical(self,n):
        tmp = ModInt(1)
        for i in range(n):
            tmp *= (i+1)
        return tmp
    
    #m:int MOD
    def modinv(self,a,m=MOD):
        b = m
        u = 1
        v = 0
        while(b):
            t = a//b
            a -= t * b
            a,b = b,a
            u -= t * v
            u,v = v,u
        return ModInt(u)

    def comb(self,n,r):
        n = int(n)
        r = int(r)
        if r > n or n < 0 or r < 0:
            return 0
        m = n+1
        nterms = min(r, n-r)
        numerator = ModInt(1)
        denominator = ModInt(1)
        for j in range(1, nterms + 1):
            numerator *= m - j
            denominator *= j
        return numerator * self.modinv(denominator.x)
        
if __name__ == "__main__":
    n,a,b = map(int,input().split())
    c = ModInt(2)
    c = c ** n
    ans = ModInt(c-1)
    ans -= ans.comb(n,a)
    ans -= ans.comb(n,b)
    print(ans)

Submission status: Accepted

Solution code:
MOD = 1000000007
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)
    def __int__(self):
        return self.x

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __mod__(self, other):
        return (
            ModInt(
                other.x
            ) if isinstance(other, ModInt) else
            other
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
    
    def __iadd__(self,other):
        self.x += other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self

    def __isub__(self,other):
        self.x += ModInt(MOD - other.x) if isinstance(other, ModInt) else ModInt(MOD - other)
        return self

    def __imul__(self, other):
        self.x *= other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self
    
    def factorical(self,n):
        tmp = ModInt(1)
        for i in range(n):
            tmp *= (i+1)
        return tmp
    
    #m:int MOD
    def modinv(self,a,m=MOD):
        b = m
        u = 1
        v = 0
        while(b):
            t = a//b
            a -= t * b
            a,b = b,a
            u -= t * v
            u,v = v,u
        return ModInt(u)

    def comb(self,n,r):
        n = int(n)
        r = int(r)
        if r > n or n < 0 or r < 0:
            return 0
        m = n+1
        nterms = min(r, n-r)
        numerator = ModInt(1)
        denominator = ModInt(1)
        for j in range(1, nterms + 1):
            numerator *= m - j
            denominator *= j
        return numerator * self.modinv(denominator.x)
        
if __name__ == "__main__":
    n,a,b = map(int,input().split())
    c = ModInt(2)
    c = c ** n
    ans = ModInt(int(c-1))
    ans -= ans.comb(n,a)
    ans -= ans.comb(n,b)
    print(ans)