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:
class cmb():
    def __init__(self, p=10**9+7, N=10**5+1):
        self.p = p
        self.N = N
        self.fact = [1, 1]
        self.factinv = [1, 1]
        inv = [0, 1]
        for i in range(2, self.N+1):
            self.fact.append((self.fact[-1] * i) % p)
            inv.append((-inv[p%i] * (p//i)) % p)
            self.factinv.append((self.factinv[-1] * inv[-1]) % p)
    def run1(self, a, b):
        return (self.fact[a+b] * self.factinv[a] * self.factinv[b]) % self.p
    def run2(self, n, r):
        return (self.fact[n] * self.factinv[r] * self.factinv[n-r]) % self.p
mod = 10**9+7
def fur(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 = map(int, input().split())
c = cmb()
work = pow(2, n, 10**9+7)
result = (work - fur(n, a) - fur(n, b) - 1) % (10**9+7)
print(result)

Submission status: Accepted

Solution code:
def modInv(a,mod):
  return pow(a,mod-2,mod)

def nCr(n,r,mod):
  r=min(r,n-r)
  if r==0:
    return 1
  if r==1:
    return n
  numer=1
  denom=1
  for i in range(r):
    numer=(n-i)*numer%mod
    denom=(i+1)*denom%mod
  return numer*modInv(denom,mod)%mod

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
ins = lambda: input().strip()
inn = lambda: int(input())
inl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

n, a, b = inl()

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

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

print(sum_comb % mod)

Submission status: Accepted

Solution code:
import numpy as np
from operator import mul
from functools import reduce
def modmul(a,b):
    return a * b % 1000000007
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
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(modmul, range(n, n - r, -1))
    under = reduce(modmul, range(1,r + 1))
    return over * modinv(under, 1000000007)
def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K = (K * x) % 1000000007
        x = (x * x) % 1000000007
        n //= 2
    return (K * x) % 1000000007
n,a,b = (int(x) for x in input().split())
binary = bin(n)
l = []
for i in range(1,len(binary)-1):
    if binary[-i] == "1":
        l.append(pow_k(2,pow_k(2,i-1)))
prod = 1
for value in l:
    prod = (prod * value) % 1000000007
print((prod-(1+(comb(n, a)%1000000007)+(comb(n, b)%1000000007)))%1000000007)

Submission status: Accepted

Solution code:
def modInv(a,mod):
    return pow(a,mod-2,mod)

def nCr(n,r,mod):
    r=min(r,n-r)
    if r==0: return 1
    if r==1: return n
    numer=1
    denom=1
    for i in range(r):
        numer=(n-i)*numer%mod
        denom=(i+1)*denom%mod
    return numer*modInv(denom, mod)%mod
        
n,a,b=map(int,input().split())
mod=10**9+7
f=pow(2,n,mod)-1
A=nCr(n,a,mod)
B=nCr(n,b,mod)
print((f-A-B)%mod)

Submission status: Accepted

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7

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

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

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

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 //= 2

    return K * x % MOD

def kai(x):
    an = 1
    for i in range(1,x+1):
        an = an * i % MOD
        
    return an

def kai2(x,yy):
    an = 1
    for i in range(x+1-yy,x+1):
        an = an * i % MOD
        
    return an

x = pow_k(2,n) - 1

mia = (kai2(n,a) * pow_k(kai(a),MOD-2)) % MOD
mib = (kai2(n,b) * pow_k(kai(b),MOD-2)) % MOD

ans = (4*MOD + x - mia - mib) % MOD

print(ans)

Submission status: Accepted

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

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

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

# a*a**(p-2) mod p (Fermat's little theorem)
def modInv(x,m):
    return modpow(x,m-2,m)

def nCr(n,r):
    if r > n-r:
        r=n-r
    denom=1
    numer=1
    for i in range(r):
        denom=(n-i)*denom%MOD
        numer=(i+1)*numer%MOD
    return modInv(numer, MOD)*denom%MOD

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

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
def modpow(x,y,p):
  if y==1:
    return x%p
  if y%2==1:
    return x*modpow(x,y-1,p)
  t=modpow(x,y/2,p)
  return (t*t)%p
def modfc(x,y,p):
  f=1
  for i in range(x,y+1):
    f=f%p*i%p
  return f%p
A=modfc(n-a+1,n,10**9+7)*modpow(modfc(1,a,10**9+7),10**9+5,10**9+7)
B=modfc(n-b+1,n,10**9+7)*modpow(modfc(1,b,10**9+7),10**9+5,10**9+7)
print((modpow(2,n,10**9+7)-1-A-B)%(10**9+7))

Submission status: Accepted

Solution code:
import math


mod=10**9+7

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

n,a,b=map(int,raw_input().split())
p=pow(2,n,mod)
p=(p-1+mod)%mod
p=(p-ncr(n,a)+mod)%mod
p=(p-ncr(n,b)+mod)%mod
print p

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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


def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


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

Submission status: Accepted

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

M = 10**9+7

def ncr(n, r, mod=M):
    upp, low = 1, 1
    for i in range(r):
        upp = upp * (n-i) % mod
        low = low * (r-i) % mod
    return upp * pow(low, mod-2, mod) % mod

all_p = (pow(2, n, M) - 1) % M

print((all_p - ncr(n, a, M) - ncr(n, b, M)) % M)

Submission status: Accepted

Solution code:
from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

MOD = 10**9 + 7

n, a, b = LI()

def combination(r):
    numerator = reduce(lambda x, y: x * y % MOD, [n - r + i + 1 for i in range(r)])
    denominator = reduce(lambda x, y: x * y % MOD, [i + 1 for i in range(r)])

    return numerator * pow(denominator, MOD-2, MOD) % MOD

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

print(ans % MOD)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def comb(n, k, MOD):
    if n < k or n < 0 or k < 0:
        return 0
    if k == 0:
        return 1
    iinv = [1] * (k + 1)
    ans = n
    for i in range(2, k + 1):
        iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
        ans *= (n + 1 - i) * iinv[i] % MOD
        ans %= MOD
    return ans
n, a, b = map(int, input().split())
ans = pow(2,n,MOD)
print(((ans-comb(n,a,MOD))%MOD-comb(n,b,MOD))%MOD-1)

Submission status: Accepted

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

mod = 10**9 + 7

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

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

ans %= mod

print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
from math import factorial 
n,a,b=map(int,input().split())
mod=10**9+7
def comb(n,r,mod):
  r=min(r,n-r)
  x=1
  y=1
  
  for i in range(r):
    x = x* (n-i) % mod
    y = y* (1+i) % mod
  y=pow(y,mod-2,mod)

  return(x*y%mod)

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

print(int(ans % (10**9+7)))

Submission status: Accepted

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

def choose(n, k):
  x, y = 1, 1
  for i in range(k):
    x = x * (n-i) % MAX_INT
    y = y * (k-i) % MAX_INT

  return ( x * pow(y, MAX_INT-2, MAX_INT) ) % MAX_INT

print( (pow(2, N, MAX_INT) - 1 - choose(N, A) - choose(N, B)) % MAX_INT)

Submission status: Accepted

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

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

ans = (pow(2, N, MOD)-1-comb(N, a)-comb(N, b))%MOD
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
##################################
# University of Wisconsin-Madison
# Author: Yaqi Zhang
##################################

# standard library
import sys

def cmb(n, r, mod):
    r = min(r, n - r)
    x, y = 1, 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


def main():
    import math
    n, a, b = map(int, input().split())
    MOD = int(1e9 + 7)
    ans = pow(2, n, MOD) - 1
    ans = ans - cmb(n, a, MOD) - cmb(n, b, MOD)
    while ans < 0:
        ans += MOD
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def cmb(n, k, p):
    x, y = 1, 1
    for i in range(k):
        x = x * (n-i) % p
        y = y * (k-i) % p
    return x * pow(y, p-2, p) % p
def main():
    n, a, b = map(int, input().split())
    p = 10 ** 9 + 7
    ans = pow(2, n, p) - 1
    ans -= cmb(n, a, p) + cmb(n, b, p)
    print(ans%p)
if __name__ == "__main__":
    main()

Submission status: Accepted

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


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

comb_a = comb(n,a,mod)
comb_b = comb(n,b,mod)

print((sum_comb - comb_a - comb_b)%mod)

Submission status: Accepted

Solution code:
def pow_mod(n, k, m):
    r = 1
    while k:
        if k & 1:
            r = (r * n) % m
        n = (n * n) % m
        k >>= 1
    return r

def comb(n, r):
    numerator, denominator = 1, 1
    for i in range(n - (r - 1), n + 1):
        numerator = (numerator * i) % (10**9 + 7)
    for i in range(1, r + 1):
        denominator = (denominator * i) % (10**9 + 7)
    inv = pow(denominator, 10**9 + 7 - 2, 10**9 + 7)
    return (numerator * inv) % (10**9 + 7)

def mod_minus(a, b, m):
    if a < b:
        return a + m - b
    else:
        return a - b

n, a, b = map(int, input().split())
count = pow_mod(2, n, 10**9 + 7) - 1
count = mod_minus(count, comb(n, a), 10**9 + 7)
count = mod_minus(count, comb(n, b), 10**9 + 7)
print(count)

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

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

#繰り返し2乗法
def  mod_pow(a:int, b:int, mod:int)->int:
    if b % 2 == 0:
        return (mod_pow(a, b//2, mod) ** 2) % mod
    elif b == 1:
        return a % mod
    else:
        return ((mod_pow(a, b//2, mod) ** 2) * a) % mod

#逆元を求める関数
def mod_inverse(mod:int, b:int)->int:
    return mod_pow(b, mod-2, mod)

#aCbをmodで割った余りを求める関数(bが小さい)
def nCr_mod(n:int, r:int, mod:int)->int:
    num, den = 1, 1 #numerator, denominator

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

    return (num * mod_inverse(mod, den)) % mod
    
ans = (mod_pow(2, n, mod) - 1 - nCr_mod(n, a, mod) - nCr_mod(n, b, mod)) % mod
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

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

#繰り返し2乗法
def  mod_pow(a:int, b:int, mod:int)->int:
    if b % 2 == 0:
        return (mod_pow(a, b//2, mod) ** 2) % mod
    elif b == 1:
        return a % mod
    else:
        return ((mod_pow(a, b//2, mod) ** 2) * a) % mod

#逆元を求める関数
def mod_inverse(mod:int, b:int)->int:
    return mod_pow(b, mod-2, mod)

#aCbをmodで割った余りを求める関数(bが小さい)
def nCr_mod(n:int, r:int, mod:int)->int:
    num, den = 1, 1 #numerator, denominator

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

    return (num * mod_inverse(mod, den)) % mod

""""
print(mod_pow(2,n, mod))
print(nCr_mod(n, a, mod))
print(nCr_mod(n, b, mod))
"""

ans = (mod_pow(2, n, mod) - 1 - nCr_mod(n, a, mod) - nCr_mod(n, b, mod)) % mod
print(ans)

Submission status: Accepted

Solution code:
def nCr(n,r):
    num = den = 1

    for i in range(r):
        num = (num*(n-i)) % MOD #n*(n-1)*...*(n-r)
        den = (den*(i+1)) % MOD #1*2*...*r
    
    return (num * pow(den, MOD-2, MOD)) % MOD
    #フェルマーの小定理を使うことで1/denを作っている
    #最終的に(n*...*(n-r))/(1*...*r)

MOD = 10**9 + 7
n, a, b = map(int, input().split())
x = pow(2, n, MOD)

print((x - nCr(n,a) - nCr(n,b) -1 )% MOD)

Submission status: Accepted

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

MOD = 1000000007  # type: int


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

def mod_range(mod, start, stop=None, step=1):    
    if stop == None:
        stop = start
        start = 0
    return map(lambda i: i % mod, range(start, stop, step))

def mod_inv(mod, n):
    '''
    >>> mod_inv(3, 2)
    2
    >>> mod_inv(1000000007, 2)
    500000004
    '''
    return pow(n, mod-2, mod)

def mod_permutation(mod, n, r):
    '''
    >>> mod_permutation(1000000007, 10, 2)
    90
    >>> mod_permutation(7, 10, 2)
    6
    '''
    m = 1
    for i in mod_range(mod, n-r+1, n+1):
        m = (m * i) % mod
    return m

def mod_factorial(mod, n):
    '''
    >>> mod_factorial(1000000007, 10)
    3628800
    >>> mod_factorial(7, 6)
    6
    '''
    return mod_permutation(mod, n, n)

def mod_combination(mod, n, r):
    '''
    >>> mod_combination(1000000007, 10, 2)
    45
    >>> mod_combination(7, 10, 2)
    3
    '''
    return mod_permutation(mod, n, r) * mod_inv(mod, mod_factorial(mod, r)) % 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
    print(solve(n, a, b))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def powl(x, n, l):#繰り返し2乗法 O(log n)
    ans = 1
    while n > 0:
        if bin(n & 1) == bin(1):
            ans = ans*x
        x = (x*x)%l
        n = n >> 1 #ビットシフト
    return ans

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

out=powl(2,n,pow(10,9)+7)-1
X,Y=1,1
for i in range(a):
    X=(X*(i+1))%(pow(10,9)+7)
    Y=(Y*(n-i))%(pow(10,9)+7)
out-=Y*powl(X,pow(10,9)+5,pow(10,9)+7)

for i in range(a,b):
    X=(X*(i+1))%(pow(10,9)+7)
    Y=(Y*(n-i))%(pow(10,9)+7)
out-=Y*powl(X,pow(10,9)+5,pow(10,9)+7)

print(out%(pow(10,9)+7))

Submission status: Accepted

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

Q=pow(2,N,P)

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

def makeinv(length,p):
    L=[0,1]
    for i in range(2,length+1):
        x=p-((L[p%i]*(p//i))%p)
        L.append(x)
    return L

def comb(n,k,p):
    if k==0:
        return 1
    else:
        ans=fac(n,k,p)
        inv=makeinv(k,p)
        for i in range(1,k+1):
            ans=(ans*inv[i])%p
        return ans

R=comb(N,A,P)
S=comb(N,B,P)

print((Q-1-R-S)%P)

Submission status: Accepted

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

def fast_nCk(n, k, mod=MOD):
    upper = 1
    for i in range(n - k + 1, n + 1):
        upper = upper * i % mod
    below = 1
    for i in range(1, k + 1):
        below = below * i % mod
    
    ans = upper * pow(below, mod - 2, mod) % mod
    ans %= mod
    return ans

# all
total = pow(2, N, MOD) - 1

# remove a (a / b mod MOD) and 
ans1 = fast_nCk(N, a, MOD)
ans2 = fast_nCk(N, b, MOD)
ans = (total - ans1 - ans2) % MOD
print(ans)

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
# D
#入力
n,a,b=map(int,input().split())

#諸関数
def pront(X):
    #デバッグ用プリント
    #環境変数としてdebugを確保して、それが1なら内容を出力
    if debug==0:
        print(X)

#デバッグ用
debug=1#0:本番,1:デバッグ中

#処理
#定数
base=(10**9)+7

#関数
    #10*9+7で割ったあまりを返し続ける
def add(a,b):#a+b
    return(((a%base)+(b%base))%base)
def sub(a,b):#a-b
    return (((a%base)-(b%base))%base)
def multi(a,b):#a*b
    return(((a%base)*(b%base))%base)
def exp(a,b):#a**b
    x=1
    c=a
    d=b
    while d!=0:
        if d%2==1:
            x=multi(x,c)
        c=(c**2)%base
        d=d//2
    return x

#割り算はフェルマーの小定理に基づいて考える
def div(a,b):#a/b
    return(multi(a,exp(b,base-2)))

    #その他演算
def fact(m,n):#m~nの積(m<n)
    x=1
    for i in range(m,n+1):
        x=multi(x,i)
    return x
def comb(n,r):
    return div(fact(n-r+1,n),fact(1,r))
#処理
Z=sub(sub(sub(exp(2,n),comb(n,a)),comb(n,b)),1)
print(Z)

Submission status: Accepted

Solution code:
mod = 10**9+7 
n, a, b = map(int, input().split())
whole = pow(2, n, mod)-1 # 2^n-1(mod p)を計算。
# nCaの計算
comb1=1
for i in range(n-a+1,n+1): # n*(n-1)*(n-2)*...*(n-a+1)(mod p)を計算
  comb1 *= i
  comb1 %= mod
for i in range(1,a+1): # 1/a!(mod p)を計算 フェルマーの小定理:1/a = a^p-2(mod p)を利用
  comb1 *= pow(i,mod-2,mod)
  comb1 %= mod
comb2=1
for i in range(n-b+1,n+1): # n*(n-1)*(n-2)*...*(n-b+1)(mod p)を計算
  comb2 *= i
  comb2 %= mod
for i in range(1,b+1):
  comb2 *= pow(i,mod-2,mod)
  comb2 %= mod
whole -= (comb1+comb2)
whole %= mod
print(whole)

Submission status: Accepted

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

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

A = fast_nCr(n, a)
B = fast_nCr(n, b)
ans = (total - A - B) % mod
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
# int(input()) # 入力が1つ
n, a, b = map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字

mod = 10 ** 9 + 7
def fast_nCk(n, k, mod):
    upper = 1
    for i in range(n - k + 1, n + 1):
        upper = upper * i % mod
    below = 1
    for i in range(1, k + 1):
        below = below * i % mod
    
    ans = upper * pow(below, mod - 2, mod) % mod
    ans %= mod
    return ans

A = fast_nCk(n, a, mod)
B = fast_nCk(n, b, mod)
total = (pow(2, n, mod) - 1) % mod
ans = (total - A - B) % mod
print(ans)

Submission status: Accepted

Solution code:
sel='D'
if sel=='D':
    def fact(n,mod):
        ret=1
        for i in range(2,n+1):
            ret=(ret*i)%mod
        return ret

    N,A,B=map(int,input().split())
    MOD=10**9+7
    ANS=(pow(2,N,MOD)-1)%MOD # 全通り
    
    def pCq(p,q,mod):
        pCq=1
        for i in range(q):
            pCq*=p-i
            pCq=pCq%mod
        den=fact(q,mod)
        inv=pow(den,mod-2,mod)
        pCq=(pCq*inv)%mod
        return pCq
    
    ANS-=pCq(N,A,MOD)+pCq(N,B,MOD)
    ANS=ANS%MOD
    print(ANS)

Submission status: Accepted

Solution code:
def cumprod(start, stop=None, mod=None):
    res = 1
    for i in range(start, stop):
        if mod:
            res *= i % mod
            res %= mod
        else:
            res *= i
    return res


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

mod = 10**9+7
res = pow(2, n, mod) - 1
comb_a = cumprod(n-a+1, n+1, mod) * pow(cumprod(1, a+1, mod), mod-2, mod) % mod
comb_b = cumprod(n-b+1, n+1, mod) * pow(cumprod(1, b+1, mod), mod-2, mod) % mod
res -= comb_a + comb_b
while res < 0:
    res += mod

print(res)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def mul(a, b):
    return ((a % P) * (b % P)) % P

def div(x, y):
    return mul(x, pow(y, P-2, P))

def comb(n, r):
    x = 1
    for i in range(n, n - r, -1):
        x = (x * i) % P
        
    y = 1
    for i in range(1, r+1):
        y = (y * i) % P
    return div(x, y)
  
n, a, b = map(int, input().split())
P = 10 ** 9 + 7
res = pow(2, n, P) - 1 - comb(n, a) - comb(n, b)
print(res % P)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# D
'''
4 1 3
'''

import math
DIVISOR = 10**9 + 7


def comb(n, r):
    res1 = 1
    # 分子
    for i in range(r):
        res1 = (res1 * (n-i)) % DIVISOR

    # 分母
    res2 = 1
    for i in range(r):
        res2 = (res2 * (i+1)) % DIVISOR
    res2 = power_mod(res2, DIVISOR - 2, DIVISOR)
    return (res1 * res2) % DIVISOR


def power_mod(n, k, m):
    if k == 0:
        return 1
    elif k % 2 == 1:
        return power_mod(n, k-1, m) * (n % m) % m
    elif k % 2 == 0:
        temp = power_mod(n, k/2, m)
        return (temp % m) * (temp % m) % m


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

S = 2 * power_mod(2, n-1, DIVISOR)
S = (S - 1) % DIVISOR
# print(S)

# print(comb(n, a))
# print(comb(n, b))

S = S - comb(n, a) - comb(n, b)

print(S % DIVISOR)

Submission status: Accepted

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

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

def main():
    ans = pow(2, n, MOD) - 1
    ans -= comb(n=n, r=a, mod=MOD)
    ans -= comb(n=n, r=b, mod=MOD)
    ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def power_func(a, n, mod):
  bi = bin(n)[2:]
  res = 1
  for i in range(len(bi)):
    res = (res * res) % mod
    if bi[i] == "1":
      res = (res * a) % mod
  return res

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

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

def main():
    ans = power_func(a=2, n=n, mod=MOD) - 1
    ans -= combination(n=n, r=a, mod=MOD)
    ans -= combination(n=n, r=b, mod=MOD)
    ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

p = pow(2,a,MOD)
q = comb(a,b)
r = comb(a,c)
ans = (p-q-r-1)%MOD
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
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


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

Submission status: Accepted

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

Q=pow(2,N,P)

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

def makeinv(length,p):
    L=[0,1]
    for i in range(2,length+1):
        x=p-((L[p%i]*(p//i))%p)
        L.append(x)
    return L

def comb(n,k,p):
    ans=fac(n,k,p)
    inv=makeinv(k,p)
    for i in range(1,k+1):
        ans=(ans*inv[i])%p
    return ans

R=comb(N,A,P)
S=comb(N,B,P)

print((Q-1-R-S)%P)

Submission status: Accepted

Solution code:
MOD=10**9+7
N,a,b=[int(s) for s in input().split()]

MAX = N
inv = [0, 1]
for i in range(2, b+1):
  inv.append(MOD - inv[MOD % i] * (MOD // i) % MOD)

r=1
for i in range(a):
  r=r*(N-i)%MOD
  r=r*inv[i+1]%MOD

s=r
for i in range(a,b):
  r=r*(N-i)%MOD
  r=r*inv[i+1]%MOD

base=2
n=1
pow=[1,base]
while n<MAX:
  pow.append((pow[-1]**2)%MOD)
  n*=2
  
n=N
i=1
p=1
while n>0: 
  if n%2==1:
    p=p*pow[i]%MOD
  n//=2
  i+=1

print((p-1-r-s)%MOD)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7


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

def nCk(N, K):
    ans = 1
    for i in range(1, K + 1):
        ans *= (N - i + 1)
        ans %= mod
        ans *= inv[i]
        ans %= mod
    return ans


inv = [0 for i in range(10 ** 5 * 2 + 1)]
inv[1] = 1
for i in range(2, len(inv)):
    inv[i] = modpow(i, mod - 2)

n, a, b = map(int, input().split(" "))
ans = (modpow(2, n) + mod - 1) % mod
ans -= nCk(n, a) + nCk(n, b)
print(ans % mod)

Submission status: Accepted

Solution code:
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


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

Submission status: Accepted

Solution code:
# 乗法のmod逆元 (mod-2乗)
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
 
# nCr mod m
# modinvが必要
# rがn/2に近いと非常に重くなる
def comb(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
  
def binary(n):
    return bin(n)[2:]

# バイナリ法
def pow_by_binary(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
  
n,a,b = [int(i) for i in input().split()]
mod = 10**9+7
ans = pow_by_binary(2,n,mod)-1-comb(n,a,mod)-comb(n,b,mod)
if ans < 0:
  ans += mod
print(ans%mod)

Submission status: Accepted

Solution code:
mod = 1000000007;

def bin(b, m):
    a = b;
    n = m;
    res = 1;
    while n > 0:
        if n % 2 == 1:
            res = (res * a) % mod;
        a = (a * a) % mod;
        n //= 2;
    return res;

def fact(x):
    res = 1;
    for i in range(1, x + 1):
        res = (res * i) % mod;
    return res;

def inv(x):
    return bin(x, mod - 2);

def cnk(n, k):
    res = 1;
    for i in range(n - k + 1, n + 1):
        res = (res * i) % mod;
    return (res * inv(fact(k))) % mod;

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

ans = (bin(2, n) - 1 - cnk(n, a) - cnk(n, b) + 3 * mod) % mod;
#print(bin(2, n), cnk(n, a), cnk(n, b));
print(ans);

Submission status: Accepted

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