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


def neko(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((pow(2, n, mod) - 1 - neko(n, a) - neko(n, b)) % mod)

Submission status: Accepted

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


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


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

Submission status: Accepted

Solution code:
mod = 10**9+7
 
def comb(n,m,p=10**9+7):
    if n < m : return 0
    if n < 0 or m < 0:return 0
    m = min(m, n-m)
    top = bot = 1
    for i in range(m):
        top = top*(n-i) % p
        bot = bot*(i+1) % p
    bot = pow(bot, p-2, p)
    return top*bot % p
 
n,a,b = map(int, input().split())
ans = pow(2, n, mod)-1 - comb(n,a) - comb(n, b)
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#156D
p=7+10**9
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)
n,a,b=map(int,input().split())
s=-1+pow(2,n,p)-comb(n,a)-comb(n,b)
print(s%p)

Submission status: Accepted

Solution code:
N, a, b = map(int,input().split())
p = pow(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)
print((pow(2,N, p) - 1 - comb(N,a) - comb(N,b)) % p)

Submission status: Accepted

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

mod = 10 ** 9 + 7


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


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

Submission status: Accepted

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

m = 10 ** 9 + 7

def comb(n, r, m):
  ans = 1
  for i in range(r):
    #ans = ans * (n-i) * pow(i+1, m-2, m) % m
    ans *= (n-i) * pow(i+1, m-2, m) % m
    ans %= m
    # *= で書いてしまうとans自体にmod計算されないので
    # 大きな数が発生して遅くなる．
    # ans %= mを追加すれば早い？
    
  return ans
  
print((pow(2,n,m)-1-comb(n,a,m)-comb(n,b,m))%m)

Submission status: Accepted

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

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


a0 = 1
a1 = 1 
for i in range(1, a+1):
  a0 = a0 * (n - i + 1) % 1000000007
  a1 = a1 * i % 1000000007

b0 = 1
b1 = 1 
for i in range(1, b+1):
  b0 = b0 * (n - i + 1) % 1000000007
  b1 = b1 * i % 1000000007

A = (pow(2, n) - 1 - a0 * pow(a1, 1000000005) - b0 * pow(b1, 1000000005)) % 1000000007

print(A)

Submission status: Accepted

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


def pow(m, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return (pow(m, int(n / 2)) ** 2) % mod
    elif n % 2 == 1:
        return (pow(m, int((n - 1) * 0.5)) ** 2 * m) % mod


def conb(n, a):
    mod1 = 1
    mod2 = 1
    for i in range(a):
        mod1 *= n - i
        mod1 %= mod
        mod2 *= i + 1
        mod2 %= mod
    mod2 = pow(mod2, mod - 2)
    return (mod1 * mod2) % mod


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


ans = 1
noa = 1
nob = 1
mod = 1000000007
ans = pow(2, n) - 1 - conb(n, a) - conb(n, b)
ans %= mod
print(ans)

Submission status: Accepted

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

def comb(r):
    bunshi = 1
    # iは2からnの範囲を動く
    for i in range(n - r + 1, n + 1):
        bunshi = bunshi * i % mod
    bunbo = 1
    for i in range(1, r + 1):
        bunbo = bunbo * i % mod
    return bunshi * pow(bunbo, mod - 2, mod) % mod


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

Submission status: Accepted

Solution code:
mod = (10**9)+7
def modpow(x, n):
  ans = 1
  mod = (10**9)+7
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = ans*x
      ans %= mod
    x = x*x
    x %= mod
    n = n >> 1 #ビットシフト
  return ans


def nCr(n,r):
    mod = (10**9)+7
    r = min(n,r)
    bunsi = bunbo = 1
    for i in range(1,r+1):
      bunsi = (bunsi * (n+1-i) )% mod
      bunbo = bunbo * i % mod
    ans = (bunsi * pow(bunbo,mod-2,mod)) % mod
    return ans

n,a,b = map(int,input().split())
print((modpow(2,n)- 1 - nCr(n,a) - nCr(n,b) )% mod)

Submission status: Accepted

Solution code:
import numpy as np
mod = (10**9)+7
def modpow(x, n):
  ans = 1
  mod = (10**9)+7
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = ans*x
      ans %= mod
    x = x*x
    x %= mod
    n = n >> 1 #ビットシフト
  return ans


def nCr(n,r):
    mod = (10**9)+7
    r = min(n,r)
    bunsi = bunbo = 1
    for i in range(1,r+1):
      bunsi = (bunsi * (n+1-i) )% mod
      bunbo = bunbo * i % mod
    ans = (bunsi * pow(bunbo,mod-2,mod)) % mod
    return ans

n,a,b = map(int,input().split())
print((modpow(2,n)- 1 - nCr(n,a) - nCr(n,b) )% mod)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

mod=10**9+7 
def nCr(n, r, mod=10**9+7):#mod=10**9+7
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

def modpow(a,n,mod=10**9+7):
    res=1
    while(n>0):
        if (n&1):
            res = res*a%mod
        a = a*a%mod
        n>>=1
    return res


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

Submission status: Accepted

Solution code:
import math

def cmb(N,X,mod):
	P=1
	Q=1
	for i in range (X):
		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())
