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:
from functools import reduce
n, a, b = map(int, input().split())
mod = 10**9 + 7

def f(A):
    bunsi = reduce(lambda x, y: x*y%mod, range(n, n-A, -1))
    bunbo = reduce(lambda x, y: x*y%mod, range(1, A+1))
    return bunsi * pow(bunbo, mod-2, mod) % mod

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

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 156
# D - Bouquet
# https://atcoder.jp/contests/abc156/tasks/abc156_d
n, a, b = map(int, input().split())
mod = 10**9 + 7

MAX = 202020

cmb = [0]*MAX
facinv = [0]*MAX
inv = [0]*MAX


def nCk_init(n, mod, MAX):
    facinv[0] = facinv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        inv[i] = -inv[mod % i] * (mod // i) % mod
        facinv[i] = facinv[i-1] * inv[i] % mod
    cmb[0] = 1
    for i in range(1, MAX):
        cmb[i] = cmb[i-1] * ((n-i+1)*inv[i] % mod) % mod


nCk_init(n, mod, MAX)
ans = pow(2, n, mod)
ans += mod - cmb[a]
ans %= mod
ans += mod - cmb[b]
ans %= mod
ans += mod - 1
ans %= mod
print(ans)

Submission status: Accepted

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

lm = min(n, 2*10**5)

# ①nCrの各項のmod(10^9+7)を事前計算
p = 10 ** 9 + 7
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, lm + 1):
  fact.append((fact[-1] * i) % p)
  inv.append((-inv[p % i] * (p // i)) % p)
  factinv.append((factinv[-1] * inv[-1]) % p)

# ②事前計算した項を掛け合わせ
def cmb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  rt = 1
  for i in range(r):
    rt = (rt * (n-i)) % p
  rt = rt*factinv[r] % p
  return rt

def pow_r(x, n, p):
  """
  O(log n)
  """
  if n == 0:  # exit case
    return 1
  if n % 2 == 0:  # standard case ① n is even
    return pow_r(x ** 2 % p, n // 2, p)
  else:  # standard case ② n is odd
    return x * pow_r(x ** 2 % p, (n - 1) // 2, p) % p

rlt = pow_r(2,n,p)
  
rlt -= 1


rlt -= cmb(n,a,p) % p
rlt -= cmb(n,b,p) % p

while rlt < 0:
  rlt += p

print(rlt)

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
mod = 10**9 + 7
all = pow(2, n, mod)
if all == 0:
    all = 10**9 + 6
else:
    all -= 1

a = min(n-a,a)
b = min(n-b,b)

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

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

ans = all - nca - ncb

while ans < 0:
    ans += mod
if ans >= mod:
    ans -= mod
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

P = 10 ** 9 + 7


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


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


print((pow(2, n) - conb(n, a) - conb(n, b) - 1) % P)

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
#組み合わせ(数が大きいとき)(10**9+7で割ったもの)
q = 10**9+7
def comb(a, b):
    c = 1
    for i in range(b):
        c *= a - i
        c %= q
    d = 1
    for i in range(b):
        d *= i + 1
        d %= q
    return c*pow(d, q-2, q)
p = pow(2,n,q)-1-comb(n,a)-comb(n,b)
print(p%(10**9+7))

Submission status: Accepted

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

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


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

Submission status: Accepted

Solution code:
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 = numer * ((n - i) % mod) % mod
        denom = denom * ((i + 1) % mod) % mod

    return numer * mod_inverse(denom, mod) % mod


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

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

print(ans)

Submission status: Accepted

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


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


print((s - comb(n, a) - comb(n, b))%mod)

Submission status: Accepted

Solution code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n, a, b = map(int, input().split())
mod = pow(10, 9) + 7
 
def comb(N, x):
    numerator = 1
    for i in range(N-x+1, N+1):
        numerator = numerator * i % mod
    denominator = 1
    for j in range(1, x+1):
        denominator = denominator * j % mod
    d = pow(denominator, mod-2, mod)
    return numerator * d
 
a = comb(n, a)
b = comb(n, b)
 
print((pow(2, n, mod) -1 -a -b) % mod)

Submission status: Accepted

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

def combi(n, k, MOD):
    numer = 1
    for i in range(n, n-k, -1):
        numer *= i
        numer %= MOD
    denom = 1
    for j in range(k, 0, -1):
        denom *= j
        denom %= MOD
    return (numer*(pow(denom, MOD-2, MOD)))%MOD

def main():
    n, a, b = map(int, input().split())
    allsum = pow(2, n, MOD)
    s1 = combi(n, a, MOD)
    s2 = combi(n, b, MOD)
    ans = (allsum - s1 - s2 - 1)%MOD
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def choose(n, a):
    global 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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
n, a, b = map(int, input().split())
MOD = 1000000007

def cmb(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 = pow(2, n, MOD) - 1
A = cmb(n, a, MOD)
B = cmb(n, b, MOD)

print((N - A - B) % MOD)

Submission status: Accepted

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

def cmb(n, r):
    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

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

Submission status: Accepted

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

def modInverse(a,p):
    # Fermat's little theorem, a**(p-1) = 1 mod p
    return pow(a,p-2,p)

def nCr(n,r,p=mod):
    num = 1
    den = 1
    for i in range(r):
        num = (num*(n-i)) % p
        den = (den*(i+1)) % p
    return num*modInverse(den,p)% p

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,A,B=map(int,input().split())
p=10**9+7
def cmb(n,k):
    x,y = 1,1
    for i in range(k):
        x=x*(n-i)%p
        y=y*(i+1)%p
    return x*pow(y,p-2,p)%p
print((pow(2,N,p)-cmb(N,A)-cmb(N,B)-1)%p)

Submission status: Accepted

Solution code:
def cmb(n,k,p):
    x,y = 1,1
    for i in range(k):
        x = x * (n-i) % p
        y = y * (i+1) % p
    res = x * pow(y,p-2,p) % p
    return res

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

Submission status: Accepted

Solution code:
from math import factorial
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n,a,b = nm()
mod = 10**9+7

MAX = 10**6


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
    

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

def modcom(n,a,mod):
  X=1
  Y=1
  for i in range(a):
    X*=(n-i)
    X%=mod
  for i in range(a):
    Y*=(a-i)
    Y%=mod
  return X * modpow(Y,mod-2,mod)%mod


ans -= modcom(n,a,mod)
ans -= modcom(n,b,mod)

print(ans % mod)

Submission status: Accepted

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

Submission status: Accepted

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

a_num = list(range(1,a+1))
j = 0
for i in range(1,a+1):
    comb_a *= (n-i+1)
    comb_a *= pow(a_num[i-1],m-2,m)
    comb_a = comb_a % m

b_num = list(range(1,b+1))
j = 0
for i in range(1,b+1):
    comb_b *= (n-i+1)
    comb_b *= pow(b_num[i-1],m-2,m)
    comb_b = comb_b % m

ans = pow(2,n,m) - comb_a - comb_b - 1
print(int(ans) % m)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
MOD=10**9+7
def inv(a):
  return pow(a,MOD-2,MOD)
def choose(n,r):
  if r==0 or r==n:
    return 1
  else:
    A=B=1
    for i in range(r):
      A=A*(n-i)%MOD
      B=B*(i+1)%MOD
    return A*inv(B)%MOD
print((pow(2,n,MOD)-1-choose(n,a)-choose(n,b))%MOD)

Submission status: Accepted

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

def choose(n,r):
  if r==0 or r==n:
    return 1
  else:
    A=B=1
    ls_A=[1]
    ls_B=[1]
    for i in range(r):
      A=ls_A[i]*(n-i)%MOD
      ls_A.append(A)
      B=ls_B[i]*(i+1)%MOD
      ls_B.append(B)
    return ls_A[r]*inv(ls_B[r])%MOD

def pow_k(x,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%MOD
    return K*x%MOD 

print((pow_k(2,n)-1-choose(n,a)-choose(n,b))%MOD)

Submission status: Accepted

Solution code:
def bigcmb(N, R, MOD):
    if (R < 0) or (N < R):
        return 0
    R = min(R, N - R)
    fact, inv = 1, 1
    for i in range(1, R + 1):
        fact = (fact * (N - i + 1)) % MOD
        inv = (inv * i) % MOD
    return fact * pow(inv, MOD - 2, MOD) % MOD


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

exc = bigcmb(n, a, mod) + bigcmb(n, b, mod)
print((pow(2, n, mod) - exc - 1) % mod)

Submission status: Accepted

Solution code:

def bigcmb(N, R, MOD):  # nCr(mod p) #n>=10**7 #前処理不要
    if (R < 0) or (N < R):
        return 0
    R = min(R, N - R)
    fact, inv = 1, 1
    for i in range(1, R + 1):
        fact = (fact * (N - i + 1)) % MOD
        inv = (inv * i) % MOD
    return fact * pow(inv, MOD - 2, MOD) % MOD


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

exc = bigcmb(n, a, mod) + bigcmb(n, b, mod)
print((pow(2, n, mod) - exc - 1) % mod)

Submission status: Accepted

Solution code:
# N = int(input())
def cmb(n, r, mod):
    x = 1
    for i in range(r):
        x = x * (n-i) % mod
    return (x * g2[r]) % mod


mod = 10**9+7 #出力の制限
N = 2*10**5
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)

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

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

    return (k * x) % MOD

n, a, b = [int(i) for i in input().split()]
MOD = 10 ** 9 + 7
n_num = pow_(2, n) - 1
a_num = cmb(n, a, MOD)
b_num = cmb(n, b, MOD)
print((n_num - a_num - b_num) % MOD)

Submission status: Accepted

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

Submission status: Accepted

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

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

nca = comb(n, a)
ncb = comb(n, b)
all -= nca + ncb
print(all%mod)

Submission status: Accepted

Solution code:
def power(x, y, p) : 
    res = 1     # Initialize result 
  
    # Update x if it is more 
    # than or equal to p 
    x = x % p  
      
    if (x == 0) : 
        return 0
  
    while (y > 0) : 
          
        # If y is odd, multiply 
        # x with result 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
  
        # y must be even now 
        y = y >> 1      # y = y/2 
        x = (x * x) % p 
          
    return res 
def ncr(n, r, p): 
    # initialize numerator 
    # and denominator 
    num = den = 1 
    for i in range(r): 
        num = (num * (n - i)) % p 
        den = (den * (i + 1)) % p 
    return (num * pow(den, p - 2, p)) % p 
n,a,b=map(int,input().split())
m=10**9+7;
ans=power(2,n,m)
ans-=ncr(n,a,m)
ans-=ncr(n,b,m)
print(ans%m-1)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def modpow(a, n, p):
    if n == 0: return 0
    elif n == 1: return a % p
    elif n % 2: return (a * modpow(a, n - 1, p)) % p
    else:
        t = modpow(a, n // 2, p)
        return (t * t) % p

def calc(n, r):
    p, q = 1, 1
    for i in range(r):
        p = p * (n - i) % MOD
        q = q * (i + 1) % MOD
    return p * modpow(q, MOD - 2, MOD) % MOD
    

MOD = 10 ** 9 + 7

N, a, b = map(int, input().split())
s = modpow(2, N, MOD) - 1
print((s - (calc(N, a) + calc(N, b))) % MOD)

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)


def cmb2(n, r, mod):
    if n < r:
        return 0
    re = 1
    for i in range(n - r + 1, n + 1):
        re = (re * i) % mod
    for i in range(1, r + 1):
        re = (re * inverse(i, mod)) % mod
    return re % mod


def inverse(a, p):
    a_, p_ = a, p
    x, y = 1, 0
    while p_:
        t = a_ // p_
        a_ -= t * p_
        a_, p_ = p_, a_
        x -= t * y
        x, y = y, x
    x %= p
    return x


# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(n, a, b):
    mod = 10 ** 9 + 7
    ans = pow(2, n, mod)
    ans = (ans - cmb2(n, a, mod)) % mod
    ans = (ans - cmb2(n, b, mod)) % mod
    ans -= 1  # remove zero flower pattern
    print(ans)


if __name__ == '__main__':
    n, a, b = map(int, input().split())
    solve(n, a, b)

Submission status: Accepted

Solution code:
from functools import reduce
MOD = 10**9 + 7


def cmb(N, A):
    num = reduce(lambda x, y: x * y % MOD, range(N, N - A, -1))
    den = reduce(lambda x, y: x * y % MOD, range(1, A + 1))
    return num * pow(den, MOD - 2, MOD) % MOD


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


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

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MAX = 2 * 10 ** 5 + 5
MOD = 10 ** 9 + 7

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 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 com(mod, n, k):
    numerator = 1
    for i in range(1, k + 1):
        numerator *= (n - i + 1)
        numerator %= mod
    return (numerator * finv[k] % mod)
comInit(MOD)

n, a, b = map(int, readline().split())
nb = n

def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod
ans = (my_pow(2, n, MOD) - 1) % MOD

print((ans - com(MOD, nb, a) - com(MOD, nb, b)) % MOD)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MAX = 2 * 10 ** 5 + 5
MOD = 10 ** 9 + 7

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 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 com(mod, n, k):
    numerator = 1
    for i in range(1, k + 1):
        numerator *= (n - i + 1)
        numerator %= mod
    return (numerator * finv[k] % mod)
comInit(MOD)

n, a, b = map(int, readline().split())
nb = n
x = 2
y = 1
while n > 1:
    if n % 2 == 1:
        y *= x
        n -= 1
    else:
        x *= x
        n //= 2
    x %= MOD
    y %= MOD
ans = (x * y % MOD) - 1
print((ans - com(MOD, nb, a) - com(MOD, nb, b)) % MOD)

Submission status: Accepted

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

def mypow(x, y, mod):
   ans = 1
   while y > 0:
      if bin(y & 1) == bin(1):
         ans *= x % mod
      x *= x % mod
      y = y >> 1
   return ans

def comb(n, r, mod):
   num, denom = 1, 1
   for i in range(1, r+1):
      num = (num*(n+1-i)) % mod
      denom = (denom*i) % mod
   return num * mypow(denom, mod-2, mod) % mod

print((mypow(2, n, mod) - 1 - comb(n, a, mod) - comb(n, b, mod)) % mod)

Submission status: Accepted

Solution code:
from functools import reduce
N,a,b = map(int,input().split())
MOD = 10**9+7
def f(r):
    nPr = reduce(lambda x,y: x * y % MOD,range(N,N-r,-1))
    r_fact = reduce(lambda x,y: x * y % MOD,range(1,r+1))
    return nPr * pow(r_fact,MOD-2,MOD) % MOD
result = pow(2,N,MOD) - f(a) - f(b) - 1
result %= MOD
print(result)

Submission status: Accepted

Solution code:
import math


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

c1=1
c2=1

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

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

print((ans-c1-c2)%mod)

Submission status: Accepted

Solution code:
from functools import reduce
def cmb(n,r,mod):
  r=min(r,n-r)
  if r==0:
    return 1
  over=reduce(lambda x,y:(x*y)%mod,range(n,n-r,-1))
  under=reduce(lambda x,y:(x*y)%mod,range(1,r+1))
  return (over*pow(under,mod-2,mod))%mod

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

Submission status: Accepted

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

Submission status: Accepted

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

def comb(n,r,m):
    x,y=1,1
    for i in range(r):
        x*=n-i
        y*=i+1
        x%=m
        y%=m
    return int(x * pow(y, m-2, m))
ans = pow(2, n, m)-1-comb(n, a, m) - comb(n, b, m)
print(ans%m)

Submission status: Accepted

Solution code:
from functools import reduce
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

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


def comb_mod(n, a):
    num = reduce(lambda x, y: x * y % MOD, range(n, n - a, -1))
    den = reduce(lambda x, y: x * y % MOD, range(1, a + 1))
    return num * pow(den, MOD - 2, MOD) % MOD


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

print(ans)

Submission status: Accepted

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

def 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

N=pow(2,n)
def comb(c,d):
  x=1
  for i in range(d):
    x=x*(c-i)%mod
  y=1
  for i in range(d):
    y=y*(i+1)%mod
  return x*pow(y,mod-2)%mod
A=comb(n,a)
B=comb(n,b)
print((N-A-B-1)%mod)

Submission status: Accepted

Solution code:
p = 10**9+7
def power_func(a,n):
    bi=str(format(n,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
          res=(res*a) %p
    return res
g1,g2,inverse = [1, 1],[1, 1],[0, 1]
for i in range(2,2*(10**5)+1):
    g1.append((g1[-1]*i)%p)
    inverse.append((-inverse[p%i]*(p//i))%p)
    g2.append((g2[-1]*inverse[-1])%p)
n,a,b= map(int,input().split())
comnk=1
temp1=-1
for i in range(b):
    comnk=(((comnk*(n-i))%p)*inverse[i+1])%p
    if i==a-1:temp1=(power_func(2,n)-1+p-comnk)%p
print((temp1 + p - comnk) % p)

Submission status: Accepted

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

def modinv(n):
    return pow(n, M-2, M)

def comb(n, r):
    num = denom = 1
    for i in range(1,r+1):
        num = (num*(n+1-i))%M
        denom = (denom*i)%M
    return num * modinv(denom) % M

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

Submission status: Accepted

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

def modinv(n):
    return pow(n, M-2, M)

def comb(n, r):
    num = 1
    for i in range(n,n-r,-1):
        cur = i
        while cur%M == 0:
            cur //= M
        num = (num*cur)%M

    denom = 1
    for i in range(1,r+1):
        cur = i
        while cur%M == 0:
            cur //= M
        denom = (denom*cur)%M

    return num * modinv(denom) % M


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

Submission status: Accepted

Solution code:
# Vicfred
# https://atcoder.jp/contests/abc156/tasks/abc156_d
# math
def binpow(a, b, m):
    a %= m
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % m
        a = a * a % m
        b >>= 1
    return res

def binomial(n, k, m):
    x = 1
    y = 1
    for i in range(k):
        x *= n-i
        x %= m
        y *= i+1
        y %= m
    y = binpow(y, m-2, m)
    return (x*y)%m

mod = 10**9+7

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

print((binpow(2, n, mod) - binomial(n,a, mod) - binomial(n,b, mod) - 1 + mod)%mod)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = 10**9 + 7
 
def powerDX(n, r, mod):
  if r == 0: return 1
  if r%2 == 0:
    return pow(n*n % mod, r//2, mod) % mod
  if r%2 == 1:
    return n * pow(n, r-1, mod) % mod
 
def combination(n, r, mod=10**9+7):
    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
 
ans = pow(2, n, mod) - 1
ans -=  combination(n, a, mod)
ans -=  combination(n, b, mod)
ans += 3*mod
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = 10**9 + 7
 
def powerDX(n, r, mod):
  if r == 0: return 1
  if r%2 == 0:
    return pow(n*n % mod, r//2, mod) % mod
  if r%2 == 1:
    return n * pow(n, r-1, mod) % mod
 
def combination(n, r, mod=10**9+7):
    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 * powerDX(denom, mod-2, mod) % mod
 
ans = pow(2, n, mod) - 1
ans -=  combination(n, a, mod)
ans -=  combination(n, b, mod)
ans += 3*mod
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = 10**9 + 7
 
def powerDX(n, r, mod):
  if r == 0: return 1
  if r%2 == 0:
    return powerDX(n*n % mod, r//2, mod) % mod
  if r%2 == 1:
    return n * powerDX(n, r-1, mod) % mod
 
def combination(n, r, mod=10**9+7):
    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 * powerDX(denom, mod-2, mod) % mod
 
ans = pow(2, n, mod) - 1
ans -=  combination(n, a, mod)
ans -=  combination(n, b, mod)
ans += 3*mod
ans %= mod
print(ans)

Submission status: Accepted

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

from functools import reduce
def comb(n,k,p):
    A = reduce(lambda x,y:x*y%p ,[n-k+1+i for i in range(k)])
    B = reduce(lambda x,y:x*y%p ,[i+1 for i in range(k)])
    return A*pow(B,p-2,p)%p

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

Submission status: Accepted

Solution code:
def cmb(n,r,mod):
	a=1
	b=1
	r = min(r,n-r)
	for i in range(r):
		a = a*(n-i)%mod
		b = b*(i+1)%mod
	return a*pow(b,mod-2,mod)%mod
mod = 10**9+7
n,a,b = list(map(int,input().split()))
ans = pow(2,n,mod)+mod - cmb(n,a,mod) - cmb(n,b,mod)
ans = (ans -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

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((ans-combination(n, a)-combination(n, b))%mod)

Submission status: Accepted

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

mod = 10**9 + 7
def cmb(n,r,mod):
	a=1
	b=1
	r = min(r,n-r)
	for i in range(r):
		a = a*(n-i)%mod
		b = b*(i+1)%mod
	return a*pow(b,mod-2,mod)%mod

all = pow(2,N,mod) + mod
nCa = cmb(N,A,mod)
nCb = cmb(N,B,mod)

ans = all - nCa - nCb
print((ans-1)%mod)

Submission status: Accepted

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

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= MOD

    for i in range(1,k+1):
        nCk *= pow(i,MOD-2,MOD)
        nCk %= MOD
    return nCk

x=pow(2,n,10**9+7)-1
y=comb(n,a)+comb(n,b)
ans=x-y





while ans<0:
          ans+=10**9+7
print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    n,a,b = LMIIS()
    def cmb(n,r):
        if r == 0:
            return 0
        res = 1
        r = min(r,n-r)
        for i in range(n-r+1,n+1):
            res *= i
            res %= MOD
        for i in range(1,r+1):
            res *= pow(i,(MOD-2),MOD)
            res %= MOD
        return res
    print((pow(2,n,MOD)-cmb(n,a)-cmb(n,b)-1)%MOD)

    
if __name__ == '__main__':
    main()

Submission status: Accepted

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



def Mod_pow(x, n):
    x = x%Mod
    if n==0:
        return 1
    elif n%2==1:
        return (x*Mod_pow(x,n-1)%Mod)
    else:
        return (Mod_pow(x*x,n/2)%Mod)


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

    for i in range(1,r+1):
        y = y*i%Mod

    #この問題の特徴，フェルマーの小定理よりyで除算することはy^(Mod-2)をかけることと同値
    y = Mod_pow(y,Mod-2)
    return x*y%Mod

ans = (Mod_pow(2,n)-1-comb(n,a)-comb(n,b))
while ans<0:
    ans += Mod

print(ans)