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:
import functools

def get_mul_inverse(x: int, p: int) -> int:
    return iterative_square(x, p - 2, p)

def _iterative_square(x: int, n: int, p: int) -> int:
    if n <= 1:
        return x
    div, mod = divmod(n, 2)
    return (((iterative_square(x, div, p) ** 2) % p) * x ** mod) % p

def iterative_square(x: int, n: int, p: int) -> int:
    if n <= 0:
        return None

    return _iterative_square(x, n, p)

def factorial(a, b, p):
  x = 1

  x = functools.reduce(lambda x, y: (x * y) % p, range(a, b + 1), 1)
  return x

def com(n, r, p):
  fact_div_r = get_mul_inverse(factorial(1, r, p), p)

  _result = factorial(n - r + 1, n, p)
  result = (_result * fact_div_r) % p
  
  return result


n, a, b = [int(i) for i in input().split()]
p = 10**9 + 7


pow_2_n_1 = iterative_square(2, n, p) - 1

_result = pow_2_n_1 - com(n, a, p)

_result = _result - com(n, b, p)

result = _result % p
print(result)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
value_max = 2 * (10 ** 5)
com = [0 for _ in range(value_max + 1)]
com[1] = n
mod = 10 ** 9 + 7
mod_inverse = [pow(i, mod - 2, mod) for i in range(1, value_max + 1)]
ans = pow(2, n, mod)

for i in range(2, min(n, value_max) + 1):
    if (n - i + 1) == 0:
        break

    com[i] = com[i - 1] * (n - i + 1)
    com[i] *= mod_inverse[i - 1]
    com[i] %= mod

diff = (com[a] + com[b] + 1) % mod
print((ans - diff) % mod)

Submission status: Accepted

Solution code:
def binom(n, r, mod):
    if n < r or n < 0 or r < 0: return 0
    
    if n - r < r: r = n - r
    if r == 0: return 1
    elif r == 1: return n

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

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

Submission status: Accepted

Solution code:
def binom(n, r, mod):
    if n < r or n < 0 or r < 0: return 0
    
    if n - r < r: r = n - r
    if r == 0: return 1
    elif r == 1: return n

    numerator = [(n - r + 1 + k) % mod for k in range(r)]  # (n-r+1)*(n-r+2)*...*(n-1)*n
    denominator = [1 + k for k in range(r)]         # 1*2*...*(r-1)*r

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

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

Submission status: Accepted

Solution code:
p = 10**9+7
def combmod(x, n):
    X = 1
    Y = 1
    for i in range(x):
        X = X * (n-i)%p
        Y = Y * (i+1)%p
    return X*pow(Y, p-2, p)%p
def main():
    n, a, b = list(map(int, input().split()))
    numall = pow(2, n, p) - 1 
    numa = combmod(a, n)
    numb = combmod(b, n)
    print((numall-numa-numb)%p)
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(n: int, a: int, b: int):
    # 1本選ぶ時→nC1、2本選ぶ時→nC2、...、n本選ぶ時→nCn
    # 二項定理の和の公式より、上記の和はnC1+nC2+...+nCn=2**n
    # ans=2**n-1-nCa-nCb # 「-1」は、0本選ぶ場合を除外している。(問題の制限がN>=1なので)
    # 数列nCaの総和 = ΣnCa = n/1 + n(n-1)/2*1 + n(n-1)(n-2)/3*2*1 + ... + n(n-1)(n-2)...(n-a+1)/a!
    # ΣnCa = Π(n-a)/a! # Π(パイ)は総乗(数列を掛け算した合計)のこと。Σ(シグマ)は総和。
    # 2**nは普通に**で求めるとTLEする。python3ならpow()を使用することでO(logn)で計算できる。「繰り返し二乗法」という。
    # 繰返し二乗法・・・f(x) = 2**x、f(2x) = f(x)**2、f(2x+1) = f(x)**2 * 2、f(N) = f(2/N)**2
    nCa = choose(n, a)
    nCb = choose(n, b)
    ans = (pow(2, n, MOD) - 1 - nCa - nCb) % MOD
    print(int(ans))


