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:
M,A,B = [int(x) for x in input().split()]

mod = 10**9+7

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

def binary(n):
    return bin(n)[2:]


def pow_by_binary_exponentiation(a, x, n): # a^x mod n
    x = [int(b) for b in binary(x)]
    y = a
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * a) % n
    return y
d = pow_by_binary_exponentiation(2,M,mod)-1
    
d1 = cmb(M,A,mod)
d2 = cmb(M,B,mod)
print((d-d1-d2)%mod)

Submission status: Accepted

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


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


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

while ans < 0:
    ans += mod
print(ans)

Submission status: Accepted

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

MOD = 1000000007

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

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

ans -= x * pow(y, MOD - 2, MOD) % MOD

while ans < 0:
    ans += MOD
print(ans)

Submission status: Accepted

Solution code:
n, a, b = [int(i) for i in input().split()]
mod = 10**9 + 7
 
total = pow(2, n, mod) - 1
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
 
at = combination(n,a)
bt = combination(n,b)
 
result = total - at - bt
result %= mod
if result < 0:
  result += mod
print(result)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
n, a, b = [int(i) for i in input().split()]
mod = 10**9 + 7
 
total = pow(2, n, mod) - 1
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
 
at = combination(n,a)
bt = combination(n,b)
 
result = total - at - bt
result %= mod
if result < 0:
  result += mod
print(result)

Submission status: Accepted

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

i = 2
f = 1
fn = N
while i <= A:
    f = (f * i) % mod
    fn = (fn * (N + 1 - i)) % mod
    i += 1
fa, fna = f, fn
while i <= B:
    f = (f * i) % mod
    fn = (fn * (N + 1 - i)) % mod
    i += 1
fb, fnb = f, fn


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


nca = (fna * pow(fa, mod - 2)) % mod
ncb = (fnb * pow(fb, mod - 2)) % mod
print((pow(2, N) - 1 - nca - ncb) % mod)

Submission status: Accepted

Solution code:
k = 72
kk = k // 4
K = 1<<k
nu = lambda L: int("".join([hex(K+a)[3:] for a in L[::-1]]), 16)
st = lambda n: hex(n)[2:]
li = lambda s, l, r: [int(a, 16) % P if len(a) else 0 for a in [s[-(i+1)*kk:-i*kk] for i in range(l, r)]]

def grow(d, v, h):
    h += [0] * d
    f = [(-1 if (i+d) % 2 else 1) * fainv[i] * fainv[d-i] % P * h[i] % P for i in range(d+1)]
    nuf = nu(f)
    a = d * inv[v] % P
    t = [1] * (3*d+3)
    for i in range(1, 3*d+3): t[i] = t[i-1] * (a - d + i - 1) % P
    ti = [1] * (3*d+3)
    ti[-1] = pow(t[-1], P-2, P)
    for i in range(1, 3*d+3)[::-1]: ti[i-1] = ti[i] * (a - d + i - 1) % P
    iv = [1] * (3*d+3)
    for i in range(1, 3*d+3):
        iv[i] = ti[i] * t[i-1] % P

    ###
    g = [inv[i] for i in range(1, 2*d+2)]
    fg = li(st(nuf * nu(g)), d, d * 2 + 1)
    for i in range(d):
        h[i+d+1] = fg[i] * fa[d+i+1] % P * fainv[i] % P

    ###
    g = [iv[i] for i in range(1, 2*d+2)]
    fg = li(st(nuf * nu(g)), d, d * 2 + 1)
    for i in range(d+1):
        h[i] = h[i] * (fg[i] * t[d+i+1] % P * ti[i] % P) % P

    ###
    g = [iv[i] for i in range(d+2, 3*d+3)]
    fg = li(st(nuf * nu(g)), d, d * 2 + 1)
    for i in range(d):
        h[i+d+1] = h[i+d+1] * (fg[i] * t[2*d+i+2] % P * ti[d+i+1] % P) % P

    return h

# Create a table of the factorial of the first v+2 multiples of v, i.e., [0!, v!, 2v!, ..., (v(v+1))!]
def create_table(v):
    s = 1
    X = [1, v+1]
    while s < v:
        X = grow(s, v, X)
        s *= 2

    table = [1]
    for x in X:
        table.append(table[-1] * x % P)
    return table

