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())
m=10**9+7
def cmb(x,y):
    c=1
    for i in range(1,y+1):
        c=(c*(x-i+1)*pow(i,m-2,m))%m
    return c
print((pow(2,n,m)-1-cmb(n,a)-cmb(n,b))%m)

Submission status: Accepted

Solution code:

n,a,b=map(int,input().split())
#print(n,a,b)
mod=10000*100000+7
def mpow(a,b,m=100000*10000+7):#returns a**b%m
  ret=1
  while b>0:
    if b&1:
      ret=(ret*a)%m
    a=(a*a)%m
    b>>=1
  return ret
def nCr(n,r):#computes nCr
  num=1
  for i in range(n-r+1,n+1):
    num=(num*i)%mod
  den=1
  for i in range(1,r+1):
    den=(den*i)%mod
  den=mpow(den,mod-2)
  return (num*den)%mod
ans=mpow(2,n)-1
if ans<0:
  ans+=mod
ans-=nCr(n,a)
if ans<0:
  ans+=mod
ans-=nCr(n,b)
if ans<0:
  ans+=mod
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()


def inv_mod(a, N):
    """
    ユークリッドの互除法より
    aの逆元 ax = 1 (mod N)を満たすxを返す。
    O(log a)
    """

    def extgcd(a, b):
        """
        Extended Great Common Divisor
        ax + by = gcd(a, b) = dを満たすx, y, dを返す。
        """
        d = fractions.gcd(a, b)
        if b == 0:
            return 1, 0, a
        else:
            q, r = divmod(a, b)
            x, y, d = extgcd(b, r)
            s, t = y, x - q * y
            return s, t, d

    return extgcd(a, N)[0]