def choose(n, a):
    x = y = 1  # xが分子、yが分母
    for i in range(a):
        x *= n - i
        x %= MOD
        y *= i + 1
        y %= MOD
    # 割り算はコストが高いので,x/yするとTLEする。
    # mod pの結果が素数の場合は、フェルマーの小定理でx=x**(p-1)となる。
    # ここから逆元(逆数)を求めると、1/x = x**(p-1)/x = x**(p-2)となる。
    return x * pow(y, MOD-2, MOD) % MOD


# 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:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(n: int, a: int, b: int):
    # 1本選ぶ時→nC1、2本選ぶ時→nC2、...、n本選ぶ時→nCn
    # 二項定理の和の公式より、上記の和はnC1+nC2+...+nCn=2**n
    # ans=2**n-1-nCa-nCb # 「-1」は、0本選ぶ場合を除外している。(問題の制限がN>=1なので)
    # 数列nCaの総和 = ΣnCa = n/1 + n(n-1)/2*1 + n(n-1)(n-2)/3*2*1 + ... + n(n-1)(n-2)...(n-a+1)/a!
    # ΣnCa = Π(n-a)/a! # Π(パイ)は総乗(数列を掛け算した合計)のこと。Σ(シグマ)は総和。
    # 2**nは普通に**で求めるとTLEする。python3ならpow()を使用することでO(logn)で計算できる。「繰り返し二乗法」という。
    # 繰返し二乗法・・・f(x) = 2**x、f(2x) = f(x)**2、f(2x+1) = f(x)**2 * 2、f(N) = f(2/N)**2
    nCa = choose(n, a)
    nCb = choose(n, b)
    ans = (pow(2, n, MOD) - 1 - nCa - nCb) % MOD
    print(int(ans))


def choose(n, a):
    x = y = 1  # xが分子、yが分母
    for i in range(a):
        x *= n - i
        x %= MOD
        y *= i + 1
        y %= MOD
    return x * pow(y, MOD-2, MOD) % MOD


# 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 = map(int, input().split())
mod = 10**9 + 7
def c(x):
  out = 1
  for i in range(min(x, n-x)):
    out *= n-i
    out *= pow(i+1, mod-2, mod)
    out %= mod
  return out
ans = pow(2, n, mod) -1 -c(a)-c(b)
ans %= mod
print(ans)

Submission status: Accepted

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

DIVIDER = 10 ** 9 + 7
MAX_BIT = 64

flg_DIV = []
tmp = DIVIDER - 2
for i in range(MAX_BIT):
    flg_DIV.append(tmp % 2)
    tmp >>= 1

memo = [None] * (max(a, b) + 1)
    
def myinv(arg):
    global DIVIDER
    if memo[arg] != None: return memo[arg]
    pow_arg = []
    tmp = arg
    for i in range(MAX_BIT):
        pow_arg.append(tmp)
        tmp = (tmp * tmp) % DIVIDER
    #
    # print("##", arg, pow_arg)
    ret = 1
    for i in range(MAX_BIT):
        if flg_DIV[i]:
            ret = (ret * pow_arg[i]) % DIVIDER
    #
    memo[arg] = ret
    return ret

# def mydiv(arg_a, arg_b):
#     ret = (arg_a * myinv(arg_n)) % DIVIDER
#     return ret

# calc 2^n
flg_n = []
tmp = n
for i in range(MAX_BIT):
    flg_n.append(tmp % 2)
    tmp >>= 1

pow_2 = []
tmp = 2
for i in range(MAX_BIT):
    pow_2.append(tmp)
    tmp = (tmp * tmp) % DIVIDER

ans = 1
for i in range(MAX_BIT):
    if flg_n[i]:
        ans = (ans * pow_2[i]) % DIVIDER
# print("# 2^n =", ans)
        
# subtract nCa ans nCb
nCa = 1
for i in range(min(a, n - a)):
    nCa = (nCa * (n - i)) % DIVIDER
# print("# {0}C{1} =".format(n, a), nCa)
for i in range(min(a, n - a)):
    nCa = (nCa * myinv(i + 1)) % DIVIDER
# print("# {0}C{1} =".format(n, a), nCa)

nCb = 1
for i in range(min(b, n - b)):
    nCb = (nCb * (n - i)) % DIVIDER
