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

MOD = 1000000007  # type: int

class ModOperator:
    def __init__(self, MOD: int = 10 ** 9 + 7):
        self.MOD = MOD

    def mod_pow(self, x: int, n: int):
        bi = str(format(n, "b"))
        res = 1
        a = x
        for i in range(len(bi)):
            if n >> i & 1:
                res = (res * a) % self.MOD
            a = (a * a) % self.MOD
        return res
    
    def mod_fact(self, x: int):
        res = 1
        for i in range(1, x + 1):
            res = res * i % self.MOD
        return res % self.MOD
    
    def mod_partial_fact(self, x: int, y: int):
        res = 1
        for i in range(x - y + 1, x + 1):
            res = res * i % self.MOD
        return res % self.MOD

    def mod_inv(self, x: int):
        return self.mod_pow(x, self.MOD - 2)
    
    def mod_comb(self, n: int, k: int):
        numerator = self.mod_partial_fact(n, k)
        denomintator = self.mod_fact(k)
        return numerator * self.mod_inv(denomintator) % self.MOD

def main():
    n, a, b = map(int, input().split())
    op = ModOperator()
    print((op.mod_pow(2, n) - op.mod_comb(n, a) - op.mod_comb(n, b) - 1) % MOD)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
MOD = 1000000007
def pow(d, n):
  ps = [d]
  for i in range(64):
    ps.append(ps[-1]*ps[-1]%MOD)
  r = 1
  for i in range(64):
    if n&(1<<i) != 0:
      r = r*ps[i]%MOD
  return r
def perm(n, a):
  r = 1
  for i in range(a):
    r = r*(n-i)%MOD
  return r
def comb(n, a):
  r = perm(n, a)*pow(perm(a, a), MOD-2)%MOD
  return r
r = (pow(2, n)-1-comb(n, a)-comb(n, b))%MOD
print(r)

Submission status: Accepted

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

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

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

abc156_d()

Submission status: Accepted

