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:
# ANSHUL GAUTAM
# IIIT-D

# from math import *
from copy import *
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from sys import stdin
from sys import maxsize
# from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
4 1 3
'''

def nCr(n, r):
	num = den = 1
	mod = 10**9 + 7
	for i in range(r):
		num = (num * (n - i)) % mod
		den = (den * (i + 1)) % mod
	return (num * pow(den,mod - 2, mod)) % mod

def solve(n,a,b):
	mod = 10**9 + 7
	ans = pow(2,n,mod)
	ans -= nCr(n,a)
	ans -= nCr(n,b)
	return max(0,(ans-1)%mod)

n,a,b = map(int, stdin.readline().rstrip().split())
ans = solve(n,a,b)
print(ans)

Submission status: Accepted

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

def reduce(ans, r):
    c = n % mod
    for i in range(1, r):
        c *= ((n - i) % mod) * pow(i + 1, mod - 2, mod)
        c %= mod
    ans -= c
    if ans < 0:
        ans += mod
    return ans % mod
    
ans = reduce(ans, a)
ans = reduce(ans, b)
print(ans)

Submission status: Accepted

Solution code:
import math
n,a,b = map(int,input().split())
mod = 10**9+7
k = 2
def Base_10_to_n(X,k):
  if (int(X/k)):
    return Base_10_to_n(int(X/k),k)+str(X%k)
  return str(X%k)
STR = Base_10_to_n(n,k)
ans = 1
cur = 2
for i in range(len(STR)):
    if STR[len(STR)-1-i] == '1':
        ans *= cur
        ans = ans%mod
    cur *= cur
    cur %= mod
    
ans -= 1
ans = ans%mod
L = [a,b]
cur = n
cur2 = n
for i in range(1,a):
    cur *= (n-i)*(pow(i+1, mod-2, mod))
    cur %= mod
for i in range(1,b):
    cur2 *= (n-i)*(pow(i+1, mod-2, mod))
    cur2 %= mod
cur %= mod
cur2 %= mod
ans -= cur
ans -= cur2
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,k):
    temp=1
    k=min(k,n-k)
    for i in range(1,k+1):
        temp=temp*pow(i,mod-2,mod)
        temp=temp*(n-i+1)%mod

    return temp%mod
#二分累乗法を勉強する
ans=pow(2,n,mod)-1-comb(n,a)-comb(n,b)
print(ans%mod)

Submission status: Accepted

Solution code:
mod = 1000000007

# 繰り返し二乗法  
def mod_pow(a, n, p):
    if n == 1:
        return a % p
    if n % 2 == 1:
        return (a* mod_pow(a, n - 1, p)) % p
    tmp = mod_pow(a, n / 2, p)
    return ( tmp * tmp ) % p

# 組み合わせ
def mod_cmb(n, k, p):
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if (k > n - k):
        return mod_cmb(n, n - k, p)
    c = d = 1
    for i in range(k):
        c *= (n - i)
        d *= (k - i)
        c %= p
        d %= p
    return c * mod_pow(d, p - 2, p) % p

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

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

    tmp_a = mod_cmb(n , a, mod)
    tmp_b = mod_cmb(n , b, mod)

    print((ans-tmp_a-tmp_b)%mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

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


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


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

print(ret)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


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

    def __str__(self):
        return str(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 __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))
        )


n, a, b = map(int, input().split())
ans = pow(2, n, MOD) - 1
product = ModInt(1)
div = ModInt(1)
for i in range(b + 1):
    product *= (n - i)
    div *= i + 1
    if i == a - 1 or i == b - 1:
        ans -= product / div
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def pow_self(x,n):
    ans = 1
    while n>0:
        if n&1 == 1:
            ans = (ans*x)%(10**9+7)
            
        x = (x*x)%(10**9+7)
        n >>= 1
    return ans

  
n,a,b = map(int, input().split())        
X,Y = 1,1
for i in range(b):
    X *= n-i
    X %= 10**9+7
    Y *= i+1
    Y %= 10**9+7

    if a-1 == i:
        Xa,Ya = X,Y

comb_a = (Xa*pow_self(Ya,10**9+5))%(10**9+7)
comb_b = (X*pow_self(Y,10**9+5))%(10**9+7)

result = pow_self(2,n)-1-comb_a-comb_b
while result <0:
    result += 10**9+7
print(result)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from functools import reduce

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

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())
lim = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

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

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
    
def calc(n, a, m):
    x = 1
    y = 1
    for i in range(a):
        x = (x*(n-i))%m
        y = (y*(i+1))%m
    return (x*pow(y, m-2, m))%m

m = 10**9+7
x = pow(2,n,m)-1
print((x-calc(n,a,m)-calc(n,b,m))%m)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
MOD = 10 ** 9 + 7
# Pythonのpowは繰り返し二乗法で実装されている
ans = pow(2, n, MOD) - 1
product = 1
div = 1
for i in range(1, b + 1):
    product = product * (n - i + 1) % MOD
    div = div * i % MOD
    if i == a or i == b:
        # 逆元を求める
        ans -= product * pow(div, MOD - 2, MOD)
print(ans % MOD)

Submission status: Accepted

Solution code:


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


def nCr(n,r):
    numerator, denominator = 1, 1
    for i in range(r):
        # n * N-1 * ... * n-r+1
        numerator = numerator * (n-i) % MOD
        # r * r-1 * ... * 1
        denominator = denominator * (r-i) % MOD

    # フェルマーの小定理より、aの逆元（逆数）が、a**(m-2)とのこと
    denominator = pow(denominator, MOD-2, MOD)
    return numerator * denominator % MOD

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 共通系になりそう
from math import factorial
import sys, math
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 1000000007

def combination(n, r):
    r = min(r, n - r)
    num = 1
    den = 1
    for i in range(1, r + 1):
        num = (num * (n + 1 - i)) % MOD
        den = (den * i) % MOD
    return num * pow(den, MOD - 2, MOD) % MOD

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

result_ = pow(2, N) - 1 - combination(N, A) - combination(N, B)
print(result_ % MOD)

# powはn剰の時早い

Submission status: Accepted

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


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


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

Submission status: Accepted

Solution code:
#TRE
#pow(m,n)のnが大きい時は繰り返し2乗法を使う

#繰り返し2乗法のアルゴリズム
def modPow (a,n,p):
    if n==1:
        return a % p
    if n%2 == 1:
        return (a * modPow(a,n-1,p)) % p
    else:
        t = modPow(a,n/2,p)
        return t * t


#main
n,a,b = map(int,input().split())
p = 10**9+7
if n == 2 :
    print(0)
else:
#繰り返し2乗法により計算時間を短縮
    ans = modPow(2,n,p)-1#組み合わせのシグマは2のn乗
#組み合わせはn*...*(n-a+1)/(a*...*1)
    child_a = 1
    mother_a = 1
    for i in range(a):
        child_a = (child_a*(n-i))%p
        mother_a = (mother_a*(i+1))%p
    com_a = (child_a * modPow(mother_a,p-2,p)) % p
    child_b = 1
    mother_b = 1
    for i in range(b):
        child_b = (child_b*(n-i))%p
        mother_b = (mother_b*(i+1))%p
    com_b = (child_b * modPow(mother_b,p-2,p)) % p
    ans = (ans -(com_a+com_b))%p
    print(ans%p)

Submission status: Accepted

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

DIV=10**9+7
n,a,b=map(int,input().split())
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

def pow(x, y):
  if y == 0:
    return 1
  K = 1
  while y > 1:
    if y % 2 == 0:
      y = y // 2
      x = (x * x) % MOD
    else:
      K = (K * x) % MOD
      y -= 1
  return (K * (x ** y)) % MOD

def comb_mod(p, q):
  bunsi = 1
  bunbo = 1
  for i in range(q):
    bunsi = (bunsi * (p-i)) % MOD
    bunbo = (bunbo * (i+1)) % MOD
  return ((bunsi * pow(bunbo, MOD - 2)) % MOD)

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

Submission status: Accepted

Solution code:
n, a, b=map(int, input().split())
mod = 10 ** 9 + 7 
def cmb(n, r, mod):
    r = min(r, n -r)
    if r == 0: return 1
    over, under = 1, 1
    for i in range(1, r+1):
        over = over * (n-i+1) % mod
        under = under * i % mod
    
    inv=pow(under, mod-2, mod)
    
    return over*inv % mod
  
print((pow(2,n,mod)-1 - cmb(n, a,mod)-cmb(n,b,mod))%mod)

Submission status: Accepted

Solution code:
input = raw_input

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

from math import factorial

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

#power_dict = {}
# kurikaeshi jijouhou
def power(n, r, mod):
    if r == 0: return 1
    #try:
    #    ret = power_dict[(n, r)]
    #except:
    if True:
        if r%2 == 0:
            ret = power(n*n % mod, r//2, mod) % mod
        if r%2 == 1:
            ret = n * power(n, r-1, mod) % mod
        #power_dict[(n, r)] = ret
    return ret


def comb(n, k, mod):
    k = min(k, n-k)
    bunshi = 1
    bunbo = 1
    for i in range(k):
        bunshi = bunshi * (n-i)
        bunshi = bunshi % M
        bunbo = bunbo * (i+1)
        bunbo = bunbo % M

    ret = (bunshi * power(bunbo, mod-2, mod)) % mod
    #a=framod(n, mod)
    #b=framod(k, mod)
    #c=framod(n-k, mod)
    #return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod
    return ret

#if True:
if False:
    comb_dict = {}
    comb_dict[(1, 0)] = 1
    comb_dict[(1, 1)] = 1

    zenbu2 = 1
    for i in range(2, n+1):
        new_comb_dict = {}
        new_comb_dict[(i, 0)] = 1
        new_comb_dict[(i, i)] = 1
        for j in range(1, i):
            tmp = comb_dict[(i-1, j-1)] + comb_dict[(i-1, j)]
            tmp = tmp % M
            new_comb_dict[(i, j)] = tmp
            if i == n:
                zenbu2 += tmp

        comb_dict = new_comb_dict


#zenbu = 1
#for i in range(n):
#    zenbu = zenbu * 2
#    zenbu = zenbu % M
#
#    assert zenbu not in values, (i, zenbu)
#    values.append(zenbu)
#zenbu = zenbu2

#out = 0
#for i in range(1, n+1):
#    if i == a or i == b:
#        continue
#    tmp = comb(n, i, M)
#    out += tmp

zenbu = power(2, n, M) - 1
#print("zenbu", zenbu)
A = comb(n, a, M)
#print("A", A)
B = comb(n, b, M)
#print("B", B)

out = zenbu - A - B
#out = zenbu - comb_dict[(n, a)] - comb_dict[(n, b)]
out = out % M
print(out)

Submission status: Accepted

Solution code:
#pが素数の時、p未満の数の積xについてx^(p-1)=1(mod p) <=> x^(p-2)=1/x(mod p) (オイラの小定理)
#ここでpは素数なので、p以下の数a,b,nにおいてcmb(n,a)≡n!/((n-a)!*a!)≡((n-a+1)*…*n)/(a!)≡((n-a+1)*…*n)(a!)^(p-2) (mod p)
#あとは((n-a+1)*…*n)(a!)^(p-2) (mod p)を繰り返し2乗法でO(log(p))で求められる…らしいが普通にpow(n,r,mod)つよそう
#ちゃんと実装します



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

def cmb(n,r,mod):
    x=1
    y=1
    for i in range(0,r,1):
        x=(x*(n-i))%mod
        y=(y*(i+1))%mod
    x=x%mod
    y2=modpow(y,mod-2,mod)
    return (x*y2)%mod

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


#print(modpow(2,n,p),cmb(n,a,p),cmb(n,b,p))
print((modpow(2,n,p)-1-cmb(n,a,p)-cmb(n,b,p))%p)

Submission status: Accepted

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


def f(n, a):
    x, y = 1, 1
    for i in range(1, a+1):
        x = x * (n-i+1) % MOD
        y = y * i % MOD
    return x, y


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


ans = modpow(2, N, MOD) - 1
a_x, a_y = f(N, A)
b_x, b_y = f(N, B)

a = a_x * modpow(a_y, (MOD-2), MOD) % MOD
b = b_x * modpow(b_y, (MOD-2), MOD) % MOD
print((ans - a - b) % MOD)

Submission status: Accepted

Solution code:
import math
def f_pow(x,n):
    if n == 0:
        return 1
    half = f_pow(x, n//2)
    if n % 2:
        return x * half * half % mod
    else:
        return half * half % mod

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 * f_pow(q, mod-2)%mod

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

s = f_pow(2, n) - 1
print((s - c(n,a) - c(n,b))%mod)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

mod = 10**9+7 #出力の制限
N = 10**5 * 2
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


n,a,b = m()

nn = str(n)[::-1]

co = 1

tw = [[1] for i in range(10)]
for i in range(9):
    tw[0].append(tw[0][-1] * 2)
for i in range(1,10):
    for j in range(9):
        if j == 0:
            tw[i].append((tw[i-1][-1] * tw[i-1][1])%mod)
        else:
            tw[i].append((tw[i][-1]*tw[i][1])%mod)

for i in range(len(nn)):
    if i == 0:
        co *= tw[i][int(nn[i])]
    else:
        co = (co * tw[i][int(nn[i])])%mod
        co = co % mod

aaa = 1
bbb = 1
for i in range(min(a,n-a)):
    aaa *= (n-i)
    aaa %= mod
    if i == min(a,n-a)-1:
        aaa *= g2[i+1]
        aaa %= mod
for i in range(min(b,n-b)):
    bbb *= (n-i)
    bbb %= mod
    if i == min(b,n-b)-1:
        bbb *= g2[i+1]
        bbb %= mod


print((co - aaa - bbb - 1)%mod)

Submission status: Accepted

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


def powmod(x, y, mod):
    if y == 0:
        return 1
    return (((powmod(x, y >> 1, mod) ** 2) % mod) * x ** (y & 1)) % mod


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


a = cmb(n, a, mod)
b = cmb(n, b, mod)
ans = powmod(2, n, mod) - a - b - 1
print(ans % 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
  P = 1
  F = 1

  for i in range(1,b + 1):
    P = P * (n - i + 1) % MOD #P!
    F = F * i % MOD  # i! 
    if i == a or i == b:
      #Fの逆元のmodをとる
      ans -= P * pow(F,MOD - 2,MOD)
  
  print(ans % MOD)

main()

Submission status: Accepted

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


def choose(x, y):
    v = 1
    for i in range(0, y):
        v = (v * (x - i) * pow(i + 1, m - 2, m)) % m
    return v


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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


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


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
# sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = True
show_flg = False


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


def cmb(n, r):
    p = 1
    c = 1
    for i in range(r):
        p *= (n - i)
        c *= (i + 1)
        p = p % MOD
        c = c % MOD
    return p * modinv(c) % MOD


def main():
    n, a, b = MI()
    first = cmb(n, a)
    second = cmb(n, b)
    ans = pow(2, n, MOD) - 1
    print((ans - first - second) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
def main():
    m = (10 ** 9) + 7
    n, a, b = map(int, input().split())

    a_k = math.factorial(a)
    b_k = math.factorial(b)

    # フェルマーの小定理
    a_k = pow(a_k, m - 2, m)
    b_k = pow(b_k, m - 2, m)

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

    n_b = 1
    for i in range(n-b+1, n+1):
        n_b = (n_b * i) % m

    n_C_a = a_k * n_a
    n_C_b = b_k * n_b

    n_C_a = n_C_a % m
    n_C_b = n_C_b % m

    p = pow(2, n, m)

    print((p - n_C_a - n_C_b - 1)%m)
    return 0


if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = (10**9 + 7)
from functools import reduce
from operator import mul

def mulMOD(x,y):
    return x*y%MOD

def nCr(n,r):
    num = reduce(mulMOD, range(n, n - r, -1))
    den = reduce(mulMOD, range(1, r + 1))
    return num * pow(den, MOD - 2, MOD) % MOD

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

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
N=2*10**5+1
mod=10**9+7
inv_l=[0,1]
for i in range(2,N):
    inv_l+=[inv_l[mod%i]*(mod-int(mod/i))%mod]
def nCr(n,r):
    ret=1
    for i in range(r):
        ret=ret*(n-i)%mod*inv_l[i+1]%mod
    return ret
ans=1
double=2
n_=n
while n_:
    if n_%2==1:
        ans=ans*double%mod
    n_//=2
    double=double*double%mod
ans=(ans-nCr(n,a)-nCr(n,b)-1)%mod
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


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


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
# sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = True
show_flg = False


def f(n):
    r = (n - 2)
    m = (4 * (1 - pow(2, r, MOD))) // (1 - 2)
    return (3 + m) % MOD


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


def cmb(n, r):
    p = 1
    c = 1
    for i in range(r):
        p *= (n - i)
        c *= (i + 1)
        p = p % MOD
        c = c % MOD
    return p * modinv(c) % MOD


def main():
    n, a, b = MI()
    first = cmb(n, a)
    second = cmb(n, b)
    ans = f(n)
    print((ans - first - second) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n,a,b = map(int,input().split())
    MOD = 10**9 +7
    s = pow(2,n,MOD)-1
    P_ni = 1
    F_i = 1

    for i in range(1,b + 1):
        P_ni=P_ni*(n-i+1)%MOD
        F_i=F_i* i % MOD
        if i == a or i == b:
            s-=P_ni*pow(F_i,MOD-2,MOD)
    print(s%MOD)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import heapq
import copy
import numpy as np
from collections import deque

md=10**9+7

def modinv(a,m):
    return pow(a,m-2,m)

def modFact(n,k):
    ret=1
    for i in range(k):
        enum=(n-i)%md
        denum=modinv(i+1,md)

        ret=(ret*(enum*denum)%md)%md
    
    return (ret+md)%md
        

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

print((pow(2,n,md)-1-modFact(n,a)-modFact(n,b)+md)%md)

Submission status: Accepted

Solution code:
def main():
    n,a,b = map(int,input().split())
    MOD = 10**9 +7
    s = pow(2,n,MOD)-1
    P_ni = 1
    F_i = 1


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



    print(s%MOD)

if __name__=='__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod=10**9+7
n,a,b=map(int,input().split())
pows=[2]
for _ in range(40):
  pows.append((pows[-1]**2)%mod)
ans=1
flag=format(n,'b')
if len(flag)<31:
  flag=(31-len(flag))*'0'+flag
flag=flag[::-1]
for i in range(31):
  if flag[i]=='1':
    ans*=pows[i]
    ans%=mod
ans-=1
rfacts=[pow(1,mod-2,mod)%mod,pow(1,mod-2,mod)%mod]
for i in range(2,2*(10**5)+1):
  rfacts.append((rfacts[-1]*pow(i,mod-2,mod))%mod)
if n<=2*10**5:
  fact=1
  for i in range(2,n+1):
    fact*=i
    fact%=mod
  ans-=(fact*rfacts[a]*rfacts[n-a])%mod
  ans%=mod
  ans-=(fact*rfacts[b]*rfacts[n-b])%mod
  ans%=mod
else:
  fact1=1
  for i in range(n,n-a,-1):
    fact1*=i
    fact1%=mod
  ans-=(fact1*rfacts[a])%mod
  ans%=mod
  fact2=1
  for i in range(n,n-b,-1):
    fact2*=i
    fact2%=mod
  ans-=(fact2*rfacts[b])%mod
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, a, b = MAP()

def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, int(y/2)) ** 2 % mod
    else:
        return power(x, int((y-1)/2)) ** 2 * x % mod
ans = power(2, n) - 1
    
a_max = 2 * 10 ** 5
# a, bの最大値+2
fact = [1] * (a_max + 2)
# 逆元
for i in range(1, a_max + 1):
    fact[i] = (fact[i-1] * i) % mod
# combination
def C(n, a):
    tmp = 1
    for i in range(n, n-a, -1):
        tmp = (tmp * i) % mod
    return tmp * power(fact[a], mod - 2)

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

Submission status: Accepted

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