# print("# {0}C{1} =".format(n, b), nCb)
for i in range(min(b, n - b)):
    nCb = (nCb * myinv(i + 1)) % DIVIDER
# print("# {0}C{1} =".format(n, b), nCb)
# print("#", 2, myinv(2), (2 * myinv(2)) % DIVIDER)

ans = (ans - nCa) % DIVIDER
ans = (ans - nCb) % DIVIDER
ans = max(0, ans - 1) # no flower

print(ans)

Submission status: Accepted

Solution code:
def cmb(n,r,mod):
    x=1
    y=1
    if n/2<r:
        r=n-r
    for i in range(r):
        x*=n-i
        if x>mod:
            x%=mod
        y*=r-i
        if y>mod:
            y%=mod
    val=x*pow(y,mod-2,mod)%mod #pow(y,mod-2,mod)モジュラ逆数
    return val

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

bouquet()

Submission status: Accepted

Solution code:
# from .myutil import Combination
from math import factorial

MOD = 10 ** 9 + 7
def Combination2(n, r):
    ret = 1
    for i in range(r):
        ret = ret * (n - i) % MOD
    return ret * pow(factorial(r), MOD - 2, MOD) % MOD

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

total = pow(2, n, MOD) - Combination2(n, a) - Combination2(n, b) - 1
total %= MOD

print(total)

Submission status: Accepted

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


"""
def power_func(a,n,p):
  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
"""
def cmb(n, r, p):
    #print(r)
    if (r < 0) or (n < r):
        return 0
    tmp = 1
    for i in range(r):
        tmp *= (n-i) % p
        tmp %= p
        tmp *= pow(r-i,p-2,p) % p
        tmp %= p
    return tmp%p
    #r = min(r, n - r)
    #return fact[n] * factinv[r] * factinv[n-r] % p

N = n

"""
def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
        print(n,x,ans)
    return ans

pow(2,9)
exit()
"""
p = 10 ** 9 + 7
#N = 10 ** 6  # N は必要分だけ用意する
"""
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
"""
ans = (pow(2,n)-1)%p
#print(ans)
#exit()
#print(cmb(n, a, p) , cmb(n, b, p))
#print(ans,cmb(n, a, p),cmb(n, b, p))
ans -= (cmb(n, a, p) + cmb(n, b, p))

print(ans%p)

Submission status: Accepted

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

factorial = [1]
for i in range(1, N + 1):
    factorial.append((factorial[i - 1] * i) % mod)

p_list = [n % mod]
for i in range(1, N + 1):
    p_list.append((p_list[i - 1] * (n - i)) % mod)

x = pow(2, n, mod) - 1
ya = pow(factorial[a], 10 ** 9 + 5, mod)
yb = pow(factorial[b], 10 ** 9 + 5, mod)

print((x - p_list[a - 1] * ya - p_list[b - 1] * yb) % mod)

Submission status: Accepted

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

def calc_inv(n, k, mod):
    a = 1
    b = 1
    for i in range(1,k+1):
        a *= i
        a %= mod
        b *= n
        n -= 1
        b %= mod
    return b * pow(a, mod-2, mod) % mod

ret = pow(2, N, MOD) - 1 - calc_inv(N,A,MOD) - calc_inv(N,B,MOD)
ret %= MOD
if ret < 0:
    ret += MOD
print(int(ret))

Submission status: Accepted

Solution code:
n,d,e = map(int,input().split())

mod = 10**9+7
x = pow(2,n,mod)

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

def f(hiki):
    fac = 1
    for i in range(1,1+hiki):
        fac = fac*i%mod
    return fac

a2 = pow(f(d),mod-2,mod)
b2 = pow(f(e),mod-2,mod)

a_mod = a*a2%mod
b_mod = b*b2%mod
print((x-a_mod-b_mod-1)%mod)

Submission status: Accepted

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

p = 10**9 + 7

def pow(a,n,m):
  ans = 1
  while n:
    if n % 2:
      ans *= a
    a *= a
    a = a%m
    n >>= 1
  return ans%m

def x(n,a):
  ans = 1
  for i in range(a):
    ans *= (n-i)
    ans = ans%p
  return ans