mod=pow(10,9)+7

ans=0
ans=(pow(2,N,mod)-1)

tmp_A=cmb(N,A,mod)
tmp_B=cmb(N,B,mod)
#print(ans,tmp_A,tmp_B)
ans=ans-tmp_A-tmp_B
print(ans%mod)

Submission status: Accepted

Solution code:
import math

def cmb(N,X,mod):
	P=1
	Q=1
	for i in range (X):
		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())
mod=pow(10,9)+7

ans=0
ans=(pow(2,N,mod)-1)

tmp_A=cmb(N,min(A,N-A),mod)
tmp_B=cmb(N,min(B,N-B),mod)
#print(ans,tmp_A,tmp_B)
ans=ans-tmp_A-tmp_B
print(ans%mod)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def MOD_pow(a, n):
    res = 1
    while n > 0:
        if (n & 1):
            res = res * a % MOD
        a = a * a % MOD
        n = n // 2
    return res
def MOD_perm(n, r):
    rtn = 1
    for _ in range(r):
        rtn *= n
        rtn %= MOD
        n -= 1
    return rtn
def MOD_inv(a):
    b = MOD
    u = 1
    v = 0
    while b > 0:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u = u % MOD
    if u < 0:
        u += MOD
    return u
def cmb(n, r):
    return MOD_perm(n, r) * MOD_inv(MOD_perm(r, r)) % MOD

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
MOD = 10 ** 9 + 7
sys.setrecursionlimit(MOD)


def comb(n, k):
    N, K = 1, 1
    for i in range(k):
        N = N * (n - i) % MOD
        K = K * (1 + i) % MOD
    return N * pow_mod(K, MOD - 2) % MOD


