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

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

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

    for j in range(n-b+1, n+1):
        p2 *= j
        p2 %= mod
    # print(p2)

    q1, q2 = 1, 1
    g1 = [1, 1]
    g2 = [1, 1]
    inv = [0, 1]
    for i in range(2, max(a, b)+1):
        g1.append((g1[-1] * i) % mod)
        inv.append( ( -inv[mod % i] * (mod//i)) % mod )
        g2.append((g2[-1] * inv[-1]) % mod)
    q1 = g2[a] % mod
    q2 = g2[b] % mod

    memo = dict()
    memo[0] = 1
    def powmod(n, mod):
        if n in memo: return memo[n]
        memo[n//2] = powmod(n//2, mod)
        if n % 2 == 0:
            memo[n] = pow(powmod(n//2, mod), 2) % mod
        else:
            memo[n] = 2 * pow(powmod(n//2, mod), 2) % mod
        return memo[n]

    v = powmod(n, mod)
    v1 = (p1 * q1) % mod
    v2 = (p2 * q2) % mod
    # print(v, v1, v2)

    return (v-v1-v2-1) % mod
if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

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

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

def comb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % mod

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

def comb(N, X):
    bunbo = 1
    for x in range(X):
        bunbo = (bunbo * (N - x)) % MOD
    return (bunbo * g2[X]) % MOD

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

print(answer)

Submission status: Accepted

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

def cmb(n, r):
    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 *= int(numerator[k])
            result %= MOD

    return result
ans -= (cmb(n,a) + cmb(n,b))
print(ans%MOD)

Submission status: Accepted

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

def combination(n, k):
    from math import factorial
    numer = 1
    for i in range(k):
        numer *= (n-i)
        numer %= MOD
    denom = factorial(k) % MOD
    return numer * pow(denom, MOD-2, MOD)

total = pow(2, n, MOD) - 1
comb_a = combination(n, a)
comb_b = combination(n, b)
print((total - comb_a - comb_b) % MOD)

Submission status: Accepted

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

# a//b (MOD p)
def div_mod(a, b, p = MOD):
    return (a * pow(b, p-2, p)) % p

def cmb(n, r, p = MOD):
    tmp = 1
    i = n
    while i > n - r:
        tmp *= i
        tmp %= p
        i -= 1
    for i in range(1, r+1):
        tmp = div_mod(tmp, i, p)
    return tmp

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

Submission status: Accepted

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

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

MOD = 10 ** 9 + 7


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

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

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

    return res


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

# print("hoge")


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


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


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

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

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

# print(mb)
# print(fact_inv)

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

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

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

print(ans)

Submission status: Accepted

Solution code:

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

mod = 10**9+7

MAX = max(a,b)+10
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

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



def cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
    
cominit()
cmb1 = 1
for i in range(a):
    cmb1 *= (N-i)
    cmb1 %= mod
cmb1 *= finv[a]

cmb2 = 1
for i in range(b):
    cmb2 *= (N-i)
    cmb2 %= mod
cmb2 *= finv[b]


ans = pow(2,N,mod) - 1 - cmb1 - cmb2
ans %= mod
print(ans)

Submission status: Accepted

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

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

MOD = 1000000007

ANS1 = modpow(2, n, MOD)

ANS2 = 1
for i in range(a):
    ANS2 = ANS2 * (n-i) * modpow(i+1, MOD-2, MOD) % MOD

ANS3 = 1
for i in range(b):
    ANS3 = ANS3 * (n-i) * modpow(i+1, MOD-2, MOD) % MOD

if (ANS1 - 1 - ANS2 - ANS3) % MOD < 0:
    print((ANS1 - 1 - ANS2 - ANS3) % MOD + MOD)
else:
    print((ANS1 - 1 - ANS2 - ANS3) % MOD)

Submission status: Accepted

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

if n==2:
    print(0)
    exit()

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

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

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

print((f-nca-ncb+mod)%mod)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

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

m=10**9+7
ans=1
t=2**100
for i in range(n//100):
    ans*=t
    ans%=m
ans*=2**(n-(n//100)*100)

m=10**9+7
temp_a=1

for i in range(a):
    temp_a*=(n-i)*mod_inv(i+1,m)
    temp_a%=m
temp_b=1
for i in range(b):
    temp_b*=(n-i)*mod_inv(i+1,m)
    temp_b%=m


print((ans-temp_a-temp_b+m*2)%m-1)

Submission status: Accepted

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

def pow_k(x, n):
    """
    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# 指数を割り続け n が 1 に至ったら終了

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

ans = pow_k(2, n) - 1
ans -= modc(n, a, mod) + modc(n, b, mod)
ans = ans % mod
print(ans)

Submission status: Accepted

Solution code:
def d_bouquet(MOD=10**9 + 7):
    N, A, B = [int(i) for i in input().split()]
    from operator import mul
    from functools import reduce

    def cmb(n, r):
        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 *= int(numerator[k])
                result %= MOD

        return result

    ans = pow(2, N, MOD) - 1
    ans -= cmb(N, A)
    ans -= cmb(N, B)

    return (ans + MOD) % MOD

print(d_bouquet())

Submission status: Accepted

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

mod = 10**9+7


ans = pow(2,n,mod)

ans -= 1
if ans < 0:
	ans += mod
# print("Ans now:", ans)

c1 = 0
cnt = n
num = 1
den = 1
for i in range(1,a+1):
	num = num * cnt;
	cnt -= 1
	den = den * i
	den %= mod
	num %= mod
# print(den,num)

c1 = num * pow(den,mod-2,mod)
c1 %= mod
# print(c1)

c2 = 0
cnt = n
num = 1
den = 1
for i in range(1,b+1):
	num = num * cnt
	cnt -= 1
	den = den * i
	den %= mod
	num %= mod
# print(den,num)
c2 = num * pow(den, mod-2, mod)
c2 %= mod

ans -= c1
if ans < 0 : ans += mod
ans -= c2
if ans < 0 : ans += mod

print(ans)

Submission status: Accepted

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

n = 200000
fact = [1]*(n+1)
inv = [1]*(n+1)
ifact = [1]*(n+1)
for i in range(1,n+1):
    fact[i] = fact[i-1]*i % MOD
    inv[i] = pow(i,MOD-2,MOD)
    ifact[i] = ifact[i-1]*inv[i] % MOD

pa = 1
for i in range(N,N-A,-1):
    pa = (pa * i) % MOD

pb = pa

for i in range(N-A,N-B,-1):
    pb = (pb * i) % MOD

q = 1
for i in range(B,A,-1):
    q  = (q * i) % MOD

bans =( (pow(2,N,MOD) * fact[B]) - q * pa - pb) % MOD

ans = (bans * ifact[B] -1) % MOD
print(ans)

Submission status: Accepted

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

mod = 10**9 + 7

ans = pow(2, n, mod) - 1
for i in [a,b]:
    child = 1
    mother = 1
    for j in range(1,i+1):
        child = child * (n-j + 1) % mod
        mother = mother * j % mod
    mother = pow(mother, mod-2, mod)
    ans -= (child * mother)%mod


ans = ans % mod

print(ans)

Submission status: Accepted

Solution code:
#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"
exit $?
'''
import sys

def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

class Bigint:
    def __init__(self,n,mod=10**9+7):
        self.n = n % mod
        self.mod = mod
        return


    def __str__(self):
        return str(self.n)


    def __add__(self,other):
        ot = type(other)
        if ot==Bigint:
            return Bigint(self.n+other.n,self.mod)
        elif ot==int:
            return Bigint(self.n+other,self.mod)
        else:
            raise ValueError("Invalid type")


    def __iadd__(self,other):
        return self.__add__(other)


    def __sub__(self,other):
        ot = type(other)
        if ot==Bigint:
            o = other.n
        elif ot==int:
            o = other
        else:
            raise ValueError("Invalid type")
        #
        return Bigint(self.n - o, self.mod)


    def __isub__(self,other):
        return self.__sub__(other)


    def __mul__(self,other):
        ot = type(other)
        if ot==Bigint:
            return Bigint(self.n*other.n,self.mod)
        elif ot==int:
            return Bigint(self.n*other,self.mod)
        else:
            raise ValueError("Invalid type")


    def __imul__(self,other):
        return self.__mul__(other)


    def __pow__(self,other):
        assert type(other)==int, "power should be integer"
        #
        if other<0: return self ** ( other % ( self.mod-1 ) )
        ret = Bigint(1,self.mod)
        now = Bigint(self.n,self.mod)
        while other>0:
            if other%2==0: pass
            else: ret *= now
            other//=2
            now*=now
        return ret


    def __truediv__(self,other):
        ot = type(other)
        if ot==Bigint:
            o = other
        elif ot==int:
            o = Bigint(other)
        else:
            raise ValueError("Invalid type")

        self *= ( o ** (o.mod-2) )
        return self


    def __itruediv__(self,other):
        return self.__truediv__(other)

def combination(n,k):
   kp = min(k,n-k)

   ne = Bigint(1)
   for i in range(n-kp+1, n+1): ne *= i
   de = Bigint(1)
   for i in range(1, kp+1): de *= i
   return ne / de

n, a, b = _ia()
ans = Bigint(2) ** n - 1
ans -= combination(n,a)
ans -= combination(n,b)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

# 互いに素なa,bについて、a*x+b*y=1の一つの解[x,y]を出力
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

# aの逆元(mod M)を求める（aとMは互いに素）
def mod_inv(a,M=mod):
    x = extgcd(a,M)[0]
    return (M+x%M)%M

def nCk2(n,k):
    x = [0]*(k+1)
    x[0] = 1
    for i in range(1,k+1):
        x[i] = x[i-1]*(n-k+i)*mod_inv(i) % mod
    return x[-1]

n,a,b = LI()

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

print(ans)

Submission status: Accepted

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

def inv(x):
    return(pow(x,mod-2,mod))
x=1
k=1
while x<max(a,b)+1:
    k=(k*(n-x+1))*inv(x)
    k=k%mod
    if x==a or x==b:
        ans-=k
    x+=1
print(ans%mod)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def main():
    mod = 10 ** 9 + 7

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

    ma = max(a, b)
    tbl = [0] * (ma + 1)

    # f = 1
    # for i in range(1, ma + 1):
    #     f = (f * i) % mod
    #
    # invs = [1] * (ma + 1)
    # invs[ma] = pow(f, mod - 2, mod)
    # for x in range(ma - 1, 0, -1):
    #     invs[x] = invs[x + 1] * (x + 1) % mod

    t = 1
    for i in range(1, max(a, b) + 1):
        t = (t * (n - i + 1) * pow(i, mod - 2, mod)) % mod
        tbl[i] = t

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 1000000007

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

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

def cmb(a,b):
    r=min(b,a-b)
    if(r==0):
        return 1
    ue=1
    sita=1
    for i in range(r):
        ue*=a-i
        ue%=mod
        sita*=r-i
        sita%=mod
    return div(ue,sita)

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


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

zen=power(2,n)-1

dame=cmb(n,a)
kirai=cmb(n,b)

ans=(mod*2+zen-dame-kirai) % mod
print(ans)

Submission status: Accepted

Solution code:
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
A = [1 for _ in range(200001)]
for i in range(2,200001):
    A[i] = (i*A[i-1])%p
B = [1 for _ in range(200001)]
B[200000] = pow(A[200000],p-2)
for i in range(199999,1,-1):
    B[i] = (B[i+1]*(i+1))%p
    
n,a,b = map(int,input().split())
a1 = 1
for i in range(n,n-a,-1):
    a1 = (a1*i)%p
a1 = (a1*B[a])%p
b1 = 1
for i in range(n,n-b,-1):
    b1 = (b1*i)%p
b1 = (b1*B[b])%p
ans = (pow(2,n)-1-a1-b1)%p
print(ans)

Submission status: Accepted

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

def cmb(n, r):
    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 *= int(numerator[k])
            result %= mod

    return result % mod



ans = pow(2, n, mod) - cmb(n, a) - cmb(n, b) - 1
#Sprint("{}, {}, {}".format(pow(2, n, mod), cmb(n, a), cmb(n, b)))
print(ans % mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3


P = 10 ** 9 + 7


def binom(n, k, p=P):
    denominator = 1
    for i in range(2, k + 1):
        denominator *= i
        denominator %= p
    numerator = 1
    for i in range(n, n - k, -1):
        numerator *= i
        numerator %= p
    inv_denominator = pow(denominator, p - 2, p)
    res = numerator * inv_denominator % p
    return res


def compute(n, a, b, p=P):
    num_all = pow(2, n, p)
    num_a = binom(n, a, p)
    num_b = binom(n, b, p)
    res = (num_all - 1 - num_a - num_b) % p
    return res


def main():
    n, a, b = (int(z) for z in input().split())
    res = compute(n, a, b)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

P = 10**9+7

nCa = 1

for i in range(1,a+1):
    nCa = nCa*(n+1-i)*modinv(i,P)%P
nCb = nCa
for j in range(a+1,b+1):
    nCb = nCb*(n+1-j)*modinv(j,P)%P

ans = (pow(2,n,P) -1 - nCa - nCb + 2*P)%P
print(ans)

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, N: int, MOD: int):
        fac = [0 for _ in range(N + 1)]
        fac[0] = 1
        for i in range(1, N + 1):
            fac[i] = fac[i - 1] * i % MOD
        self.fac = fac
        self.N = N
        self.MOD = MOD

    def _modpow(self, x: int, n: int) -> int:
        ret = 1
        while n > 0:
            if n % 2 == 1:
                ret = ret * x % self.MOD
            x = x * x % self.MOD
            n >>= 1
        return ret

    def _modinv(self, x: int) -> int:
        return self._modpow(x, self.MOD - 2)

    def combination(self, n: int, k: int) -> int:
        if n < k:
            return 0
        return self.fac[n] * self._modinv(self.fac[k]) % self.MOD * self._modinv(self.fac[n - k]) % self.MOD

N, A, B = map(int, input().split())
MOD = int(1e9) + 7
S = 2 ** N % MOD

comb = Combination(3 * int(1e5), MOD)


def f(X):
    x = 1
    for i in range(1, X + 1):
        x *= comb._modinv(i)
        x *= (N - i + 1)
        x %= MOD

    return x

S += 3 * MOD - f(A) - f(B) - 1
S %= MOD
print(S)

Submission status: Accepted

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

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

c_a = 1

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

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

c_b = 1

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

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

ans = (total - c_a - c_b) % mod
print(ans)

Submission status: Accepted

Solution code:
F = 2*10**5+2
mod = 10**9+7
fact = [1]*F
inv = [1]*F
for i in range(2,F):
    fact[i]=(fact[i-1]*i)%mod
inv[F-1]=pow(fact[F-1],mod-2,mod)
for i in range(F-2,1,-1):
    inv[i] = (inv[i+1]*(i+1))%mod

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

c1=1
for i in range(n,n-a,-1):
    c1=(c1*i)%mod
c2=1
for i in range(n,n-b,-1):
    c2=(c2*i)%mod
c1=(c1*inv[a])%mod
c2=(c2*inv[b])%mod

ans=pow(2,n,mod)
ans=(ans-1-c1-c2)%mod

print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7
n, a, b = map(int,input().split())
N = max(a,b)
fact = [None for i in range(N+1)]
fact[0] = 1
for i in range(1, N+1):
    fact[i] = (fact[i-1]*i) % mod
finv = [None for i in range(N+1)]
def inv(x):
    ret = 1
    k = mod - 2
    y = x
    while k:
        if (k & 1):
            ret = (ret * y) % mod
        y = (y * y) % mod
        k //= 2
    return ret
finv[N] = inv(fact[N])
for i in range(N, 0, -1):
    finv[i-1] = (finv[i]*i) % mod
def binpow(x, n, mod=None):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n >>= 1
    return ret
def comb(n,k):
    tmp = 1
    for i in range(k):
        tmp = (tmp*(n-i)) % mod
    return (tmp * finv[k]) % mod
print((binpow(2,n,mod=mod)-1-comb(n,a)-comb(n,b))%mod)

Submission status: Accepted

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

def inv(x):
    return pow(x,P-2,P)

A=max(a,b)
B=min(a,b)

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

bunsi = 1
bunbo = 1

for i in range(A):
    bunsi = bunsi * (n-i) % P
    bunbo = bunbo * (1+i) % P
    if 1+i==B:
        ans = ans - bunsi * inv(bunbo)
        #print([B, bunsi * inv(bunbo)])
    #print([i+1,bunsi,bunbo])
ans = ans - bunsi * inv(bunbo)
#print([A, bunsi * inv(bunbo)])
    
print( ans % P )

Submission status: Accepted

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

def frac_with_mod(a,m):
    outlist = [ 1 for i in range(a+1) ]
    for i in range(1,a+1):
        outlist[i] = (outlist[i-1] * i)% m
    return outlist

frac_list = frac_with_mod(2*10**5+1,10**9+7)

total = (pow(2, n, mod) - 1)
ina = pow(frac_list[a],mod-2,mod)
for i in range(n, n-a, -1):
    ina *= i
    ina %= mod
inb = pow(frac_list[b],mod-2,mod)
for i in range(n, n-b, -1):
    inb *= i
    inb %= mod
print((total - ina - inb)%mod)

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7

n, a, b = map(int, sys.stdin.readline().split())
k = min(n, 2 * 10 ** 5)

def make_inv(size=10**6, p=MOD):
    fac = [None] * (size + 1)
    fac[0] = 1
    for i in range(size):
        fac[i+1] = fac[i] * (i + 1) % p
    ifac = [None] * (size + 1)
    ifac[size] = pow(fac[size], p-2, p)
    for i in range(size, 0, -1):
        ifac[i-1] = ifac[i] * i % p
    inv = [None] * (size + 1)
    for i in range(1, size+1):
        inv[i] = fac[i-1] * ifac[i] % MOD
    return inv

inv = make_inv(k)

def make_table(n, k, p=MOD):
    table = [None] * (k + 1)
    table[0] = 1
    for i in range(k):
        table[i+1] = table[i] * (n - i) % MOD * inv[i+1] % MOD
    return table

comb_n = make_table(n, k)

def main():
    res = pow(2, n, MOD) - comb_n[a] - comb_n[b] - 1
    return res % MOD

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
def extgcd(a,b):
  r=[1,0,a]
  w=[0,1,b]
  while w[2]!=1:
    q=r[2]//w[2]
    r2=w
    w2=[r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
    r=r2
    w=w2
  return [w[0],w[1]]
def mod_inv(a,m):
  x=extgcd(a,m)[0]
  return (m+x%m)%m

n,a,b=map(int,input().split())
mod=10**9+7
x=1;y=1
for i in range(a):
  x*=(n-i)
  x%=mod
for i in range(a):
  x*=mod_inv(i+1,mod)
  x%=mod
for i in range(b):
  y*=(n-i)
  y%=mod
for i in range(b):
  y*=mod_inv(i+1,mod)
  y%=mod
z=pow(2,n,mod)
print((z-1-x-y+mod)%mod)

Submission status: Accepted

Solution code:
def cb(n, k):
    ret = a = b = 1
    mod = 10**9 + 7
    for i in range(k):
        a *= n-i
        a %= mod
        b *= i + 1
        b %= mod
    m = mod-2
    while m > 0:
        if m % 2 != 0:
            ret *= b
            ret %= mod
        b *= b
        b %= mod
        m //= 2
    ret *= a
    ret %= mod
    return ret

def two_pow(n):
    ret = 1
    two = 2
    mod = 10 ** 9 + 7
    while n:
        if n & 1:
            n -= 1
            ret *= two
            ret %= mod
        two *= two
        two %= mod
        n //= 2
    return ret
N, a, b = map(int, input().split())
mod = 10 ** 9 + 7
print((two_pow(N) - 1 - cb(N, a) - cb(N, b)) % mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

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

    def pow(self, a, b):
        return pow(a, b, self.m)


M = Mod(10**9+7)
def C(n, r):
    ans = 1
    for i in range(r):
        ans = M.mul(ans, n - i)
        ans = M.div(ans, i+1)
    return ans

@mt
def slv(N, A, B):

    # C = Combination(N, 10**9+7)
    ans = M.pow(2, N)
    ans = M.sub(ans, 1)
    ans = M.sub(ans, C(N, A))
    ans = M.sub(ans, C(N, B))
    return ans


def main():
    N, A, B = read_int_n()
    print(slv(N, A, B))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def modinv2(x,r):
  return pow(x,r-2,r)

def comb(n,a):
    dend = n
    for i in range(1,a):
        dend = (dend*(n-i))%R
    sor = 1
    for i in range(2,a+1):
        sor = (sor*i)%R
    return (dend*modinv2(sor,R))%R

n,a,b = inm()
print((pow(2,n,R)-comb(n,a)-comb(n,b)-1)%R)

Submission status: Accepted

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

n, a, b = MAP()

if n == 2:
	print(0)
	exit()

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

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

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 s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

MOD = 1000000007

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return a*b%MOD

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = (1,0,a)
    w = (0,1,b)
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return (w[0],w[1])

def mod_inv(a):
    x,_ = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

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

n, a, b = l_in()

res = mod_pow(2, n)
nCa = 1
for i in range(n, n-a, -1):
    nCa = mod_mul(nCa, i)
for i in range(1, a+1):
    nCa = mod_div(nCa, i)

nCb = 1
for i in range(n, n-b, -1):
    nCb = mod_mul(nCb, i)
for i in range(1, b+1):
    nCb = mod_div(nCb, i)

# print(res, nCa, nCb)

res = mod_sub(res, 1)
res = mod_sub(res, nCa)
res = mod_sub(res, nCb)
print(res)