Solution code:
def main():
    n,a,b = map(int, input().split())
    MOD = 1000000007
    k = b

    modinv_table = [-1] * (k+1)
    modinv_table[1] = 1
    for i in range(2, k+1):
        modinv_table[i] = (-modinv_table[MOD % i] * (MOD // i)) % MOD

    def comb(n, k):
        ans = 1
        for i in range(k):
            ans *= n-i
            ans *= modinv_table[i + 1]
            ans %= MOD
        return ans

    # sigma{comb(n,k)} (2<=k<=n,k!=a,k!=b)
    # 全パターン(2^n) - 0or1個選ぶ時 - sigma{comb(n,k)}(k==a,k==b)
    k1 = comb(n,a) if a>=1 else 0
    k2 = comb(n,b) if b>=1 else 0
    ans = pow(2,n,MOD) - 1 - (k1+k2)
    print(ans%MOD)

main()

Submission status: Accepted

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

# 2^n mod (10^9+7)
s = pow(2, n, mod) - 1

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

Submission status: Accepted

Solution code:
n, a, b = 10, 2, 3

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


def jiecheng(start, end):
    res = 1

    for i in range(start, end + 1):
        res = (res * i) % (10 ** 9 + 7)

    return res

def comb(n, a):
    X = jiecheng(n - a + 1, n) % (10**9  + 7)
    Y = jiecheng(1, a)

    S = X * pow(Y, 10 ** 9 + 5, 10 ** 9 + 7)
    return S


def calculate(n, a, b):
    s = pow(2, n, 10 ** 9 + 7) - 1
    s1 = comb(n, a)
    s2 = comb(n, b)
    res = s - s1 - s2
    res = res % (10**9 + 7)
    return res


result = calculate(n, a, b)
print(result)

Submission status: Accepted

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

def pow_speed(x,n,mod):
    res = 1
    while n > 0:
        if n & 1 == 1:
            res *= x
        x *= x
        x%=mod
        n >>= 1
    return res

def comb(n,x):
    rec=1
    for i in range(n-x+1,n+1):
        rec=rec*i%mod
    rec2=1
    for i in range(1,x+1):
        rec2=rec2*i%mod
    rec2=pow_speed(rec2,mod-2,mod)
    return rec*rec2

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

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

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

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

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

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

    __radd__ = __add__

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

    __rmul__ = __mul__

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

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


def main():
    N, A, B = map(int, input().split())
    total = ModInt(2) ** N - 1
    MAX = max(A, B)
    MIN = min(A, B)

    num = ModInt(1)
    for i in range(MAX):
        if i == MIN:
            total -= num
        num *= N - i
        num /= i + 1

    total -= num
    print(total)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000



d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

n, a, b = LI()


ans = pow(2, n, mod) - 1
# math.factorial()

# print(ans % mod)

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:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

def comb(n,r,mod): #nが大きく、rが小さい時に活用
    ans = 1
    for i in range(r):
        ans *= n-i
        ans %= mod
    d = math.factorial(r)
    d %= mod
    d = pow(d,mod-2,mod)
    ans *= d
    ans %= mod
    return ans

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

Submission status: Accepted

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


def comb2(n, i, mod):
    p = 1
    q = 1

    for s in range(n, n - i, -1):
        p = (p * s) % mod

    for s in range(1, i + 1):
        q = (q * s) % mod

    d = pow(q, mod-2, mod)

    return p * d


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

Submission status: Accepted

Solution code:
def fact(n, k, mod):
    res = 1
    for i in range(k):
        res = res * (n - i) % mod
    return res

def c(x, y, mod):
    y = min(y, x - y)
    return (fact(x, y, mod) * pow(fact(y, y, mod), mod - 2, mod)) % mod

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

Submission status: Accepted

Solution code:
from functools import reduce
def cmb(r):
    numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
    denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
    return numerator * pow(denominator, mod - 2, mod) % mod
n,a,b = map(int,(input().split()))
ans=0
mod=10**9+7

ans=pow(2,n,10**9+7)-1
ans-=cmb(a)
ans-=cmb(b)
print(ans%mod)

Submission status: Accepted

Solution code:
def fer(n, r, p):
    # calculate n_C_k mod p
    # a,pが互いに素のとき a ^ (p-2) = a ^ -1 (mod p)
    x, y = 1, 1
    for i in range(r):
        x = x * (n - i) % p
        y = y * (i + 1) % p
    # x -> n * (n-1) * ... * (n-r+1)
    # y -> 1 * 2 * ... * r
    return x * pow(y, p - 2, p) % p


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

    x = pow(2, n, mod) - 1
    y = fer(n, a, mod)
    z = fer(n, b, mod)
    ans = (x - y - z) % mod
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import factorial
import sys 
import math
sys.setrecursionlimit(400000000)
mod=1000000007
n,a,b=map(int,input().split())
def fac(n,k,mod):
    sum=1
    for i in range(k):
        sum=sum*(n-i)%mod
    return sum

def nck(x,y,mod):
    y=min(y,x-y)
    ans=fac(x,y,mod)*pow(fac(y,y,mod),mod-2,mod)%mod
    return ans
    
ans=pow(2,n,mod)-1-nck(n,a,mod)-nck(n,b,mod)
ans=ans%mod
print(ans)

Submission status: Accepted

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

def comb(r):
    num = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
    dem = reduce(lambda x, y: x * y % mod, [k+1 for k in range(r)])
    return num*pow(dem,mod-2,mod)%mod

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

Submission status: Accepted

Solution code:
N = 1000000007

def fac(n,r,N):
    ans=1
    for i in range(r):
        ans=ans*(n-i)%N
    return ans

def combi(n,r,N):
    r= min(r, n-r)
    ans = fac(n,r,N)*pow(fac(r,r,N),N-2,N)%N
    return ans

n,a,b = map(int, input().split())
ans = pow(2,n,N)-combi(n,a,N)-combi(n,b,N)-1
if ans<0:
    ans+=N
if ans<0:
    ans+=N
print(ans)

Submission status: Accepted

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

fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
Mod = 10**9+7
def COMinit():
  #N_C_kのN
  for i in range(2, n+10):
    fac.append(fac[-1]*i%Mod)
    inv.append((-inv[Mod%i] * (Mod//i)) % Mod)
    finv.append(finv[-1] * inv[-1] % Mod)


def COM(n, k):
  if n < 0 or k < 0 or n < k:
    return 0
  return fac[n] * (finv[k] * finv[n-k] % Mod) % Mod

def ncr(n, r, p):
  num = den = 1
  for i in range(r):
    num = (num * (n - i)) % p
    den = (den * (i + 1)) % p
  return (num * pow(den, p - 2, p)) % p
p=10**9+7


ans = pow(2, n, Mod)

ans -= ncr(n, a, p)
ans %= Mod
ans -= ncr(n, b, p)
ans %= Mod
print(ans-1)

Submission status: Accepted

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

# 場合の数をmodで割った余り nCr % mod
def ncr_mod(n,r,mod):
  a,b=1,1
  for i in range(r):
    a*=n-i
    a%=mod
    b*=i+1
    b%=mod
  return (a*pow(b,mod-2,mod))%mod
ans-=ncr_mod(n,a,mod)
ans-=ncr_mod(n,b,mod)
print(ans%mod)

Submission status: Accepted

Solution code:
import sys

import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 10
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    def fast_pow(num, kata, mod):
        if kata == 0:
            return 0

        res = 1
        while kata > 0:
            if kata & 1 == 1:
                res = res * num % mod
            num = num * num % mod

            kata >>= 1
        return res

    n, a, b = ns()

    total = fast_pow(2, n, MOD) - 1

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

    tmp_a = choose(n, a)
    tmp_b = choose(n, b)

    ans = total - tmp_a - tmp_b
    ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
#2**n-nCa-nCb-1
P=10**9+7
class Combination:
    def __init__(self,N,P):
        fact=[];ifact=[];fact=[1]*(N+1);ifact=[0]*(N+1)
        for i in range(1,N):
            fact[i+1]=(fact[i]*(i+1))%P
        ifact[-1]=pow(fact[-1],P-2,P)
        for i in range(N,0,-1):
            ifact[i-1]=(ifact[i]*i)%P
        self.fact=fact;self.ifact=ifact;self.P=P
    def comb(self,n,k):
        return (self.fact[n]*self.ifact[k]*self.ifact[n-k])%self.P
C=Combination(3*10**5,P)
A=1
for i in range(1,a+1):
    A*=n-i+1
    A%=P
A*=C.ifact[a]
A%=P
B=1
for i in range(1,b+1):
    B*=n-i+1
    B%=P
B*=C.ifact[b]
B%=P
print((pow(2,n,P)-A-B-1)%P)

Submission status: Accepted

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

Submission status: Accepted

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

MOD = 1000000007  # type: int

class ModOperator:
    def __init__(self, MOD: int = 10 ** 9 + 7):
        self.MOD = MOD

    def mod_pow(self, x: int, n: int):
        bi = str(format(n, "b"))
        res = 1
        a = x
        for i in range(len(bi)):
            if n >> i & 1:
                res = (res * a) % self.MOD
            a = (a * a) % self.MOD
        return res
    
    def mod_fact(self, x: int):
        res = 1
        for i in range(1, x + 1):
            res = res * i % self.MOD
        return res % self.MOD
    
    def mod_partial_fact(self, x: int, y: int):
        res = 1
        for i in range(x - y + 1, x + 1):
            res = res * i % self.MOD
        return res % self.MOD

    def mod_inv(self, x: int):
        return self.mod_pow(x, self.MOD - 2)
    
    def mod_comb(self, n: int, k: int):
        numerator = self.mod_partial_fact(n, k)
        denomintator = self.mod_fact(k)
        return numerator * self.mod_inv(denomintator) % self.MOD

def solve(n: int, a: int, b: int):
    op = ModOperator()
    print((op.mod_pow(2, n) - op.mod_comb(n, a) - op.mod_comb(n, b) - 1) % MOD)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = int(next(tokens))  # type: int
    b = int(next(tokens))  # type: int
    solve(n, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
p = 10**9+7
m = max(a,b)
A = [1] + [None] * m
invA = [None] * (m+1)

for i in range(1,m+1):
  A[i] = i * A[i-1] % p

invA[m] = pow(A[m], p-2, p)
for i in range(m):
  invA[m-i-1] = invA[m-i] * (m-i) % p

# n!/(n-a)!は個別に計算しよう幸いa,bの2計算すればいいので
na = 1
for i in range(a):
  na *= n-i
  na %= p
  
nb = 1
for i in range(b):
  nb *= n-i
  nb %= p

ca = na * invA[a] % p
cb = nb * invA[b] % p
ans = (pow(2,n,p) - 1 - ca - cb) % p
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
from collections import defaultdict

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

def main():
    n,a,b = list(map(int,sys.stdin.readline().split()))
    mod = 10**9 + 7
    ans = pow(2, n, mod) - 1
    ans = (ans - comb(n, a, mod) - comb(n, b, mod)) % mod
    print(ans)
    return 0

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod=10**9+7

n,a,b=map(int,input().split())
res=pow(2,n,mod)
res=(res-1)%mod

ncb=1
for i in range(1,b+1):
	ncb*=(n-i+1)*pow(i,mod-2,mod)
	ncb%=mod
	if i==a:
		nca=ncb
		
print((res-nca-ncb)%mod)

Submission status: Accepted

Solution code:
def pow(a,n,p):
    if n==1:
        return a%p
    elif n%2==1:
        return a*pow(a,n-1,p)
    else:
        return (pow(a,n//2,p)**2)%p
from math import factorial as f
 
def nCr(n,r,p):
    r=min(r,n-r)
    if r==0:
        return 1
    x,y=1,1
    for i in range(r):
        x=x*(n-i)%p
        y=y*(i+1)%p
    return x*pow(y,p-2,p)%p


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

ans = (pow(2, n, 10**9 + 7) - 1 - nCr(n, a, 10**9 + 7) - nCr(n, b, 10**9 + 7)) % (10**9 + 7)

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

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

def cmb_k(k):
    X = 1
    for i in range(N-k+1, N+1):
        X = X * i % MOD

    Y = 1
    for i in range(1,k+1):
        Y = Y * i % MOD

    Y_inv = pow_mod(Y, MOD-2)
    return X * Y_inv % MOD

ans = pow_mod(2, N) - 1 - cmb_k(A) - cmb_k(B)
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


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


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

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


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
ns = lambda: stdin.readline().rstrip()
na = lambda: list(map(int, stdin.readline().split()))

# code here
n, a, b = na()
mod = 1000000007

def c(n, r):
    nu = 1
    de = 1
    for i in range(r):
        # nCr の分子
        nu = nu * (n - i) % mod
        # nCr の分母
        de = de * (i + 1) % mod
    # フェルマーの小定理より
    return nu * pow(de, mod - 2, mod) % mod

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, a, b = MAP()

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

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

def C(n, k):
	tmp = 1
	for i in range(n, n-k, -1):
		tmp = tmp*i%mod
	return (tmp*pow(fact[k], mod-2, mod))%mod

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


n, a, b = MAP()

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


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

def C(n, a):
	tmp = 1
	for i in range(n, n-a, -1):
		tmp = (tmp*i)%mod
	return tmp*pow(fact[a], mod-2, mod)

print((ans - C(n, a) - C(n, b))%mod)

Submission status: Accepted

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

def power_func(a,n,p):
    bi = str(format(n,"b"))
    res = 1
    for i in range(len(bi)):
        res = (res*res) %p
        if bi[i] == "1":
            res = (res*a) %p
    return res

def main():
    n,a,b=map(int,input().split())
    mod=10**9+7
    ans=(power_func(2,n,mod)-modComb(n,a,mod)-modComb(n,b,mod)-1)%mod
    print(ans)
if __name__=="__main__":
    main()

Submission status: Accepted

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

def comb(n, x):
    numerator = 1
    for i in range(n, n - x, -1):
        numerator = numerator * i % mod

    denominator = 1
    for j in range(x, 1, -1):
        denominator = denominator * j % mod

    d = pow(denominator, mod-2, mod)

    return numerator * d

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

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

Submission status: Accepted

Solution code:
import functools

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

total = pow(2, n, m) -1

def f(n, a, m):
    X = functools.reduce(lambda x,y : (x * y) % m, range(n, n-a, -1))
    Y = functools.reduce(lambda x,y : (x * y) % m, range(1, a+1))
    return  (X * pow(Y, m - 2, m)) % m

# nCa
print((total - f(n, a, m) - f(n, b, m)) % m)

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
mod = 1000000007
ans = pow(2,n,mod) - 1

def fur(n,k):
    p,q = 1,1
    for i in range(k):
        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:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


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


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

Submission status: Accepted

Solution code:
def comb(n, r):
    _n = 1
    _r = 1
    for i in range(n - r + 1, n + 1):
        _n = _n * i % m
    for i in range(2, r + 1):
        _r = _r * i % m
    return _n * pow(_r, m - 2, m)


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

Submission status: Accepted

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

# ans 
# = 1本選ぶ,2本選ぶ,...n本選ぶ - (a本選ぶ + b本選ぶ)
# = nC1+nC2+...+nCn - (nCa + nCb)
# = 2^n-1 - nCa - nCb

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
  
def cmb(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

mod = 10**9+7
ans = 2**n % mod
ans -= 1 + cmb(n,a,mod) + cmb(n,b,mod)
ans = ans % mod
print(ans)

Submission status: Accepted

Solution code:

def create_array(n: int, r: int, mod, mod2):
    m_ls = [1] * (r + 1)

    for i, j in zip(range(n, 0, -1), range(1, r + 1)):
        m_ls[j] = (m_ls[j - 1] * i * pow(j, mod2, mod)) % mod
    return m_ls


def main():
    n, a, b = map(int, input().split())
    _mod = 1000000007
    _mod2 = 1000000005

    m_ls = create_array(n, b, _mod, _mod2)

    _all_cnts = pow(2, n, _mod) - 1
    ans = _all_cnts + (_mod - m_ls[a]) + (_mod - m_ls[b])
    ans %= _mod

    print(ans)


main()

Submission status: Accepted

Solution code:
#powは繰り返し2乗法により指数計算を行う関数
mod=10**9+7
n,a,b=map(int,input().split())
ans=pow(2,n,mod)-1 #n種類の花を使って花束を作る総数は2^n-1通り

comb1=1 #nCaの計算
for i in range(n-a+1,n+1): #n*(n-1)*…*(n-a+1)を計算
 comb1*=i
 comb1%=mod
for i in range(1,a+1): #1/a!=1/(1*2*…*a)=1^(p-2)*2^(p-2)*…*a^(p-2) (p=10**9+7)を計算
 comb1*=pow(i,mod-2,mod)
 comb1%=mod

comb2=1  # nCbの計算
for i in range(n-b+1,n+1): #n*(n-1)*…*(n-b+1)を計算
 comb2*=i
 comb2%=mod
for i in range(1,b+1): #1/b!=1/(1*2*…*b)=1^(p-2)*2^(p-2)*…*b^(p-2) (p=10**9+7)を計算
 comb2*=pow(i,mod-2,mod)
 comb2%=mod
ans-=(comb1+comb2) #nCa、nCbを総数から引く
ans%=mod
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:


n,a,b = map(int,input().split())
from functools import reduce
def mod_comb(n,r,mod=10**9+7):
    num=reduce(lambda x,y:x*y%mod,range(n,n-r,-1))
    den=reduce(lambda x,y:x*y%mod,range(1,r+1))
    return num*pow(den,mod-2,mod)%mod
mod = 10**9+7
bi = [(2**i)%mod for i in range(30) if 2**i<=n]
ans = 1
s = list(reversed(bin(n)[2:]))
for i in range(len(s)):
    ans *= 2**(bi[i]*int(s[i]))
    ans %= mod
ans = (ans+mod-1)%mod
ans = (ans-mod_comb(n,a)-mod_comb(n,b))%mod
print(ans)

Submission status: Accepted

Solution code:
from math import factorial
from operator import mul
from functools import reduce

MOD = 10 ** 9 + 7


def pow_mod(a, x, mod=MOD):
    return pow(a, x, mod) if x != -1 else pow(a, mod - 2, mod)


def factorial_mod(n, mod=MOD):
    if n == 1:
        return 1
    return n * factorial(n - 1) % mod


def comb_mod(n, k, mod=MOD):
    return reduce(lambda x, y: x * y % mod, range(n, n - k, -1)) * pow_mod(factorial_mod(k), -1, mod) % mod


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

print((pow_mod(2, n, MOD) - comb_mod(n, a) - comb_mod(n, b) - 1) % MOD)

Submission status: Accepted

Solution code:
import math

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

def comb(n,x):
  numerator = 1
  for i in range(n-x+1,n+1):
    numerator = numerator * i % mod

  denominator = 1
  for j in range(1,x+1):
    denominator = denominator * j % mod
  d = pow(denominator,mod-2,mod)
  return numerator * d
a = comb(n, a)
b = comb(n, b)

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

Submission status: Accepted

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

def comb(n,x):
    numerator = 1
    for i in range(n-x+1,n+1):
        numerator=  numerator * i  % mod
    
    denominator = 1
    for j in range(1,x+1):
        denominator = denominator * j % mod
    
    d = pow(denominator,mod-2,mod)

    return numerator * d

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

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from functools import reduce
def mod_comb4(n,r,mod=10**9+7):
    num=reduce(lambda x,y:x*y%mod,range(n,n-r,-1))
    den=reduce(lambda x,y:x*y%mod,range(1,r+1))
    return num*pow(den,mod-2,mod)%mod
def main():
    n,a,b=map(int,input().split())
    mod=10**9+7
    print((pow(2,n,mod)-1-mod_comb4(n,a)-mod_comb4(n,b))%mod)

if __name__=='__main__':
    main()

Submission status: Accepted

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

def pow(a,n,p):
  if n==1:
    return a%p
  elif n%2==1:
    return a*pow(a,n-1,p)
  else:
    return (pow(a,n//2,p)**2)%p
  
from math import factorial as f

def nCr(n,r,p):
  r=min(r,n-r)
  if r==0:
    return 1
  x,y=1,1
  for i in range(r):
    x=x*(n-i)%p
    y=y*(i+1)%p
  return x*pow(y,p-2,p)%p

def main():
  p=10**9+7
  print((pow(2,n,p)-1-nCr(n,a,p)-nCr(n,b,p))%p)

if __name__=='__main__':
  main()