def pow_mod(a, b):
    if b == 0:
        return 1
    elif b % 2 == 0:
        d = pow_mod(a, b // 2)
        return d ** 2 % MOD
    else:
        return a * pow_mod(a, b - 1) % MOD


n, a, b = map(int, input().split())
ans = (MOD + pow_mod(2, n) - 1 - comb(n, a) - comb(n, b)) % MOD
print(ans)

Submission status: Accepted

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

def getComb(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    # n!/(n-k)!
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    # k!
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    # n!/((n-k)!*k!)
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

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

MOD = 10**9 +7

# nCk (k = 1,...,a-1,a+1,...,b-1,b+1,...,n)

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

Submission status: Accepted

Solution code:
N,a,b = [int(i) for i in input().split()]
mod = 10**9+7
def power(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
def fact(m, n):
    val = 1
    for i in range(m, n+1):
        val = val*i % mod
    return val
    
def cmb1(N, r):
    A = fact(N-r+1, N)%mod
    B = fact(1, r)%mod
    return A, B, (A*power(B, mod-2))%mod
def cmb2(a, b, A, B):
    A = fact(N-a+1, N-b)*A%mod
    B = fact(b+1, a)*B%mod
    return (A*power(B, mod-2))%mod
if(a>N//2):
    a = N-a
if(b>N//2):
    b = N-b
tmp = max(a,b)
b = min(a,b)
a = tmp
A, B, K1 = cmb1(N, b)
K2 = cmb2(a, b, A, B)
print((power(2, N)-1-K1-K2)%mod)

Submission status: Accepted

Solution code:
import numpy as np
N,a,b = np.array(input().split()).astype(int)
mod = 10**9+7
def power(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
def fact(m, n):
    val = 1
    for i in range(m, n+1):
        val = val*i % mod
    return val
    
def cmb1(N, r):
    A = fact(N-r+1, N)%mod
    B = fact(1, r)%mod
    return A, B, (A*power(B, mod-2))%mod
def cmb2(a, b, A, B):
    A = fact(N-a+1, N-b)*A%mod
    B = fact(b+1, a)*B%mod
    return (A*power(B, mod-2))%mod
if(a>N//2):
    a = N-a
if(b>N//2):
    b = N-b
tmp = max(a,b)
b = min(a,b)
a = tmp
A, B, K1 = cmb1(N, b)
K2 = cmb2(a, b, A, B)
print((power(2, N)-1-K1-K2)%mod)

Submission status: Accepted

Solution code:
def dv(x, y, mod):
    # x / y = x * (y ** (mod - 2))
    return x * pow(y, mod - 2, mod) % mod

def comb(n, r, mod):
    # p / q = p * (q ** (mod - 2))
    p, q = 1, 1
    if n < r or n < 0 or r < 0: return 0
    for i in range(r):
        p = p * (n - i) % mod
        q = q * (i + 1) % mod
    return dv(p, q, mod)

mod = 1000000007
n, a, b = map(int, input().split())
# pow(a, b, c) = (a ** b) % c
ans = pow(2, n, mod) - 1
if 0 <= n: ans -= comb(n, a, mod)
if 0 <= n: ans -= comb(n, b, mod)
print(ans % mod)

Submission status: Accepted

Solution code:
mod = 1000000007

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

def dv(x, y):
    return x * pow(y, mod - 2, mod) % mod

def comb(n, r):
    p, q = 1, 1
    if n < r or n < 0 or r < 0: return 0
    for i in range(r):
        p = p * (n - i) % mod
        q = q * (i + 1) % mod
    return dv(p, q)

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

Submission status: Accepted

Solution code:
def comb_mod(n,m,mod):
  p = q = 1
  for i in range(m):
    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())
mod = 10**9 +7
print( (pow(2,n,mod)-1 -comb_mod(n,a,mod) -comb_mod(n,b,mod) ) % mod )

Submission status: Accepted

Solution code:
def nCr(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


mod = 10 ** 9 + 7  # 出力の制限

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

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

print(ans%mod)

Submission status: Accepted

Solution code:
MOD = 1000000007

def fastpow(a, n):
    x = a
    ans = 1
    while n:
        if n & 1:
            ans = (ans*x)%MOD
        n>>=1
        x = (x*x)%MOD;
    return ans

def inv(a):
    return fastpow(a, MOD-2)

def comb(n,r):
    ret = 1
    for i in range(r):
        ret = (ret*(n-i))%MOD
        ret = (ret*inv(i+1))%MOD
    return ret

n,a,b = map(int,input().split()) 
ans = fastpow(2,n)-1-comb(n,a)-comb(n,b)
while ans < 0:
    ans += MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
input = sys.stdin.buffer.readline
def inputS(): return input().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

def nCr(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
  
MOD = 10**9+7  
N, A, B = map(int, input().split())

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

Submission status: Accepted

Solution code:
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 main():
    import sys
    input = sys.stdin.readline

    mod = 1000000007
    nmax = 2 * 10 ** 5 + 10  # change here
    fac = [0] * nmax
    finv = [0] * nmax
    inv = [0] * nmax
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2, nmax):
        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 comb(n, r):
        ret = finv[r]
        for i in range(r):
            ret = (ret * (n-i))%mod
        return ret
    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:
MOD = 10**9 + 7
MAX = int(2e5)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD


def combi(n, x):
    ret = 1
    for i in range(x):
        ret = ret * (n-i) % MOD
    ret = ret * INV[x] % MOD
    return ret


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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = pow(2, n, mod) - 1
an = 1
for i in range(n - a + 1, n + 1):
    an *= i
    an %= mod
for i in range(1, a + 1):
    an *= pow(i, mod - 2, mod)
    an %= mod
bn = 1
for i in range(n - b + 1, n + 1):
    bn *= i
    bn %= mod
for i in range(1, b + 1):
    bn *= pow(i, mod - 2, mod)
    bn %= mod

ans -= (an + bn)
print(ans % mod)

Submission status: Accepted

Solution code:
x=input().split()
n=int(x[0])
a=int(x[1])
b=int(x[2])

def fast_expo(b,n,p):
    if n==0:
        return 1
    if n==1:
        return b%p
    if n%2==0:
        return fast_expo(((b%p)*(b%p))%p,n//2,p)
    else:
        return (b*fast_expo(((b%p)*(b%p))%p,n//2,p))%p
def combi(n,k,p):
    X=1
    Y=1
    for i in range(k):
        X=(X*(n-i))%p
        Y=(Y*(k-i))%p
    Z=fast_expo(Y,p-2,p)
    return (X*Z)%p

p=10**9+7
res=fast_expo(2,n,p)
res=(res-1)%p
res=(res-combi(n,a,p))%p
res=(res-combi(n,b,p))%p
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
mod = 10**9+7
def pow(n, p,mod=10**9+7): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def large_conbination(n,k,mod=10**9+7): #needs pow method. return nCk.
    res1 = 1
    for i in range(n,n-k,-1):
        res1*=i
        res1%=mod
    res2 = 1
    for i in range(1,k+1):
        res2*= i
        res2%=mod
    return res1*pow(res2,mod-2)%mod

ans = pow(2,n) -1 

ans -= large_conbination(n,a)
ans -= large_conbination(n,b)

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

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
mod = 10**9+7
def pow(n, p,mod=10**9+7): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def large_conbination(n,k,mod=10**9+7): #needs pow method. return nCk.
    res1 = 1
    for i in range(n,n-k,-1):
        res1*=i
        res1%=mod
    res2 = 1
    for i in range(1,k+1):
        res2*= pow(i,mod-2) #フェルマーの小定理を用いて分母を計算
        res2%=mod
    return res1*res2%mod

ans = pow(2,n) -1 

ans -= large_conbination(n,a)
ans -= large_conbination(n,b)

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

Submission status: Accepted

Solution code:
def comb_mod(n, r, M):
    p = q = 1
    for i in range(r):
        p = p * (n - i) % M
        q = q * (i + 1) % M
    return p * pow(q, M - 2, M) % M


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

res = (pow(2, n, M) - 1 - comb_mod(n, a, M) - comb_mod(n, b, M)) % M
print(res)

Submission status: Accepted

Solution code:
MOD = 10**9+7

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

Sn = pow(2,n,MOD) - 1
a = min(a, n-a)
b = min(b, n-b)
if a > b:
    a,b = b,a
Xa, Xb = 1,1
Ya, Yb = 1,1
for i in range(b):
    if i < a:
        Xa = ( Xa * (n-i) ) % MOD
        Ya = ( Ya * pow((a-i),MOD-2, MOD)) % MOD
    Xb = ( Xb * (n-i) ) % MOD
    Yb = ( Yb * pow((b-i),MOD-2, MOD)) % MOD

ans = Sn - Xa*Ya % MOD - Xb*Yb % MOD
while ans < 0:
    ans += MOD
    
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7

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

Sn = pow(2,n,MOD) - 1
if a > b:
    a,b = b,a
Xa, Xb = 1,1
Ya, Yb = 1,1
for i in range(b):
    if i < a:
        Xa = ( Xa * (n-i) ) % MOD
        Ya = ( Ya * pow((a-i),MOD-2, MOD)) % MOD
    Xb = ( Xb * (n-i) ) % MOD
    Yb = ( Yb * pow((b-i),MOD-2, MOD)) % MOD

ans = Sn - Xa*Ya % MOD - Xb*Yb % MOD
while ans < 0:
    ans += MOD
    
print(ans)

Submission status: Accepted

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

def power(x,n): #x**n(mod)を二分累乗法で求める
    T=[x]
    while 2**(len(T))<n+1: #a**1,a**2.a**4,a**8,...を計算しておく
        T.append(T[-1]**2%mod)
    b=bin(n) #mod-2を2進数表記にする
    ans=1
    for i in range(len(b)-2):
        if int(b[-i-1])==1:
            ans=ans*T[i]%mod
    return ans

#n!とその逆元を求めておく
N=2*10**5+10
g1=[1,1] #n!
g2=[1,1] #n!の逆元
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)

nCa=1
for i in range(a):
    nCa=nCa*(n-i)%mod
nCa=nCa*g2[a]%mod
    
nCb=1
for i in range(b):
    nCb=nCb*(n-i)%mod
nCb=nCb*g2[b]%mod

ans=power(2,n)-1
ans=(ans-nCa)%mod
ans=(ans-nCb)%mod

print(ans)

Submission status: Accepted

Solution code:
def choose(n, k, mod):
  """ nCkを計算 """
  # 分子
  numerator = 1
  for i in range(k):
    numerator *= n - i
    numerator %= mod
  # 分母
  denominator = 1
  for i in range(k):
    denominator *= (i + 1)
    denominator %= mod

  # (分子 / 分母) % mod
  # = (分子 * 分母の逆元) % mod   
  return (numerator * pow(denominator, mod - 2, mod)) % mod


def main():
  MOD = 10 ** 9 + 7
  n, a, b = [int(x) for x in input().split()]

  # "2のn乗"をMODで割ったあまり
  ans = pow(2, n, MOD)
  
  # 1個も選ばない場合
  ans -= 1
  # a個選ぶ場合
  ans -= choose(n, a, MOD)
  # b個選ぶ場合
  ans -= choose(n, b, MOD)
  
  # Pythonの場合、ansが負の値でも特別な考慮は不要
  ans %= MOD

  print(ans)

  
main()

Submission status: Accepted

Solution code:
def comb(n, k, mod):
  r = min(k, n-k)
  p = q = 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())
mod = (10**9+7)
ans = (pow(2, n, mod)-comb(n, a, mod)-comb(n, b, mod)-1)%mod
print(ans)

Submission status: Accepted

Solution code:
LARGE = 10 ** 9 + 7


def solve(n, a, b):

    pow_ab = [1] * (b + 1)
    for i in range(b):
        pow_ab[i + 1] = pow_ab[i] * (i + 1) % LARGE
    pow_ab_inv = [1] * (b + 1)
    pow_ab_inv[-1] = pow(pow_ab[-1], LARGE - 2, LARGE)
    for i in range(b - 1, 0, -1):
        pow_ab_inv[i] = pow_ab_inv[i + 1] * (i + 1) % LARGE

    res_all = pow(2, n, LARGE) - 1
    res_ab = 1
    for i in range(a):
        res_ab *= (n - i)
        res_ab %= LARGE
    res_all -= res_ab * pow_ab_inv[a]
    for i in range(a, b):
        res_ab *= (n - i)
        res_ab %= LARGE
    res_all -= res_ab * pow_ab_inv[b]
    return res_all % LARGE


def main():
    n, a, b = map(int, input().split())
    res = solve(n, a, b)
    print(res)


def test():
    assert solve(4, 1, 3) == 7
    assert solve(1000000000, 141421, 173205) == 34076506


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

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

#output
mod = pow(10, 9) + 7

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def mod_pow(p, q):
    res = 1
    while q:
        if q & 1:
            res = (res * p) % MOD
        p = (p * p) % MOD
        q //= 2
    return res

def inv(p):
    return mod_pow(p, MOD-2)

def mod_comb(p, q):
    a, b = 1, 1
    for i in range(q):
        a = (a * (p-i)) % MOD
        b = (b * (i+1)) % MOD
    return (a * inv(b)) % MOD

def solve(n, a, b):
    res = mod_pow(2, n)
    for x in [0, a, b]:
        res = (res - mod_comb(n, x)) % MOD
    return res

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

Submission status: Accepted

Solution code:
mod = 1000000007

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

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

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

def combination(n,r):
    bumbo = 1
    bunshi = 1
    for i in range(r):
        bumbo = (bumbo*(n-i)) % mod
    for i in range(1,r+1):
        bunshi = (bunshi*i) % mod
    return (div(bumbo, bunshi)) % mod


n, a, b = map(int, input().split())
print((power(2,n)-1-combination(n,a)-combination(n,b)) % mod)

Submission status: Accepted

Solution code:
import math


def fct(n, r, mod=10 ** 9 + 7):
    ans = 1
    for i in range(r):
        ans *= n - i
        ans %= mod
    return ans % mod


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

cmb1 = fct(N, A) * pow(math.factorial(A), MOD - 2, MOD)
cmb2 = fct(N, B) * pow(math.factorial(B), MOD - 2, MOD)
print((pow(2, N, MOD) - 1 - cmb1 - cmb2) % MOD)

Submission status: Accepted

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

mod = 10**9+7

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

def 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

sum = pow(2,n,mod)
case = combination(n,a,mod) + combination(n,b,mod) + 1
ans = sum-case
while ans < 0 :
    ans += mod

print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
#from math import sqrt
#from heapq import heappush, heappop
#from collections import deque
from functools import reduce

#a, b = [int(v) for v in input().split()]


def main():

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

    def pow(n, r):
        if r == 0:
            return 1
        val = pow(n, r // 2)
        val = val * val % mod
        if r % 2 == 1:
            val = val * n % mod
        return val

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

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

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


main()

Submission status: Accepted

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

MOD = 10**9+7

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

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

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

if ans < 0:
    print((ans+MOD)%MOD)
else:
    print(ans%MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
# sys.setrecursionlimit(10000000)
INF = 1<<32
# import numpy as np

MOD = 1000000007  # type: int

def solve(n: int, a: int, b: int):
    def combination_with_mod(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)-combination_with_mod(n, a)-combination_with_mod(n, b)-combination_with_mod(n, 0)

    if ans < 0:
        print((MOD+ans)%MOD)
    else:
        print(ans%MOD)

    return



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:
# -*- coding: utf-8 -*-


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

    # KeyInsight:
    # 全体 - 条件を満たす場合
    # modの世界では割り算の代わりに逆元を使う
    # See:
    # https://www.youtube.com/watch?v=lzAMKPMLdtU&feature=youtu.be
    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)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def combinations_mod(n, k, mod):
    X, Y = 1, 1
    for i in range(1, k+1):
        X = (X * (n-i+1))%mod
    for j in range(1, k+1):
        Y = (Y*j)%mod
    result = X * (pow(Y, mod-2, mod))
    return result%mod

whole_sum -= combinations_mod(n, a, mod)
whole_sum -= combinations_mod(n, b, mod)

print(whole_sum % mod)

Submission status: Accepted

Solution code:
# X/Y mod(10**9+7) == X*(Y**(10**9+7-2)) mod(10**9+7)

MOD = 10**9+7

def mod_prod(l, mod=MOD):
    p = 1
    for x in l:
        p = (p * x) % mod
    return p

n, *ab = list(map(int, input().split()))

m = pow(2, n, MOD) - 1
# print(m)

for k in ab:
    # print(f"k: {k}")
    x = mod_prod(range(n-k+1, n+1))
    y = mod_prod(range(1, k+1))
    z = x * pow(y, MOD-2, MOD)
    # print(z)
    m = (m - z) % MOD

print(m)

Submission status: Accepted

Solution code:
def comb2(n, r):
    if r<0 or r>n:
        return 0
    r=min(r, n-r)
    res=1
    for i in range(r):
        res=res*(n-i)%MOD*pow(i+1, MOD-2, MOD)%MOD
    return res

MOD=10**9+7

N, A, B=map(int, input().split())
ans=pow(2, N, MOD)-comb2(N, A)-comb2(N, B)-1
print(ans%MOD)

Submission status: Accepted

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

MOD = 10**9 + 7

def CombMod(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((pow(2, n, MOD) - 1 - (CombMod(n, a) + CombMod(n, b)))%MOD)