def bpm(x, y, N):
    """
     Bisection power method : 二分累乗法
     O(log y)でx^(y) mod N を求める。
    """
    ans = 1
    x %= MOD
    digit = int((math.log(y, 2) // 1 + 1))  # yの２進数表示の桁数
    for i in range(digit):
        if (y >> i) & 1 == 1:
            ans *= x
            ans %= MOD
        x **= 2
        x %= MOD
    return ans


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

nCa = 1
nCb = 1

inv_list = []

for i in range(max(a, b)):
    inv_list.append(inv_mod(i + 1, MOD))

for i in range(a):
    nCa *= inv_list[i]
    nCa %= MOD
    nCa *= n - i
    nCa %= MOD

for i in range(b):
    nCb *= inv_list[i]
    nCb %= MOD
    nCb *= n - i
    nCb %= MOD

print((bpm(2, n, MOD) - 1 - nCa - nCb) % MOD)

Submission status: Accepted

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

Submission status: Accepted

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

def f(x, y, MOD):
  out=1
  for i in range(x, x-y, -1):
    out=out*i%MOD
  return out

p=[0, 1]+[0]*(2*10**5-1)
for i in range(2, 2*10**5+1, 1):
  p[i]=p[i-1]*i%MOD
  
q=[0]*(2*10**5)+[pow(p[-1], MOD-2, MOD)]
for i in range(2*10**5, 0, -1):
  q[i-1]=q[i]*i%MOD

ans=(pow(2, n, MOD)-1-(f(n, a, MOD)*q[a])%MOD-(f(n, b, MOD)*q[b])%MOD)%MOD
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from math import factorial

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

mod = 10**9 + 7

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

def ncr(n, r):
    x = 1
    y = 1
    for i in range(r):
        x *= (n-i)
        y *= (i+1)
        x %= mod
        y %= mod
    return (x * pow(y, 10**9+5)) % mod

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

print(ans if ans >= 0 else ans + mod)

Submission status: Accepted

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


class ModInt:
    def __init__(self, num, mod):
        self.num = num
        self.mod = mod

    def __str__(self):
        return str(self.num)

    def __repr__(self):
        return "ModInt(num: {}, mod: {}".format(self.num, self.mod)

    def __add__(self, other):
        ret = self.num + other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def __sub__(self, other):
        ret = self.num - other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def __mul__(self, other):
        ret = self.num * other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def pow(self, times):
        pw = pow(self.num, times, self.mod)
        return ModInt(pw, self.mod)

    def inverse(self):
        return self.pow(self.mod - 2)

    def __truediv__(self, other):
        num = self * other.inverse()
        return ModInt(num, self.mod)


class CombinationSmall:
    def __init__(self, n, k, mod):
        self.n = n
        self.k = k
        self.mod = mod
        self.fact = [ModInt(1, mod)]
        self.inverse = [ModInt(1, mod)]
        for i in range(1, k + 1):
            self.fact.append(self.fact[-1] * ModInt(n - i + 1, mod))
            self.inverse.append(self.inverse[-1] * ModInt(i, mod).inverse())

    def comb(self, k):
        if k > self.k:
            return ModInt(0, self.mod)

        return self.fact[k] * self.inverse[k]


comb = CombinationSmall(n, min(n, 2 * 10 ** 5), mod)

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

def factorial(n,m):
    #0〜(2 * 10 ^ 5)!のリスト
    f = [1,1]
    for i in range(2,n+1):
        f.append(f[-1]*i % m)
    #modにおける逆元のリスト
    g = [1]
    for i in range(n):
        g.append(pow(f[i+1],m-2,m))
    return f,g

f, g = factorial(2*10**5+1,mod)

div_a = g[a]
"""
for i in range(n,n-a-1,-1):
    div_a *= i
    div_a %= mod
"""
for i in range(1,a+1):
    div_a *= n - i + 1
    div_a %= mod


div_b = g[b]
for i in range(1,b+1):
    div_b *= n - i + 1
    div_b %= mod


mx = pow(2, n, mod)
mx += mod*3
print((mx - 1 - div_a - div_b)%mod)

Submission status: Accepted

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

def factorial(n,m):
    #0〜(2 * 10 ^ 5)!のリスト
    f = [1,1]
    for i in range(2,n+1):
        f.append(f[-1]*i % m)
    #modにおける逆元のリスト
    g = [1]
    for i in range(n):
        g.append(pow(f[i+1],m-2,m))
    return f,g

f, g = factorial(2*10**5+1,mod)

div_a = g[a]
for i in range(1,a+1):
    div_a *= n - i + 1
    div_a %= mod


div_b = g[b]
for i in range(1,b+1):
    div_b *= n - i + 1
    div_b %= mod


mx = pow(2, n, mod)
mx += mod*3
print((mx - 1 - div_a - div_b)%mod)

Submission status: Accepted

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

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

nca=comb(n,a,mod)
ncb=comb(n,b,mod)

ans=pow(2,n,mod)
ans=(ans-((nca+ncb)%mod+1))%mod
print(ans)

Submission status: Accepted

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

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

nca=comb(n,a,mod)
ncb=comb(n,b,mod)

ans=pow(2,n,mod)
ans=(ans-((nca+ncb)%mod+1))%mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def solve():

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

    # 繰り返し二乗法
    def modPow(a, n, mod):
        if n == 1:
            return a
        elif n%2 == 1:
            return a * modPow(a, n-1, mod) % mod
        else:
            t = modPow(a, n/2, mod)
            return (t * t) % mod

    def combination(n, a, mod):
        x = 1
        y = 1
        for i in range(a):
            x = x * (n-i)%mod
            y = y * (a-i)%mod

            #x *= (n-i)
            #x %=mod
            #y *= (a-i)
            #y %=mod
        return x * pow(y, mod-2, mod)%mod

    #全ての選び方
    sigma_nCi = pow(2, n, mod)
    # nCa, nCb
    nCa = combination(n, a, mod)
    nCb = combination(n, b, mod)

    ans = sigma_nCi - 1 - nCa - nCb

    #print(Sigma_nCi, nCa, nCb)
    print(ans%mod)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
mo = 1000000007
A_val = 1
for i in range(A):
    A_val = ((A_val * (N - i) * pow(i+1, mo-2, mo))) % mo
B_val = 1
for i in range(B):
    B_val = ((B_val * (N - i) * pow(i+1, mo-2, mo))) % mo
    
ans = (pow(2, N, mo) - 1 - A_val - B_val) % mo
print(ans)

Submission status: Accepted

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

comb = [n] * (b + 1)
inv = [1] * (b + 1)
for i in range(2, b + 1):
  inv[i] = -inv[mod % i] * (mod // i) % mod
  comb[i] = comb[i-1] * (n - i + 1) * inv[i] % mod

count = pow(2, n, mod) - 1 - comb[a] - comb[b]
print(count % mod)

Submission status: Accepted

Solution code:
import math

# xのn乗
def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

# nCkの導出
def comb(n,k):
    nCk = 1
    # X
    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= mod

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

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

# ans = pow_k(2,n) - c(n,a) - c(n,b) - 1

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

print(ans%mod)

Submission status: Accepted

Solution code:
def choose(n, r, M):
    x = 1
    y = 1

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

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

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

Submission status: Accepted

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

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

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

print((pow(2,n,law)- fermat(n,a,law)-fermat(n,b,law)-1)%law)

Submission status: Accepted

Solution code:
def main():
    from math import factorial
    n, a, b = map(int, input().split())
    p = 1000000007

    # 1:花束の組み合わせ総数の(mod p)
    n_all = pow(2, n, p) -1

    # 2:aとbの組み合わせ数の(mod p)を出す。
    a_comb = 0      # aの組み合わせ数
    a_comb_x = 1    # aの組み合わせ数計算の分子。n*(n-1)*…*(n-r+1)のmod p
    a_comb_y = 1    # aの組み合わせ数計算の分母。r!のmod pにおける逆元
    for i in range(n, n-a ,-1):
        a_comb_x *= i
        a_comb_x %= p
    a_comb_y = factorial(a)
    a_comb_y = pow(a_comb_y, p-2,p)
    a_comb = (a_comb_x * a_comb_y) % p

    b_comb = 0      
    b_comb_x = 1    
    b_comb_y = 1    
    for i in range(n, n-b ,-1):
        b_comb_x *= i
        b_comb_x %= p
    b_comb_y = factorial(b)
    b_comb_y = pow(b_comb_y, p-2,p)
    b_comb = (b_comb_x * b_comb_y) % p

    # 3: 1の結果から２のそれをマイナスする。結果が負になったら+p
    r = n_all - a_comb
    if r < 0:
        r += p
    r -= b_comb
    if r < 0:
        r += p
    print(r)

main()

Submission status: Accepted

Solution code:
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        # g2[i] ha i no kaijo no gyakugen
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)
    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)
    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod
    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        mod = self.mod
        for i in range(n - r + 1, n + 1):
            t = t * i % mod
        return t * self.g2[r] % mod
def pown(n, m, mod):
    r = 1
    while n:
        if n & 1:
            r = r * m
            r %= mod
        m *= m
        m %= mod
        n >>= 1
    return r

def main():
    n, a, b = map(int, input().split())
    mod = 10 ** 9 + 7
    c = cmbs(mod)
    return (pown(n, 2, mod) - 1 - c.cmb(n, a) - c.cmb(n, b)) % mod
print(main())

Submission status: Accepted

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

"""繰り返し二乗法"""
def s_pow(x,n):
    ans = 1
    while n>0:
        if(bin(n&1) == bin(1)):
            ans *= x
        x *= x
        n = n>>1
    return ans

"""コンビネーション"""
def cmb(n,r):
    if n-r<r:
        r = n - r
    x,y = 1,1
    for i in range(r):
        x = x*(n-i)%MOD
        y = y*(i+1)%MOD
    return x*pow(y,MOD-2,MOD)


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

Submission status: Accepted

Solution code:
def combination(n, r, p):
    """
    nCr mod p の組み合わせ数を求める関数
    n: 総数
    r: 取り出す個数
    p: 法
    """
    r = min(n - r, r)
    if r == 0:
        return 1
    over = 1
    for i in range(n, n - r, -1):
        over = over * i % p
    under = 1
    for i in range(1, r + 1):
        under = under * i % p
    inv = pow(under, p - 2, p)
    return over * inv % p

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

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

_n = modpow(2, n, p)
_a = combination(n, a, p)
_b = combination(n, b, p)

ans = _n - _a - _b - 1

print(ans%p)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    MOD = 10**9 + 7
    n, a, b = map(int, input().split())
    
    def cmb(n, r):
        if n-r<r:
            r = n-r
        
        X, Y = (1, 1)
        for i in range(r):
            X = X*(n-i)%MOD
            Y = Y*(i+1)%MOD
        return X*pow(Y, MOD-2, MOD)
    
    base = pow(2, n, MOD)-1
    base -= cmb(n, a)
    base -= cmb(n, b)
    base %= MOD
    print(base)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

mod = 10**9+7

total = pow(2,n,mod)
total += mod*3

# c[i] = x**(mod-2) % mod
c = [pow(x,mod-2,mod) for x in range(2*10**5+1)]

nCa = 1
for i in range(1,a+1):
    nCa *= n-i+1
    nCa *= c[i]
    nCa %= mod

nCb = 1
for i in range(1,b+1):
    nCb *= n-i+1
    nCb *= c[i]
    nCb %= mod


print((total - 1 - nCa - nCb) % mod)

Submission status: Accepted

Solution code:
def choose(n, r, M):
    x = 1
    y = 1

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

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
from functools import reduce

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

def nCr(n, r):
    r = min(n-r, r)
    if r == 0: return 1
    numer = reduce(lambda x, y: x * y % mod, range(n, n - r, -1))
    denom = reduce(lambda x, y: x * y % mod, range(1, r + 1))
    return numer * pow(denom, mod - 2, mod) % mod

mod = 10 ** 9 + 7

tnmo = pow(2, n, mod) - 1
an = nCr(n, a)
bn = nCr(n, b)
ans = (tnmo - an - bn) % mod

print(ans)

Submission status: Accepted

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

mod = 10**9+7


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


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

Submission status: Accepted

Solution code:

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

inf = 10**9+7
def comb2(n,k): #素数でわるかつ数字が大きいとき 0(klogN) 10**9まで
    x,y = 1,1
    if n-k < k:
        k = n-k
    for i in range(k):
        x *= n-i
        x = x%inf
        y *= i+1
        y = y%inf
    ans = x* pow(y,inf-2,inf) %inf
    return ans

ans -= comb2(n,a) + comb2(n,b)
ans = ans%inf
print(ans)

Submission status: Accepted

Solution code:
def cmb(n, r, p):
    # nume/deno === nume * pow(deno, p - 2, p) (mod p)
    nume, deno = 1, 1
    for i in range(r):
        nume = nume * (n - i) % p
        deno = deno * (i + 1) % p
    return nume * pow(deno, p - 2, p) % p


if __name__ == "__main__":
    n, a, b = map(int, input().split())
    p = 10 ** 9 + 7

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

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
 
 
mod = 1000000007
 
inv = [1] * 222222
 
# 0 = a * MOD/a + MOD % a
# a*MOD/a = -MOD%a
# a = -MOD%a * inv[MOD/a]
# inv[a] = -inv[MOD%a] * MOD/a
for i in range(2, 222222):
    inv[i] = -inv[mod % i] * (mod // i)
    inv[i] %= mod
    
def comb(n, a):
    res = 1
    for i in range(a):
        res *= n-i
        res *= inv[i+1]
        res %= mod
    return res
 
ans = pow(2, n, mod) - 1 - comb(n, a) - comb(n, b)
 
ans %= mod
if ans < 0:
    ans += mod
 
print(ans)

Submission status: Accepted

Solution code:
# D - Bouquet
def comb(n,k,mod):
    a = 1
    b = 1
    for i in range(k):
        a = a * (n-i) % mod
        b = b * (i+1) % mod
    return a * pow(b, mod-2, mod) % mod
n,a,b=map(int,input().split())
mod=10**9+7
c_n=pow(2,n,mod)-1
c_a=comb(n,a,mod)
c_b=comb(n,b,mod)
print((c_n-c_a-c_b)%mod)

Submission status: Accepted

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

# n, aは正整数(n >= a), pは素数
def comb_mod(n, a, p):
  X = 1
  for num in range(n, n-a, -1):
    X *= num
    X %= p
  Y = math.factorial(a) % p
  return (X * (pow(Y, p-2, p))) % p

print((pow(2, n, mod_num) - (comb_mod(n, a, mod_num) + comb_mod(n, b, mod_num) + 1)) % mod_num)

Submission status: Accepted

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

_sum = 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:
    _sum -= x*pow(y, mod-2, mod)

print(_sum%mod)

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
MAX = max(A, B) + 1
MOD = 1000000007
nCk = [0] * MAX
nCk[0] = 0
nCk[1] = N


def mod_pow(a, n, m):
    res = 1
    while n != 0:
        if n & 1:
            res = (res * a) % m
        n = n >> 1
        a = (a * a) % m
    return res


def mod_inv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u


for i in range(2, MAX):
    nCk[i] = (nCk[i-1] * ((N-i+1) * mod_inv(i, MOD))) % MOD

count = (mod_pow(2, N, MOD) - 1 - nCk[A] - nCk[B]) % MOD
print(int(count))

Submission status: Accepted

Solution code:
"""
D
"""
mod=10**9+7

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

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

ans=(pow(2,N,mod)-1)%mod
num=1
for i in range(1,a+1):
    num=num*(N-i+1)*inv[i]%mod
ans=(ans-num)%mod

num=1
for i in range(1,b+1):
    num=num*(N-i+1)*inv[i]%mod
ans=(ans-num)%mod

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
mo = 10**9+7

def C(n,a):
  d = 1
  u = 1
  for i in range(n-a+1,n+1):
    d *= i
    d %= mo
  for j in range(1,a+1):
    u *= j
    u %= mo
  return d*(pow(u,mo-2,mo))

n,a,b = map(int,input().split())
p = pow(2,n,mo) - 1

print((p-C(n,a)-C(n,b))%mo)

Submission status: Accepted

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

def com(n,k,mod):
    res=1
    tmp=1
    for i in range(1,k+1):
        res=res*(n-i+1)%mod
        tmp=tmp*i%mod
    a=modpow(tmp,1000000005,mod)
    return res*a%mod

MOD=1000000007
n,a,b=map(int,input().split())
ans=modpow(2,n,MOD)-1
t=com(n,a,MOD)
m=com(n,b,MOD)
ans=ans-t
if(ans<0):
    ans+=MOD
ans=ans-m
if(ans<0):
    ans+=MOD
print(ans)

Submission status: Accepted

Solution code:
def ore_comb(n,r,mod):
    '''
    return nCr
    O(min{n-r, r})
    '''
    bunsi=1 
    bunbo=1 
    r = min(r,n-r)
    for i in range(r):#分子
      bunsi = bunsi*(n-i)%mod
      bunbo = bunbo*(i+1)%mod

    ans = (bunsi*pow(bunbo,mod-2,mod))%mod
    return ans

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

mod = 10**9+7

ans = pow(2, N, mod) -1
ans -= ore_comb(N,a,mod)
if ans<0:
    ans += mod
ans -= ore_comb(N,b,mod)
if ans<0:
    ans += mod

print(ans)

Submission status: Accepted

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

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

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

print(ans%MOD)

Submission status: Accepted

Solution code:
def modcmb(n,r,mod=10**9+7):
    res=1
    div=min(r,n-r)
    for i in range(div):
        res=res*(n-i)*pow(div-i,mod-2,mod)%mod
    return res%mod

n,a,b=[int(i) for i in input().split()]
mod=10**9+7
ans=pow(2,n,mod)-1
ans-=modcmb(n,a)
ans%=mod
ans-=modcmb(n,b)
ans%=mod
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
def modcomb(n, r, mod):
    "nCr = X/Yとおく"
    r = min(r, n - r)
    X, Y = 1, 1
    for i in range(1, r + 1):
        X = X * (n + 1 - i) % mod
        Y = Y * i % mod
    # return ue * modpow(sita, mod-2, mod)
    return X * pow(Y, mod-2, mod) % mod

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

Submission status: Accepted

Solution code:
import math

counter = 0

def new_way(n, a, b, mod, nCa, nCb):
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル

    for i in range( 2, n + 1 ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )
    
    nCa = new_cmb(n, a, mod, g1, g2)
    print("a")
    nCb = new_cmb(n, b, mod, g1, g2)
    print("b")

def new_cmb(n, r, mod, g1, g2):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    ans = g1[n] * g2[r] % mod
    ans = ans * g2[n-r] % mod
    return ans


def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    bunshi = 1
    bunbo = 1
    for i in range(r):
        bunshi = bunshi * (n-i) % mod

        bunbo = bunbo * (i+1) % mod
    
    bunbo_inv = my_pow(bunbo, mod-2, mod)

    return bunshi * bunbo_inv % mod

def my_pow(x, n, mod):
    global counter
    
    if n == 0:
        return 1

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

    return K * x % mod

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


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

sum_nCr = my_pow(2, n, mod)

nCa = cmb(n, a, mod)
nCb = cmb(n, b, mod)
# nCa = 0
# nCb = 0
# new_way(n, a, b, mod, nCa, nCb)

ans = sum_nCr - (1 + nCa + nCb)
ans %= mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

# permutation: n * (n-1) * …… * (n-k+1) (mod p)
def prm(n, k, p=10**9+7):
    res = 1
    for i in range(k):
        res = res * (n-i) % p
    return res

# combination: nPk / k! (mod p), note: p must be a prime number
def cmb(n, k, p=10**9+7):
    k = min(k, n - k)
    return prm( n, k ) * pow( prm(k, k), p-2, p ) % p

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

#何も選ばない1通りを除く
ans = pow(2,n,mod) - 1 - cmb(n,a) - cmb(n,b)
print(ans % mod)

Submission status: Accepted

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

mod = 10**9+7

total = pow(2,n,mod)
total += mod*3

def factorials(n,m):
    # 0~n!のリスト
    f = [1,1]
    for i in range(2,n+1):
        f.append(f[-1]*i%m)

    # 0~n!の逆元のリスト
    g = [1]
    for i in range(n):
        g.append(pow(f[i+1],m-2,m))

    return f,g

f,g = factorials(2*10**5+1,mod)

nCa = g[a]
for i in range(1,a+1):
    nCa *= n-i+1
    nCa %= mod

nCb = g[b]
for i in range(1,b+1):
    nCb *= n-i+1
    nCb %= mod

print((total - 1 - nCa - nCb) % mod)

Submission status: Accepted

Solution code:
import math

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

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


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

sum2 = modpow(2, n, mod)
ca = modcomb(a, n, mod)
cb = modcomb(b, n, mod)
ans = (sum2 - ca -cb -1) % mod

print(ans)

Submission status: Accepted

Solution code:
def mpow(a,b,M):
	r = 1
	while(b >= 1):
		if(b%2 == 1):
			r=r*a%M
		b//=2
		a=a*a%M
	return r

def minv(a,M):
	return mpow(a,M-2,M)

def mcomb(a,b,M):
	A = 1
	for i in reversed(range(a-b+1,a+1)):
		A = A * i % M
	A = A * minv(mfact(b,M),M) % M
	return A
def mfact(a,M):
	res = 1
	for i in range(1,a+1):
		res = res * i % M
	return res
def main():
	n,a,b  = [int(n) for n in input().split()]
	M=10**9+7
	A = mpow(2,n,M)-1
	A = ((A - mcomb(n,a,M))%M - mcomb(n,b,M))%M
	print(A)
main()

Submission status: Accepted

Solution code:
from functools import reduce
mod=10**9+7
def nCk(n,k):
  c=reduce(lambda x,y: x*y%mod, range(n,n-k,-1))
  m=reduce(lambda x,y: x*y%mod, range(1,k+1))
  return c*pow(m,mod-2,mod)%mod

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

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


class ModInt:

    def __init__(self, x):
        self.x = x.x if isinstance(x, ModInt) else x % MOD

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

    def __int__(self): return self.x
    __index__ = __int__

    def __add__(self, other): return ModInt(self.x + ModInt(other).x)

    def __sub__(self, other): return ModInt(self.x - ModInt(other).x)

    def __mul__(self, other): return ModInt(self.x * ModInt(other).x)

    def __pow__(self, other): return ModInt(pow(self.x, ModInt(other).x, MOD))

    def __truediv__(self, other): return ModInt(
        self.x * pow(ModInt(other).x, MOD - 2, MOD))

    def __floordiv__(self, other): return ModInt(self.x // ModInt(other).x)

    def __radd__(self, other): return ModInt(other + self.x)

    def __rsub__(self, other): return ModInt(other - self.x)

    def __rpow__(self, other): return ModInt(pow(other, self.x, MOD))

    def __rmul__(self, other): return ModInt(other * self.x)

    def __rtruediv__(self, other): return ModInt(
        other * pow(self.x, MOD - 2, MOD))

    def __rfloordiv__(self, other): return ModInt(other // self.x)

    def __lt__(self, other): return self.x < ModInt(other).x

    def __gt__(self, other): return self.x > ModInt(other).x

    def __le__(self, other): return self.x <= ModInt(other).x

    def __ge__(self, other): return self.x >= ModInt(other).x

    def __eq__(self, other): return self.x == ModInt(other).x

    def __ne__(self, other): return self.x != ModInt(other).x


def cmb(n, r):  # nCr = n!/(n-r)!r!
    retVal = ModInt(1)
    for i in range(n-r+1, n+1):
        retVal *= i
    for i in range(2, r+1):
        retVal /= i
    return retVal


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


def twopow(p):
    if p == 0:
        return ModInt(1)
    if p % 2 == 0:
        t = twopow(p // 2)
        return t * t
    return 2 * twopow(p - 1)


nC = [ModInt(1)]
for i in range(1, 200005):
    nC.append(nC[-1] * (n - i + 1) / i)

print((twopow(n) - nC[a] - nC[b] - 1))
# print((twopow(n) - cmb(n, a) - cmb(n, b)-1))

Submission status: Accepted

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

MOD = 10**9+7

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

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

ans = (ans - cmb(n,a,MOD))%MOD
ans = (ans - cmb(n,b,MOD))%MOD

print(ans)