def y(n):
  ans = 1
  for i in range(1,n+1):
    ans *= i
    ans = ans%p
  return ans

al = pow(2,n,p)
ap = pow(y(a), p-2,p)
bp = pow(y(b), p-2,p)
ap = ap*x(n,a) % p
bp = bp*x(n,b) % p
if al-ap-bp-1 < 0:
  z = al-ap-bp-1+p
  while z < 0:
    z = z + p
  print(z)
else:
  print(al-ap-bp-1)

Submission status: Accepted

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

def remainder_of_combination(n, r, p):
    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
        
    return X * pow(Y, p-2, p)

ans = -1 + pow(2, n, p) - remainder_of_combination(n, a, p) - remainder_of_combination(n, b, p)

print(ans % p)

Submission status: Accepted

Solution code:
import math
m=10**9+7
n,a,b=map(int,input().split())
if(a>n//2):
  a = n-a
if(b>n//2):
  b = n-b
aa=min(a,b)
bb=max(a,b)
na=1
nb=1
da=1
db=1
for i in range(aa):
  na=na*(n-i)%m
  da=da*(1+i)%m
  nb=nb*(n-i)%m
  db=db*(1+i)%m
for i in range(aa,bb):
  nb=nb*(n-i)%m
  db=db*(1+i)%m
CA=(na*pow(da,m-2,m))%m
CB=(nb*pow(db,m-2,m))%m
c=pow(2,n,m)-CA-CB-1
print(c%m)

Submission status: Accepted

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

def power_func(a,n,p):
  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

def cmb(n, r, p):
    #print(r)
    if (r < 0) or (n < r):
        return 0
    tmp = 1
    for i in range(r):
        tmp *= (n-i) % p
        tmp %= p
        tmp *= power_func(r-i,p-2,p) % p
        tmp %= p
    return tmp%p
    #r = min(r, n - r)
    #return fact[n] * factinv[r] * factinv[n-r] % p

def cmb_old(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p



N = n

def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
        print(n,x,ans)
    return ans

#pow(2,9)
#exit()

p = 10 ** 9 + 7
#N = 10 ** 6  # N は必要分だけ用意する
"""
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
"""
ans = power_func(2,n,p)-1
#print(ans)
#exit()
#print(cmb(n, a, p) , cmb(n, b, p))
#print(ans,cmb(n, a, p),cmb(n, b, p))
ans -= (cmb(n, a, p) + cmb(n, b, p))

print(ans%p)

Submission status: Accepted

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

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

comb2 = 1
for i in range(n-b+1, n+1):
    comb2 *= i
    comb2 %=  mod
for i in range(1, b+1):
    comb2 *= pow(i, mod-2, mod)
    comb2 %=  mod
ans -= (comb1 + comb2)
print(ans % mod)

Submission status: Accepted

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

mod = 1000000007

def choose(n, a):
    x = 1
    y = 1
    if n/2 < a:
        a = n - a
    for i in range(a):
        x *= n - i
        if x > mod:
            x %= mod
        y *= a - i
        if y > mod:
            y %= mod
    val = x * pow(y, mod-2, mod) % mod
    return val

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

Submission status: Accepted

Solution code:
MOD = 10**9+7


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


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


main()

Submission status: Accepted

Solution code:
mod = 1000000007
def choose(n, a):
    x = 1
    y = 1
    if n/2 < a:
        a = n - a
    for i in range(a):
        x *= n - i
        if x > mod:
            x %= mod
        y *= a - i
        if y > mod:
            y %= mod
    val = x * pow(y, mod-2, mod) % mod
    return val

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

ans=pow(2,N,mod)-1
ans=(ans-conbination(N,a)-conbination(N,b))%mod
print(ans)

Submission status: Accepted

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

def cmb(n, r):
  num=1
  den=1
  for i in range(0,r):
    num*=n-i
    den*=i+1
    num%=p
    den%=p
  return num*modinv(den,p)%p
def power(x,a):
    if a==0:
        return 1
    if a==1:
        return x%p
    if a%2==0:
        return power(x,a//2)**2%p
    else:
        return power(x,a//2)**2*x%p
def modinv(x,p):
    return power(x,p-2)
ans=(pow(2,n,p)-cmb(n,a)-cmb(n,b)-1)%p
print(ans)

Submission status: Accepted

Solution code:
import math

z = 10**9 + 7

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

r = pow(2, n, z) - 1

def c(m):
  x = 1
  for i in range(n-m+1, n+1):
    x = x*i % z
  
  return (x * pow(math.factorial(m), z-2, z)) % z

r = (r - c(a) - c(b)) % z

print(r)

Submission status: Accepted

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

def cmb(N,K):
    r=1

    for i in range(K):
        r=r*(N-i)*pow(i+1,mod-2,mod)%mod

    return r
ans=((pow(2,N,mod)-1)%mod-cmb(N,a)-cmb(N,b))%mod
#逆元の割り算のmodは、分子*逆元（分母)%modと等価　フェルマーの小定理から、 逆元はpow(b,mod-2,mod)となる
print(ans)

Submission status: Accepted

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


def modpow(a, b, mod=10 ** 9 + 7):
    ret = 1
    while b > 0:
        if b % 2 == 1:
            ret = ret * a % mod
        a = a * a % mod
        b //= 2
    return ret


def modcomb(n, c, mod=10 ** 9 + 7):
    if c > n - c:
        c = n - c
    u, d = 1, 1
    for i in range(c):
        u = u * (n - i) % mod
        d = d * (i + 1) % mod
    return u * modpow(d, mod - 2) % mod


print((modpow(2, n) - modcomb(n, a) - modcomb(n, b)) % (10 ** 9 + 7) - 1)

Submission status: Accepted

Solution code:
n,a,b = list(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

def m_power_n_mod(m,n,mod):
    q = 1
    f = m
    while(n > 0):
        c = n % 2
        n = int((n-c)/2)
        q = (q * f**c) % mod
        f = f**2 % mod
    return q

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

Submission status: Accepted

Solution code:
mod = 10**9 + 7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

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

ans = pow(2,n,mod) -1
ncr = 1
for i in range(1,max(a,b)+1):
  ncr = ncr * (n-i+1) * modinv(i) % mod
  if i == a or i == b:
    ans -= ncr
    if (ans < 0):
      ans += mod
print(ans)

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
p = 10**9 + 7
def comb(n,r):
	bunshi = 1
	for i in range(n-r+1,n+1):
		bunshi = bunshi * i % p
	bunbo = 1
	for i in range(1,r+1):
		bunbo = bunbo * i % p

	return bunshi * pow(bunbo,p-2,p)


s = -1 + pow(2,n,p) - comb(n,a) -comb(n,b)

print(s%p)

Submission status: Accepted

Solution code:
import numpy as np
import math as m

def main(**kwargs):
    mod = 10 ** 9 + 7
    r = repeatSquare(2, n, mod) - 1
    r -= factMod(n, n - a + 1, mod) * repeatSquare(factMod(a, 1, mod), mod - 2, mod)
    r -= factMod(n, n - b + 1, mod) * repeatSquare(factMod(b, 1, mod), mod - 2, mod)
    r %= mod
    return r

def repeatSquare(n, p, m):
    if p == 0:
        return 1

    if p % 2 == 0:
        tmp = repeatSquare(n, p/2, m) % m
        return tmp * tmp % m

    return n * repeatSquare(n, p-1, m) % m

def factMod(n, r, m):
    res = n

    while n > r:
        n -= 1
        res *= n
        res %= m

    return res

if __name__ == "__main__":
    
    cin = np.array(input().split(" ")).astype("int")
    n, a, b = cin

    cout = main(n=n, a=a, b=b)
    print(cout)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

def combination(n,a):
    x = 1
    for i in range(a):
        x = x * (n-i) % mod
    y = 1
    for i in range(a):
        y = y * (a-i) % mod
    y = pow(y, mod-2, mod)
    return (x*y % mod)
n, a, b = map(int, input().split())
mod = 1000000007
print((pow(2,n,mod) - 1 - combination(n,a) - combination(n,b)) % mod)

Submission status: Accepted

Solution code:
import sys

def comb_mod(n, r, mod):
  x = 1
  y = 1
  for i in range(r):
    x = (x * (n - i)) % mod
    y = (y * (i + 1)) % mod
    
  ans = x * pow_k(y, mod-2, mod)
  
  return ans % mod
  
  
def pow_k(x, n, mod):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (x * K) % mod
        
    x = (x * x) % mod

    n //= 2

  return (x * K) % mod
  

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

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

ans = pow_k(2, n, mod) - comb_mod(n,a,mod) - comb_mod(n,b,mod) - 1

print(ans % mod)

Submission status: Accepted

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

#print(bin(n))

# 2のN乗の計算
def mypow(b, n):
    ans = 1
    x = b
    while n > 0:
        if bin(n & 1) == bin(1):
            ans *= x
            ans = ans % MOD
        x = x * x
        x = x % MOD
        n = n >> 1
#        print("{} {}".format(ans, bin(n)))
    return ans

# n combination cの計算


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

    ans = (x * mypow(y, MOD - 2)) % MOD
#    print("x:{} y:{} ans:{}".format(x, y, ans))
    return ans

ans1 = mypow(2, n)
ans2 = mycob(n, a)
ans3 = mycob(n, b)

ans = ans1 - ans2 - ans3 - 1
print(ans % MOD)

Submission status: Accepted

Solution code:


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

# 階乗
def fact(n, mod):
    ans = 1
    for i in range(1, n+1):
        ans = (ans*i) % mod
    return ans

# 繰り返し２乗法
def pow(a, n, mod):
    if n == 0:
        return 1
    if n%2 == 0:
        t = pow(a, n//2, mod)
        return t*t % mod
    return a * pow(a, n-1, mod)


# 組み合わせ
def comb(n, a, mod):
    val = pow(fact(a, mod), mod-2, mod)

    p = 1
    for i in range(a):
        p = (p*(n-i)) % mod
    return val*p %mod


mod = 10**9+7
allptn = pow(2, n, mod)
aptn = comb(n, a, mod)
bptn = comb(n, b, mod)

ans = (allptn-1 - aptn - bptn) % mod
print(ans)

Submission status: Accepted

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

x=pow(2,n,mod)

v=1
w=1
for i in range(a):
    v*=n-i
    v%=mod
    w*=a-i
    w%=mod

c=v*pow(w,mod-2,mod)
v=1
w=1
for i in range(b):
    v*=n-i
    v%=mod
    w*=b-i
    w%=mod

d=v*pow(w,mod-2,mod)
d%=mod

ans=(x-c-d-1)%mod
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math 
MOD = 10**9+7
def comb(n,k):
    nCk = 1
    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

def main():
    N,A,B = map(int,input().split())
    print((pow(2,N,MOD)-1-comb(N,A)-comb(N,B))%MOD)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MAX = 10 ** 5 * 2
mod = 10 ** 9 + 7
frac = [1]
def pow(a, n):
    if n == 0 : return  1
    elif n == 1 : return a
    tmp = pow(a, n//2)
    tmp = (tmp * tmp) % mod
    if n % 2 == 1 :
        tmp = (tmp * a) % mod
    return tmp
def inv(x):
    return pow(x, mod - 2 )
def comb(n, k):
    a=1
    b=1
    for i in range(n-k+1,n+1):
        a=(a*i)%mod
    for i in range(1,k+1):
        b=(b*i)%mod
    if k >= n or k < 0 : return 1
    return (a* inv(b))%mod
n,a,b = map(int,input().split())
print((pow(2,n)-1-comb(n,a)-comb(n,b))%mod)

Submission status: Accepted

Solution code:
n, a, b = map(int,input().split())
mod7 = 10 ** 9 + 7
def power(a,b,mod):
    p = 1
    q = a
    while b != 0:
        if b % 2 == 1:
            p = (p * q) % mod
        q = (q * q) % mod
        b = b // 2
    return p

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


def combi(n,a,mod):
    inv_af = power(fact(a,mod),mod-2,mod)
    p = 1
    for i in range(a):
        p = (p * (n-i)) % mod
    return inv_af * p % mod

Answer = (power(2, n, mod7) - combi(n, a, mod7) - combi(n, b, mod7) - 1) % mod7
print(Answer)

Submission status: Accepted

Solution code:
from sys import stdin
mod = 10**9+7
n,a,b = [int(x) for x in stdin.readline().rstrip().split()]

maxn = max(a,b)
inv = [0,1] + [0]*maxn
for i in range(2,maxn+1):
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    
allc = pow(2,n,mod) - 1

def comb(n,r):
    res = 1
    for i in range(1,r+1):
        res *= (n-i+1)
        res *= inv[i]
        res %= mod
    return res

ans = allc - comb(n,a) - comb(n,b)
ans %= mod
print(ans)

Submission status: Accepted

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

def powmod(x, exp, mod):
    if(exp == 1):
        return x % mod

    if(exp % 2 == 1):
        return (x * powmod(x, exp - 1, mod)) % mod

    x = powmod(x, exp / 2, mod)

    return (x * x) % mod

# nCrを計算するが、nもrも巨大なためフェルマーの小定理を利用する
# x = nPr
# y = r!
# x / y ≡ x * y^-1
# p を法とした時、掛けるたびにmodをとった数同士の割り算はうまくいかない
# フェルマーの小定理から
# y^(p-1) ≡ 1
# y * y^(p-2) ≡ 1
# y^(p-2)がyの逆元と同じ振る舞いをするのでy^(p-2)を掛ける
def combination(n, r, mod):
    x = 1
    y = 1

    for i in range(r):
        x *= n - i # n * (n - 1) * (n - 2) * ... * (n - i + 1)
        x %= mod
        y *= i + 1 # r * (r - 1) * (r - 2) * ... * 2 * 1 を逆さまにかけていく
        y %= mod

    return x * powmod(y, mod - 2, mod) % mod


total = powmod(2, n, p) - 1 #1本も花を選ばないパターンは除外する
comb_a = combination(n, a, p)
comb_b = combination(n, b, p)


print((total - comb_a - comb_b) % p)

Submission status: Accepted

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

ans = ans % (10**9+7)
print(ans-1)

Submission status: Accepted

Solution code:

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

mod = 10**9+7

def comb(n,r):
	u = 1
	d = 1
	for i in range(n-r+1,n+1):
		u = u*i%mod

	for i in range(1,r+1):
		d = d*i%mod
	D = pow(d,mod-2,mod)

	return u*D%mod

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

print(ans%mod)

Submission status: Accepted

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

mod = 10**9+7

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

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

Submission status: Accepted

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

Submission status: Accepted

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

MOD=10**9+7
def comb(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%MOD
    for i in range(2,k+1):
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        ans=ans*(n-k+i)*inv[i]%MOD
    return ans

nCa = comb(n,a)
nCb = comb(n,b)

ans = (pow(2,n,MOD) - 1) - nCa - nCb
 
if ans < 0:
    print((ans+MOD)%MOD)
else:
    print(ans%MOD)

Submission status: Accepted

Solution code:
MOD = 1000000007

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

# https://tex2e.github.io/blog/crypto/modular-mul-inverse
def xgcd(a, b):
	x0, y0, x1, y1 = 1, 0, 0, 1
	while b != 0:
		q, a, b = a // b, b, a % b
		x0, x1 = x1, x0 - q * x1
		y0, y1 = y1, y0 - q * y1
	return a, x0, y0

# https://tex2e.github.io/blog/crypto/modular-mul-inverse
def modinv(a, m):
	g, x, y = xgcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

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

ans = 0
ans += pow(2, n, MOD) - 1
ans += MOD - combination(n, a)
ans += MOD - combination(n, b)
ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
def comb(n, r, p):
    numer = 1
    denom = 1

    for i in range(n-r+1, n+1):
        numer = numer * i % p
    for i in range(1, r+1):
        denom = denom * i % p
    return numer * pow(denom, p-2, p)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def func_156d(n, r):
    numerator = 1
    denominator = 1
    for i in range(r):
        numerator = numerator * (n-i) % mod
        denominator = denominator * (i+1) % mod
    return numerator * pow(denominator, mod-2, mod) %mod

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

Submission status: Accepted

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

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

print((pow(2, n, mod) -1 - func_156d(n,a) - func_156d(n,b) + 2*mod) %mod )