def fact(i, table):
    a = table[i//v]
    for j in range(i//v*v+1, i+1):
        a = a * j % P
    return a

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

v = 1 << (N.bit_length() + 1) // 2
fa = [1] * (2*v+2)
fainv = [1] * (2*v+2)
for i in range(2*v+1):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(2*v+1)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P
inv = [0] * (2*v+2)
for i in range(1, 2*v+2):
    inv[i] = fainv[i] * fa[i-1] % P

T = create_table(v)
C = lambda n, k: fact(n, T) * pow(fact(k, T) * fact(n-k, T), P-2, P) % P
 
print((pow(2, N, P) - 1 - C(N, A) - C(N, B)) % P)

Submission status: Accepted

Solution code:
def pow(x, n, mod):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = ans*x % mod
    x = x*x % mod
    n = n >> 1
  return ans

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

def main():
    n, a, b = map(int, input().split())
    mod = 10**9 +7
    allsum = pow(2, n, mod)-1
    abunbo = kaijou_k(n, n-a+1, mod)
    abunsi = kaijou_k(a, 1, mod)
    asum = abunbo * pow(abunsi, mod-2, mod) % mod
    bbunbo = kaijou_k(n, n-b+1, mod)
    bbunsi = kaijou_k(b, 1, mod)
    bsum = bbunbo * pow(bbunsi, mod-2, mod) % mod
    ans = (allsum - asum - bsum) % mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def solve():
  n,a,b = (int(i) for i in input().split())
  mod = 10**9+7
  all = pow(2,n,mod)-1
  
  comba = 1
  inva = 1
  for i in range(1,a+1):
    comba *= (n-i+1)
    comba %= mod
    
    inva *= i
    inva %= mod

  ta = pow(inva,10**9+5,mod)
  comba = (comba * ta)%mod
  
  combb = 1
  invb = 1
  for i in range(1,b+1):
    combb *= (n-i+1)
    combb %= mod
    
    invb *= i
    invb %= mod
  tb = pow(invb,10**9+5,mod)
  combb = (combb * tb)%mod
  
  print((all-comba-combb)%mod)
  
solve()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
M = pow(10, 9) + 7

def pow_mod(a, n, m): # (a^n) % m
    res = 1
    while n > 0:
        if n % 2 == 1:
            res = (res * a) % m
        a = (a * a) % m
        n = n // 2
    return res

def combi_mod(p, q, m):
    numerator, denominator = 1, 1
    for i in range(1, q+1):
        numerator *= (p - i + 1)
        numerator %= m
        denominator *= i
        denominator %= m
    return numerator * pow_mod(denominator, m-2, m) % m

n, a, b = list(map(int, input().split()))
res = pow_mod(2, n, M) - 1
res -=combi_mod(n, a, M)
if res < 0:
    res += M
res -= combi_mod(n, b, M)
if res < 0:
    res += M
print(res)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

def rep_pow(x, n):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = (ans*x) % MOD
    x = (x*x) % MOD
    n = n >> 1 #ビットシフト
  return ans

ans = rep_pow(2, n) - 1

#print(ans)

def comb(c, n):
    x = 1
    y = 1
    for i in range(c):
        x = (x * (n - i)) % MOD
        y = (y * (i + 1)) % MOD
    return (x * rep_pow(y, MOD - 2)) % MOD

ans = ans + MOD * 2 - comb(a, n) - comb(b, n)

print(ans % MOD)

Submission status: Accepted

Solution code:
class Mint:
    
    MOD = 10**9+7
    
    def __init__(self, x=0):
        self.x = (x%self.MOD + self.MOD) % self.MOD
    
    def __iadd__(self, other):
        self.x += other.x
        if self.x >= self.MOD:
            self.x -= self.MOD
        return self
    
    def __isub__(self, other):
        self.x += self.MOD - other.x
        if (self.x >= self.MOD):
            self.x -= self.MOD
        return self
    
    def __imul__(self, other):
        self.x *= other.x
        self.x %= self.MOD;
        return self;
    
    def __add__(self, other):
        ans = Mint(self.x)
        ans += other
        return ans
        
    def __sub__(self, other):
        ans = Mint(self.x)
        ans -= other
        return ans
    
    def __mul__(self, other):
        ans = Mint(self.x)
        ans *= other
        return ans
    
    def __pow__(self, n):
        if n == 0:
            return Mint(1)
        a = self.__pow__(n >> 1)
        a *= a
        if n&1:
            a *= self
        return a
    
    def inv(self):
        return self**(self.MOD-2)
    
    def __ifloordiv__(self, other):
        self *= other.inv()
        return self
    
    def __floordiv__(self, other):
        ans = Mint(self.x)
        ans //= other
        return ans
        
class Comb:
    
    def __init__(self):
        pass
    
    def comb(self, n, k):
        assert n < Mint.MOD
        if k < 0 or k > n:
            return 0
        numerator = Mint(n-k+1)
        for i in range(n-k+2, n+1):
            numerator *= Mint(i)
        d = Mint(1)
        for i in range(2, k+1):
            d *= Mint(i)
        denominator = d.inv()
        return numerator*denominator            
        

def Main(N, A, B):
    ans = Mint(2)**N-Mint(1)-Comb().comb(N, A)-Comb().comb(N, B)
    return ans.x

def main():
    N, A, B = list(map(int, input().split()))
    print(Main(N, A, B))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

print(ans % mod)

Submission status: Accepted

Solution code:
def cmb(n, r, mod):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n%mod

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

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

def solve(mod):
    n, a, b = [int(_) for _ in input().split()]
    nb = cmb(n, b, mod)
    na = cmb(n, a, mod)
    return RepeatingSquare(2, n, mod) - 1 - na - nb

if __name__ == '__main__':
    MOD = 10 ** 9 + 7
    print(solve(MOD)%MOD)

Submission status: Accepted

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

MOD = 10**9+7

def combination_formula(n, r):
    _max, _min = max(n-r, r), min(n-r, r)
    bunsi, bunbo = 1, 1
    for i in range(_min):
        bunsi *= (n-i)
        bunbo *= (i+1)
        bunsi %= MOD
        bunbo %= MOD
    # フェルマーの小定理を使って、modの世界のbunsi/bunboを計算する
    # 1/bunbo ≡ bunbo^{p-2} より、
    bunbo = pow(bunbo, MOD-2, MOD)
    ans = (bunsi*bunbo) % MOD
    return ans

def solve():
    n, a, b = list(map(int, input().split()))
    ans = pow(2, n, MOD)
    ans -= 1  # nC0を除外
    ans -= combination_formula(n, a)
    ans -= combination_formula(n, b)
    while ans < 0:
        ans += MOD
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

Submission status: Accepted

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

MOD = 1000000007

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

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

Submission status: Accepted

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

print((c - comb(N,a) - comb(N,b)) % MOD)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

def modcomb(n,a,mod):
    cnt = 1
    for i in range(a):
        cnt *= (n-i)
        cnt *= pow(i+1,mod-2,mod)
        cnt %= mod
    # print(cnt)
    return cnt
    


X = pow(2,n,MOD)-1
A = modcomb(n,a,MOD)
B = modcomb(n,b,MOD)
ans = (X-A-B)%MOD
print(ans)

Submission status: Accepted

Solution code:
# return x^{-1} % mod
# it takes O(log{mod})
def mod_inverse(x, mod):
    return pow(x, mod-2, mod)

# return nCk % mod
# it takes O(k)
def mod_comb(n, k, mod):
    numer, denom = 1, 1
    for i in range(k):
        # numer: 分子, denom: 分母
        numer = numer * ((n-i) % mod) % mod
        denom = denom * ((i+1) % mod) % mod

    return numer * mod_inverse(denom, mod) % mod


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

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
mod = pow(10,9)+7
ans = pow(2,n,mod) - 1
anu = 1
ade = 1
bnu = 1
bde = 1
for i in range(max(a,b)):
  if i < a:
    anu = (anu*(n-i))%mod
    ade = (ade*(a-i))%mod
  if i < b:
    bnu = (bnu*(n-i))%mod
    bde = (bde*(b-i))%mod
ade = pow(ade,mod-2,mod)
bde = pow(bde,mod-2,mod)
ans -= (anu*ade)%mod
ans -= (bnu*bde)%mod
print(ans%mod)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# n^p(mod m) -- START --
def powMod(n,p,m):
  if p==0:
    return 1
  if p%2==0:
    t=powMod(n,p//2,m)
    return t*t%m
  return n*powMod(n,p-1,m)%m
# n^p(mod m) --- END ---

def main():
  n,a,b=LI()

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

  pattern_a1=1
  for i in range(a):
    pattern_a1*=n-i
    pattern_a1%=mod
  pattern_a2=1
  for i in range(1,a+1):
    pattern_a2*=i
    pattern_a2%=mod
  pattern_a=pattern_a1*pow(pattern_a2,mod-2,mod)

  pattern_b1=1
  for i in range(b):
    pattern_b1*=n-i
    pattern_b1%=mod
  pattern_b2=1
  for i in range(1,b+1):
    pattern_b2*=i
    pattern_b2%=mod
  pattern_b=pattern_b1*pow(pattern_b2,mod-2,mod)

  ans-=pattern_a
  ans%=mod
  if ans<0:
    ans+=mod
  ans-=pattern_b
  ans%=mod
  if ans<0:
    ans+=mod

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
n,a,b = (int(x) for x in input().split())
mod = pow(10,9) + 7
ans = pow(2,n,mod) - 1
X = 1
Y = 1
W = 1
Z = 1

if a < b:
    c = a
    a = b
    b = c

for i in range(a):
    if i < a:
        X *= (n-i)
        X %= mod
        Y *= (a-i)
        Y %= mod

    if i < b:
        W *= (n-i)
        W %= mod
        Z *= (b-i)
        Z %= mod
    
Y = pow(Y,mod-2,mod)
ans -= ((X*Y) % mod)
    
Z = pow(Z,mod-2,mod)
ans -= ((W*Z) % mod)
print(ans%mod)

Submission status: Accepted

Solution code:
# modなしの場合は，mod=1にする

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def nhr(self, n, r):  # 重複組合せ
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

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

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

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

Submission status: Accepted

Solution code:
import sys
#sys.setrecursionlimit(100000)

MOD = 1000000007  # type: int

def cmb(n, r):
    shi=bo=1
    for i in range(r):
        shi*=(n-i)
        shi%=MOD
        bo*=(r-i)
        bo%=MOD
    return shi*pow(bo,MOD-2,MOD)

def solve(n: int, a: int, b: int):
    print((pow(2,n)-cmb(n,a)-cmb(n,b)-1)%MOD)
    return

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = int(next(tokens))  # type: int
    b = int(next(tokens))  # type: int
    solve(n, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

p = 10 ** 9 + 7

# x^nを求める
def exp_by_sq(x, n):
    if n == 0:
        exp = 1
    elif n == 1:
        exp = x % p
    elif  n % 2 == 0:
        exp = exp_by_sq(x * x % p, n // 2)
    else:
        exp = x * exp_by_sq(x * x % p, (n - 1) // 2) % p
    return exp % p

def binomial_p(n, k, p):
    '''
    Input: integers n, k such that n >= k >= 0, prime number p
    Output: n choose k mod p
    '''
    k = min(k, n-k)

    if k == 0:
        retval = 1
    elif k == 1:
        retval = n
    else:
        numer = n  # n * (n - 1) * ... * (n - k + 1)
        inv = [0, 1]    # inv[i] : inverse of i mod p
        inv_denom = 1 # factorial of inverse of k mod p = 1^(-1) * 2^(-1) * ... * k^(-1) mod p
        for i in range(2, k + 1):
            numer = numer * (n - i + 1) % p
            inv.append(( inv[p % i] * (p - p//i) ) % p ) # inverse of i
            inv_denom = inv_denom * inv[-1] % p
        retval = numer * inv_denom % p

    return retval

ans = (exp_by_sq(2, n) - 1 - binomial_p(n, a, p) - binomial_p(n, b, p)) % p

print(ans)

Submission status: Accepted

Solution code:
def mod_comb(n,k,mod):
    result = 1
    for i in range(n-k+1,n+1):
        result *= i
        result %= mod
    for i in range(1,k+1):
        result *= pow(i,mod-2,mod)
        result %= mod
    return result


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
from operator import mul
from functools import reduce
# a, b = [int(v) for v in input().split()]


def main():

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

    def combi(n, r):
        if r < 0 or r > n:
            return 0
        r = min(n - r, r)

        over = 1
        under = 1

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

        for i in range(1, r + 1):
            under = under * i % mod

        return over * modpow(under, mod-2) % mod

    def modpow(n, r):
        if r == 0:
            return 1

        v = modpow(n, r // 2)
        v = v * v % mod
        if r % 2 != 0:
            v = v * n % mod
        return v

    ans = modpow(2, n) - 1
    ans -= combi(n, a)
    ans -= combi(n, b)

    while ans < 0:
        ans += mod

    print(ans)


main()

Submission status: Accepted

Solution code:
# return x^{-1} % mod
# it take O(log{mod})
def mod_inverse(x, mod):
    return pow(x, mod-2, mod)

# return nCk % mod
# it take O(k)
def mod_comb(n, k, mod):
    numer, denom = 1, 1
    for i in range(k):
        # numer: 分子, denom: 分母
        numer = numer * ((n-i) % mod) % mod
        denom = denom * ((i+1) % mod) % mod

    return numer * mod_inverse(denom, mod) % mod


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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
"""pythonで整数処理"""

def divisors(n):
    """約数の配列を返す"""
    yakusu = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            yakusu.append(i)
            if i * i != n:
                yakusu.append(n // i)
    return yakusu

class ModInt:
    """mod計算を勝手にやってくれるクラス"""
    def __init__(self, x, mod=1000000007):
        self.x = x % mod
        self.mod = mod

    def __repr__(self):
        return str(self.x)

    def __add__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__(self.x + (other.x % self.mod))
        else:
            return self.__class__(self.x + (other % self.mod))

    def __sub__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__(self.x - (other.x % self.mod) if \
                (self.x - (other.x % self.mod)) > 0 else (self.x - (other.x % self.mod)) + self.mod)
        else:
            return self.__class__(self.x - (other % self.mod) if \
                (self.x - (other % self.mod)) > 0 else (self.x - (other % self.mod)) + self.mod)

    def __mul__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__(self.x * (other.x % self.mod))
        else:
            return self.__class__(self.x * (other % self.mod))

    def __truediv__(self, other):
        return self.__class__(self.x * other.inv().x)

    def __pow__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__(pow(self.x, other.x, self.mod))
        else:
            return self.__class__(pow(self.x, other, self.mod))

    def inv(self):
        return self.__class__(pow(self.x, self.mod - 2, self.mod))

def modcomb(n, r, mod=1000000007):
    """
    nCrを返す。
    ModIntが必要。
    1 <= r <= n <= modが必要。
    """
    x = ModInt(1, mod)
    y = ModInt(1, mod)
    for i in range(r):
        x = x * (n - i)
        y = y * (i + 1)
    return x / y
        
n,a,b = map(int,input().split())
print(ModInt(2)**n-modcomb(n,a)-modcomb(n,b)-1)

Submission status: Accepted

Solution code:
def nck(n, k, mod):
    result = 1
    for i in range(n - k + 1, n + 1):
        result = result * i % mod
    tmp = 1
    for i in range(1, k + 1):
        tmp = tmp * i % mod
    return result * pow(tmp, mod - 2, mod) % mod


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

mod = 10**9+7

all = pow(2,n,mod)-1
exc = (combination(n,a)+combination(n,b))%mod
ret = (all - exc)%mod

print(ret)

Submission status: Accepted

Solution code:
# coding: utf-8
n,a_,b_=map(int,input().split())
l=[min(a_,n-a_),min(b_,n-b_)]
a,b=min(l),max(l)
mod=10**9+7
def pow_k(x,n):#いらない
    k=1
    #kは漏れたやつ
    while n>1:
        if n%2==1:
            k*=x
            n-=1
            k=k%mod
        x**=2
        x=x%mod
        n//=2
    
    return (k * x) % mod
    
#ans=pow_k(2,1000000000)
def modcomb(n,r,mod):
    X, Y =  1, 1
    r = min(r, n-r)
    for i in range(1,r+1):
        X = X * (n-i+1) % mod
        Y = Y * i % mod
    
    return X * pow(Y,mod-2,mod) % mod
ans=pow(2,n,mod)-1-modcomb(n,a,mod)-modcomb(n,b,mod)
print(ans%mod)

Submission status: Accepted

Solution code:
# coding: utf-8
n,a_,b_=map(int,input().split())
l=[min(a_,n-a_),min(b_,n-b_)]
a,b=min(l),max(l)
mod=10**9+7
def pow_k(x,n):
    k=1
    #kは漏れたやつ
    while n>1:
        if n%2==1:
            k*=x
            n-=1
            k=k%mod
        x**=2
        x=x%mod
        n//=2
    
    return (k * x) % mod
    
#ans=pow_k(2,1000000000)
def modcomb(n,r,mod):
    X, Y =  1, 1
    r = min(r, n-r)
    for i in range(1,r+1):
        X = X * (n-i+1) % mod
        Y = Y * i % mod
    
    return (X * pow_k(Y, mod-2) % mod) % mod
ans=pow_k(2,n)-1-modcomb(n,a,mod)-modcomb(n,b,mod)
print(ans%mod)

Submission status: Accepted

Solution code:
from functools import reduce
def modcomb(n, k, mod):
    #num = reduce(lambda x, y: x * y % mod, range(n, n - k, -1))
    #den = reduce(lambda x, y: x * y % mod, range(1, k + 1))
    #return num * pow(den, mod - 2, mod) % mod
    num = reduce(lambda x, y: x * y % mod, range(n, n - k, -1))
    den = reduce(lambda x, y: x * y % mod, range(1, k + 1))
    return num * pow(den, mod - 2, mod) % mod
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
x = pow(2, n, mod)
y = modcomb(n, a, mod)
z = modcomb(n, b, mod)
ans = x - y - z - 1
print(ans % mod)

Submission status: Accepted

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

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

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

print((all_case - cmb_mod(n, a, mod) - cmb_mod(n, b, mod)) % mod)

Submission status: Accepted

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

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

ans = pow(2, n, mod)    # 全体
ans -= 1    # 花を選ばない場合をひく

# nCa を求める
nCa = choose(n, a)
nCb = choose(n, b)
ans -= (nCa + mod) % mod
ans -= (nCb + mod) % mod
ans = (ans + mod) % mod
print(ans)

Submission status: Accepted

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

# 逆元配列の作成
inv = [1] * (2 * (10 ** 5)+1)
for i in range(2, 2 * (10 ** 5)+1):
    inv[i] = -inv[mod % i] * (mod // i)
    inv[i] %= mod


def comb(n, a):
    res = 1
    for i in range(a):
        res *= n - i  # 分子
        res *= inv[i + 1]  # 分母
        res %= mod  # modで割ったあまり
    return res


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

ans %= mod
if ans < 0:
    ans += mod

print(ans)

Submission status: Accepted

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

p = 10 ** 9 + 7
inv = [0] * (b + 1)
inv[1] = 1

for k in range(2, b + 1):
	inv[k] = pow(k, p - 2, p)

com = 1
for i in range(1, a + 1):
	com = (com * (n + 1 - i)) % p * inv[i]

coma = com

for j in range(a + 1, b + 1):
	com = (com * (n + 1 - j)) % p * inv[j]

comb = com

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

Submission status: Accepted

Solution code:
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


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


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


def inv(a, mod):
    return pow(a, mod - 2, mod)


def P(a, b, mod):
    res = 1
    for i in range(a, b + 1):
        res *= i
        res %= mod
    return res


def C(a, b, mod):
    return P(a - b + 1, a, mod) * inv(P(1, b, mod), mod) % mod


def main():
    N, A, B = read_values()
    mod = 10 ** 9 + 7 
    res = pow(2, N, mod) - 1

    p1 = P(N - A + 1, N, mod)
    p2 = p1 * P(N - B + 1, N - A, mod) % mod
    p3 = P(1, A, mod)
    p4 = p3 * P(A + 1, B, mod) % mod
    res -= p1 * inv(p3, mod) % mod
    res -= p2 * inv(p4, mod) % mod
    print(res % mod)


if __name__ == "__main__":
    main()