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

def read_int_list(sep = " "):
    return [int(s) for s in sys.stdin.readline().rstrip().split(sep)]


def dprint(*args, **kwargs):
    return
    print(*args, **kwargs)


def choose(a, b, mod):
    numer, denomi = 1, 1 
    for i in range(0, b):
        denomi = (denomi * (i + 1)) % mod
        numer = ((a - i) * numer) % mod
    return (numer * pow(denomi, mod - 2, mod)) % mod


def main():
    mod = 1000000007
    n, a, b = read_int_list()
    ans = pow(2, n, mod)
    ans = (ans - 1) % mod  # case for zero flowers
    ans = (ans - choose(n, a, mod)) % mod
    ans = (ans - choose(n, b, mod)) % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def modPow(a, n, mod):
  if n == 1:
    return a % mod
  if n%2 == 1:
    return (a * modPow(a, n - 1, mod)) % mod
  t = modPow(a, n / 2, mod)
  return (t * t) % mod

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

  
n, a, b = map(int, input().split())
mod = 10**9+7
ans = modPow(2, n, mod)-1
aa = comb(n, a, mod)
bb = comb(n, b, mod)

print((ans-aa-bb)%mod)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
m=10**9+7
def com(n,k,m):
  p,q=1,1
  for i in range(n-k+1,n+1):
    p*=i
    p%=m
  for i in range(1,k+1):
    q*=i
    q%=m
  return p*pow(q,m-2,m)%m
ca,cb=com(n,a,m),com(n,b,m)
ans=(pow(2,n,m)-1-ca-cb)%m
print(ans)

Submission status: Accepted

Solution code:
def cmb_mod(n, r, mod):
    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)) % mod


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

Submission status: Accepted

Solution code:
MOD = 1000000007


def cal(a, n):
    if n == 1:
        return a
    if n % 2 == 0:
        return (cal(a, n // 2) % MOD) ** 2 % MOD
    else:
        return (cal(a, n - 1) % MOD) * a % MOD


def cal_p(n, r):
    res = 1
    for i in range(r):
        res = res * (n - i) % MOD

    return res


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

all = cal(2, n) - 1
A = cal_p(n, a) * cal(cal_p(a, a), 1000000005) % MOD
B = cal_p(n, b) * cal(cal_p(b, b), 1000000005) % MOD

print((all - A - B) % MOD)

Submission status: Accepted

Solution code:
def get_exp_mod(base, exp, mod):
    exp_bin = str(format(exp, 'b'))  # ２進表現
    res = 1
    for i in range(len(exp_bin)):
        if exp_bin[-i - 1] == '1':
            res = res * base % mod
        base = base * base % mod  # base^2^nをmodで割ったあまり

    return res


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


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


# 2^n -1のmodを求める
all_case = (get_exp_mod(2, n, mod) - 1) % mod

# nCa modを引く
print((all_case - comb(n, a, mod) - comb(n, b, mod)) % mod)

Submission status: Accepted

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


M = 10**9+7

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


def power(x,n):
    res = 1
    if(n>0):
        res = power(x,n//2)
        if (n%2)==0:
            res = (res*res)%M
        else:
            res = (((res*res)%M)*x)%M
    return res

def comb(n,a):
    ans = 1
    for i in range(a):
        ans = (ans*(n-i))%M
        ans = (ans*power(i+1,M-2))%M 
    return ans

#print(pow(10,2))
#print(power(5,8))

print((power(2,N)-1-comb(N,a)-comb(N,b))%M)

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
mod = 10**9+7
ans = pow(2,n,mod) - 1 
mod_inv = [0, 1] + [0] * (b+3)
for i in range(2, b+5):
    mod_inv[i] = - mod_inv[mod % i] * (mod // i) % mod
def comod(n, r, mod):
    ans = 1
    for i in range(r):
        ans *= (n-i) % mod
        ans *= mod_inv[i+1]
        ans %= mod
    return ans
ans -= comod(n,a,mod) + comod(n,b,mod)
print(ans % mod)

Submission status: Accepted

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

max_r = b

# nCrでnがでかすぎる時は直接O(r)で計算した方がいい
# 1<=n<=10**9, 1<=k<=10**7くらいのとき

def make_mod_inv(l,p): # lまでの逆元を作る
    mod_inv = [0, 1] + [0] * (l+3) # inv[n] = n^(-1) mod p, 0! = 1　だけど便宜上inv[0]=0にしてる
    for i in range(2, l+5):
        mod_inv[i] = -mod_inv[p % i] * (p // i) % p
    return mod_inv

mod_inv = make_mod_inv(max_r,p)

def NCr_mod_p(N, r, p):
    ret = 1
    for i in range(r):
        ret *= (N-i)%p
        ret *= mod_inv[i+1]
        ret %= p
    return ret

ans = pow(2,n,p) - 1 - NCr_mod_p(n,a,p) - NCr_mod_p(n,b,p)
print(ans%p)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
def main():
	n,a,b = inputMap()
	#print(pow(2, n))

	total = pow(2, n, mod)
	total -= 1
	tmp = combination(n, a, mod)
	if total < tmp:
		total = total + mod - tmp
	else:
		total -= tmp

	tmp = combination(n, b, mod)
	if total < tmp:
		total = total + mod - tmp
	else:
		total -= tmp

	print(total)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
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

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
def main():
	n,a,b = inputMap()
	#print(pow(2, n))

	total = pow(2, n, mod)
	total -= 1
	tmp = combination(n, a, mod)
	if total < tmp:
		total = total + 1000000007 - tmp
	else:
		total -= tmp

	tmp = combination(n, b, mod)
	if total < tmp:
		total = total + 1000000007 - tmp
	else:
		total -= tmp

	print(total)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

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

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

if __name__ == "__main__":
	main()

Submission status: Accepted

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

max_r = b

# nCrでnがでかすぎる時は直接計算した方がいい
# 1<=n<=10**9, 1<=k<=10**7くらいのとき

def make_inv(m,p): # 必要なところnCkのkまでの逆元を作る
    inv = [0, 1] + [0] * m # inv[n] = n^(-1) mod p, 0! = 1　だけど便宜上inv[0]=0にしてる
    for i in range(2, m+2):
        inv[i] = -inv[p % i] * (p // i) % p
    return inv

inv = make_inv(max_r+3,p)

def NCr_mod_p(N, r, p):
    ret = 1
    for i in range(r):
        ret *= (N-i)%p
        ret *= inv[i+1]
        ret %= p
    return ret

ans = pow(2,n,p) - 1 - NCr_mod_p(n,a,p) - NCr_mod_p(n,b,p)
print(ans%p)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

n, a, b = map(int, input().split())
mod = 10**9 + 7
a = min(a, n-a)
b = min(b, n-b)
com = [1] * (max(a, b) + 1)
for i in range(1,len(com)):
    com[i] = (com[i-1] * pow(i, mod-2, mod) * (n-i+1)) % mod
print((pow(2, n, mod) + mod - 1 - com[a] - com[b]) % mod)

Submission status: Accepted

Solution code:
from functools import reduce 
def solve():
    mod = 10 ** 9 + 7
    n, a, b = map(int, input().split())
    all_comb = pow(2, n, mod) - 1

    X = reduce(lambda x,y:x*y%mod, list(range(n-a+1, n+1))) 
    Y = reduce(lambda x,y:x*y%mod, list(range(1,a+1)))
    Y = pow(Y, mod-2, mod)
    a_comb = X * Y % mod

    X = reduce(lambda x,y:x*y%mod, list(range(n-b+1, n+1))) 
    Y = reduce(lambda x,y:x*y%mod, list(range(1,b+1)))
    Y = pow(Y, mod-2, mod)
    b_comb = X * Y % mod

    ans = all_comb - a_comb
    ans %= mod
    ans -= b_comb
    ans %= mod
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

def f(n: int, a: int) -> int:
    n = functools.reduce(lambda x, y: x*y%mod, range(n, n-a, -1))
    d = functools.reduce(lambda x, y: x*y%mod, range(1, a+1))
    return n*pow(d, mod - 2, mod)%mod

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

Submission status: Accepted

Solution code:
from functools import reduce
mod=10**9+7

def f(A):
 dem=reduce(lambda x,y:x*y%mod,range(n,n-A,-1))
 num=reduce(lambda x,y:x*y%mod,range(1,A+1))
 return dem*pow(num,mod-2,mod)%mod

stdin=open(0)
n,a,b=map(int,stdin.read().split())
ans=pow(2,n,mod)-f(a)-f(b)-1
ans%=mod
print(ans)

Submission status: Accepted

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


def permMOD(MOD, N, R=-1):
    from functools import reduce as r
    if R==-1: R=N
    return r(lambda x,y: x*y%MOD, range(N, N-R, -1))


def combMOD(MOD, N, R):
    return permMOD(MOD, N, R) * pow(permMOD(MOD, R), MOD-2, MOD) % MOD


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

Submission status: Accepted

Solution code:
def main():
    n,a,b = map(int,input().split())
    MOD = 10**9 +7
    s = pow(2,n,MOD)-1
    
    print(comb_mod(n,MOD,a,b,s))

def comb_mod(n, mod,a,b,s):
    numerator = 1
    denominator = 1
    for i in range(b):
        numerator = (numerator * (n - i)) % mod
        denominator = (denominator * (i + 1)) % mod
        if i == a-1 or i == b-1:
            s = s - (numerator * pow(denominator, mod - 2, mod)) % mod
    return s%mod


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n,a,b = map(int,input().split())
    MOD = 10**9 +7
    s = pow(2,n,MOD)-1
    P_ni = 1
    F_i = 1

    s = s - comb_mod(n,a,MOD)
    s = s - comb_mod(n,b,MOD)

    print(s%MOD)

def comb_mod(n, k, mod):
    numerator = 1
    denominator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % mod
        denominator = (denominator * (i + 1)) % mod

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


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def combmod(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
  
num,A,B = list(map(int, input().split()))
print((pow(2,num,10**9+7) - 1 - combmod(num,A,10**9+7) - combmod(num,B,10**9+7)) % (10**9+7))

Submission status: Accepted

Solution code:
from sys import stdin
from math import factorial
n,a,b = map(int,stdin.readline().rstrip().split())
if n <= 2:
    print(0)
    exit()
def combination(n,r,mod=10**9+7):
    r=min(r,n-r)
    up,down=1,1
    for i in range(r):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod
kotae = 2**n-combination(n,a)-combination(n,b)-1
kotae %= 10**9+7
print(kotae)

Submission status: Accepted

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

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

ans -= (comb1+comb2)
ans %= mod
print(ans)

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
inv = [0] * MAX
inv[1] = 1


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

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

Submission status: Accepted

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

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

cn = pow(2,n,div)-1
ca = combinations(n,a,div)
cb = combinations(n,b,div)

print((cn-ca-cb)%div)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
mod=10**9+7
def C(n,k,mod):
    k=min(k,n-k)
    comb=1
    for i in range(k):
        temp=(n-i)*pow(i+1,mod-2,mod)
        comb=comb*temp%mod

    return comb

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

Submission status: Accepted

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

p = 10 ** 9 + 7
N = 10 ** 5 *5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


# def f(x):
#     if x==1:
#         return 2
#     elif x==2:
#         return 4
#     elif x%2==0:
#         return f(x//2)**2
#     else:
#         return f(x//2)**2*2

di131072 = 1
for i in range(131072):
    di131072 *= 2
    di131072 %= p

q = n//131072
r = n%131072
ans = 1
for i in range(q):
    ans *= di131072
    ans %= p
for i in range(r):
    ans *= 2
    ans %= p


fact2 = []
fact2num = max(a,b)+2
now = 1
for i in range(fact2num):
    now *= (n-i)
    now %= p
    fact2.append(now)

def ncr(n,r):
    return (fact2[r-1]*factinv[r])%p


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
mod = 10**9+7
    
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
    

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

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

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

Submission status: Accepted

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

mmod = 10**9 + 7


def comb_mod(n, r, mod=mmod):
    nume = 1
    deno = 1

    r = min(r, n - r)

    for i in range(1, r + 1):
        nume = (nume * (n + 1 - i)) % mod
        deno = (deno * i) % mod

    return (nume * pow(deno, mod - 2, mod)) % mod


result_a = comb_mod(n, a)
result_b = comb_mod(n, b)
total = (pow(2, n, mmod) - result_a - result_b - 1) % mmod

print(total)

Submission status: Accepted

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

mod = 10**9 + 7

import time
start = time.time()

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
	return pow(x, mod-2, mod)

modinv_table = [-1] * (b+1)
for i in range(1, b+1):
    modinv_table[i] = modinv(i)

end = time.time()
# print("time: ", end - start)

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

# (2 ** n - 1) - nCa - nCb
ans = pow(2, n, mod) - 1

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


# print(binomial_coefficients2 (5, 2) % mod)

Submission status: Accepted

Solution code:
# AtCoder用のライブラリ
# 参照
# https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a

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

MOD = 10 ** 9 + 7


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


# aの-1乗をmで割ったときの商を求める
def mod_inv(a, m=10 ** 9 + 7):
    b = m
    u = 1
    v = 0
    while b > 0:
        t = a // b
        a -= t * b
        c = a
        a = b
        b = c

        u -= t * v
        c = u
        u = v
        v = c
    u %= m
    return u


inv_fact_list = [1]
P_list = [1]


def combination(r):
    if r > len(inv_fact_list) - 1:
        _list_extend(r)
    return inv_fact_list[r] * P_list[r] % MOD


def _list_extend(needed):
    now = len(inv_fact_list)
    while now <= needed:
        P_list.append(P_list[-1] * (n - now + 1) % MOD)
        inv_fact_list.append(inv_fact_list[-1] * mod_inv(now) % MOD)
        now += 1


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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# AtCoder用のライブラリ
# 参照
# https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a


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


# aの-1乗をmで割ったときの商を求める
def mod_inv(a, m=10 ** 9 + 7):
    b = m
    u = 1
    v = 0
    while b > 0:
        t = a // b
        a -= t * b
        c = a
        a = b
        b = c

        u -= t * v
        c = u
        u = v
        v = c
    u %= m
    return u


# 組み合わせ数(nCk)を計算させる。
# nを固定しながら複数のkに対して計算させることができるようにしてあるため、
# 計算量はO(max(k)*log(mod))のため、実質O(max(k))。
class ModCombination:
    def __init__(self, n, mod=10 ** 9 + 7):
        self.N = n
        self.MOD = mod
        self.inv_fact_list = [1]
        self.P_list = [1]

    def combination(self, r):
        if r > len(self.inv_fact_list) - 1:
            self._list_extend(r)
        return self.inv_fact_list[r] * self.P_list[r] % self.MOD

    def _list_extend(self, needed):
        now = len(self.inv_fact_list)
        while now <= needed:
            self.P_list.append(self.P_list[-1] * (self.N - now + 1) % self.MOD)
            self.inv_fact_list.append(self.inv_fact_list[-1] * mod_inv(now) % self.MOD)
            now += 1


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

MOD = 10 ** 9 + 7

c = ModCombination(n)

ans = (mod_pow(2, n) - c.combination(b) - c.combination(a) - 1) % MOD

print(ans)

Submission status: Accepted

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


def nCr(n,r,mod = 10**9+7):
    r = min(n-r,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


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

Submission status: Accepted

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

def comb_mod(n, k, mod):
    numerator = 1
    denominator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % mod
        denominator = (denominator * (i + 1)) % mod

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

def factor(a,b):
    ans = 1
    for i in range(a, b+1):
        ans*=i
    return ans

total = (pow(2,n,p) - 1) % p
case_a = comb_mod(n, a, p)
case_b = comb_mod(n, b, p)

print((total - case_a - case_b) % p)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
p = 1000000007
def fast_pow(x,n,p):
    ans = 1
    while(n > 0):
        if n & 1 == 1:
            ans = ans * x % p
        x = x * x % p
        n = n >> 1
    return ans

def comb_mod(n, k, mod):
    numerator = 1
    denominator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % mod
        denominator = (denominator * (i + 1)) % mod

    return (numerator * fast_pow(denominator, mod - 2, mod)) % mod

def factor(a,b):
    ans = 1
    for i in range(a, b+1):
        ans*=i
    return ans

total = (fast_pow(2,n,p) - 1) % p
case_a = comb_mod(n, a, p)
case_b = comb_mod(n, b, p)

print((total - case_a - case_b) % p)

Submission status: Accepted

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

n = 10 ** 9
k = 2 * 10 ** 5
mod = 10**9 + 7

# x ** a をmodで割った余りを、O(log(a))時間で求める。
def power(x, a):
    if a == 0:
        return 1
    elif a == 1:
        return x
    elif a % 2 == 0:
        return power(x, a//2) **2 % mod
    else:
        return power(x, a//2) **2 * x % mod

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
    return power(x, mod-2)

def binomial_coefficients(n, k):
    numera = 1  # 分子
    denomi = 1  # 分母

    for i in range(k):
        numera *= n-i
        numera %= mod
        denomi *= i+1
        denomi %= mod
    return numera * modinv(denomi) % mod


print(((((power(2, q) - binomial_coefficients(q, a)) % mod) - binomial_coefficients(q, b)) % mod - 1) % mod)

Submission status: Accepted

Solution code:
# TODO: P3: Create modint library with Python 
"""
【競プロ】繰り返し二乗法と再帰関数
https://math.nakaken88.com/textbook/cp-binary-exponentiation-and-recursive-function/
「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜
https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a
Pythonでmodintを実装してみた
https://qiita.com/wotsushi/items/c936838df992b706084c

"""
# No mod

# def pow(a,n):
#     """
#     繰り返し二乗法 (半分の数の 2 乗)
#     a の n 乗を O(logN) で計算する
#     """
#     if n == 0:
#         return 1
#     x = pow(a, n//2)
#     x *= x
#     if n%2 == 1:
#         x *= a
#     return x
# def choose(n, a):
#     """
#     nCa (n 個から a 個選ぶ組み合わせ)
#         分子: n!
#         分母: a! * (n-a)!
#     約分して
#         分子: n * (n-1) * ... * (n-a+1) = (n-i) の積の和 (i=0 ~ a-1)
#         分母: a!
#     逆元
#      フェルマーの小定理より
#         1 ≡ x**(p-1) (mod p)
#         => 1/x ≡ x**(p-2) (mod p)
#         => 1/x%p = x**(p-2)%2
#     """
#     x = 1 # 分子
#     y = 1 # 分母
#     for i in range(a):
#         x *= n-i
#         y *= i+1
#     pow
#     return x / y

def pow(a, n, MOD):
    """
    繰り返し二乗法 (半分の数の 2 乗)
    Compute nth power of a -- O(logn)
    """
    if n == 0:
        return 1
    x = pow(a, n//2, MOD)
    x = (x%MOD * x%MOD) % MOD
    if n%2 == 1:
        x = (x%MOD * a%MOD) % MOD
    return x

def choose(n, a, MOD):
    """
    nCa (Choose a from n)
        numerator (分子): n!
        denominator(分母): a! * (n-a)!
    Reduce... (約分)
        numerator:: n * (n-1) * ... * (n-a+1) = (n-i) の積の和 (i=0 ~ a-1)
        denominator: a!
    iverse (逆元)
     フェルマーの小定理
        1 ≡ x**(p-1) (mod p)
        => 1/x ≡ x**(p-2) (mod p)
        => 1/x%p = x**(p-2)%2
    """
    x = 1 # numerator
    y = 1 # denominator
    for i in range(a):
        x = (x%MOD * (n-i)%MOD) % MOD
        y = (y%MOD * (i+1)%MOD) % MOD
    return (x * pow(y, MOD-2, MOD)) % MOD

"""
AC: https://atcoder.jp/contests/abc156/submissions/10294982
N**2 - 1 - nCa - nCb

pow(2,n)
140625001
nCa
-483404860
nCb
589953354
"""

n, a, b = map(int, input().split())
MOD = 1000000007
# n,a,b = 4,1,3
# n,a,b = 1000000000,141421,173205

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

Submission status: Accepted

Solution code:
MOD = (10**9) + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

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

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

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

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

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

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    n, a, b = (int(i) for i in input().split())
    ans = modint(pow(2, n, MOD))
    c_a = modint(1)
    c_b = modint(1)
    for k in range(a):
        c_a *= (n-k)
    for k in range(1, a+1):
        c_a /= k
    for k in range(b):
        c_b *= (n-k)
    for k in range(1, b+1):
        c_b /= k
    ans -= c_a + c_b + 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

ans = power(2, n, mod) - cmb2(n, a, mod) - cmb2(n, b, mod) -1
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
from math import factorial

mod = 10**9 + 7

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

n, a, b = na()

def pow(a,n,p=mod):
    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 comb(a, b, p=mod):
    res = 1
    pres = 1
    for i in range(b):
        res = (res*(a-i))%p
        pres = (pres*(i+1))%p
    return res*pow(pres, p-2, p) % p
print((pow(2, n) - 1 - comb(n, a) - comb(n, b))%mod)