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:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
    
class modint:#商をとるときはmodとdが互いに素であること
    def __init__(self,x,mod=1000000007): 
        self.x, self.mod= x%mod, mod

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

    def __add__(self, a):
        if isinstance(a, modint):a=a.x
        return (self.x+a)%self.mod

    def __radd__(self, a):return self.__add__(a)

    def __iadd__(self, a):
        self.x=self.__add__(a)
        return self

    def __sub__(self, a):
        if isinstance(a, modint):a=a.x
        return self.__add__(-a)
    
    def __rsub__(self, a):return (a-self.x)%self.mod

    def __isub__(self, a):
        return self.__iadd__(-a)

    def __mul__(self, c):
        if isinstance(c, modint):c=c.x
        return (self.x*(c%self.mod))%self.mod
    
    def __rmul__(self, c):return self.__mul__(c)
    
    def __imul__(self, c):
        self.x=self.__mul__(c)
        return self

    def __pow__(self,p):
        if isinstance(p, modint):p=p.x
        return pow(self.x,p,self.mod)
    
    def __ipow__(self,p):
        self.x=self.__pow__(p)
        return self

    def __truediv__(self, d):
        if isinstance(d, modint):d=d.x
        u,v,a,b=1,0,d,self.mod
        while b:
            t=a//b
            a-=t*b
            a,b,u,v=b,a,v,u-t*v
        if a!=1: print("not 素")
        return int((self.x*(u%self.mod))%self.mod)

    def __itruediv__(self, d):
        self.x=self.__truediv__(d)
        return self

    def __eq__(self, target):
        if isinstance(target, modint):
            return self.x==target.x
        return self.x==target%self.mod
 
def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    n,a,b = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列


    tot=pow(2,n,mod)-1
    fac1=1
    for i in range(n-a+1,n+1):
        fac1*=i
        fac1%=mod
    div1=1
    for i in range(1,a+1):
        div1*=i
        div1%=mod
    div1=pow(div1,mod-2,mod)
    c1=fac1*div1%mod

    fac2=1
    for i in range(n-b+1,n+1):
        fac2*=i
        fac2%=mod
    div2=1
    for i in range(1,b+1):
        div2*=i
        div2%=mod
    div2=pow(div2,mod-2,mod)
    c2=fac2*div2%mod
    print((tot-c1-c2)%mod)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from functools import reduce
def comb(n, r, mod=10 ** 9 + 7):
    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())
mod = 1000000007
print((pow(2, n, mod) - 1 - comb(n, a, mod) - comb(n, b, mod)) % mod)

Submission status: Accepted

Solution code:
def n_comb_k( n, k, MOD ):
    chld = 1
    prnt = 1
    for r in range( 1, k + 1 ):
        chld = ( chld * ( n - k + r ) ) % MOD
        prnt = ( prnt * r ) % MOD
    return chld * pow( prnt, MOD - 2, MOD ) % MOD

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

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

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

print( ans )

Submission status: Accepted

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

def combinations_mod(n, r, mod=1000000007):
    """Returns nCr in mod."""
    r = min(r, n - r)
    combs = 1
    for i, j in zip(range(n - r + 1, n + 1), range(1, r + 1)):
        combs *= (i % mod) * pow(j, mod - 2, mod)
        combs %= mod
    return combs

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

Submission status: Accepted

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

mod = 10**9+7
ans = pow(2,n,mod)-1

nca = 1
ncb = 1

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

ans -= nca+ncb
print(ans%mod)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def combinations_mod(n, r, mod=1000000007):
    """Returns nCr in mod."""
    r = min(r, n - r)
    combs = 1
    for i, j in zip(range(n - r + 1, n + 1), range(1, r + 1)):
        combs *= (i % mod) * pow(j, mod - 2, mod)
        combs %= mod
    return combs


def main():
    n, a, b = NMI()
    all = pow(2, n, MOD) - 1
    ans = all - combinations_mod(n, a) - combinations_mod(n, b)
    ans %= MOD
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
mod = 10**9 + 7
n,a,b=map(int,input().split())
k=a
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 binomial_coefficients(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans
d=binomial_coefficients(n, a)
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 binomial_coefficients(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans
e=binomial_coefficients(n, b)
c = pow(2,n%(10**9+7), 10**9+7)
print((c-d-e-1)%(10**9+7))

Submission status: Accepted

Solution code:
def combinations_mod(n, r, mod=1000000007):
    """Returns nCr in mod."""
    r = min(r, n - r)
    combs = 1
    for i, j in zip(range(n - r + 1, n + 1), range(1, r + 1)):
        combs *= (i % mod) * pow(j, mod - 2, mod)
        combs %= mod
    return combs


def main():
    n, a, b = [int(x) for x in input().split()]
    mod = 1000000007
    total = pow(2, n, mod) - 1
    ans = total - combinations_mod(n, a) - combinations_mod(n, b)
    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def combinations_mod(n, r, mod=1000000007):
    """Returns nCr in mod."""
    r = min(r, n - r)
    combs = 1
    for i, j in zip(range(n - r + 1, n + 1), range(1, r + 1)):
        combs *= i * pow(j, mod - 2, mod)
        combs %= mod
    return combs


def main():
    n, a, b = [int(x) for x in input().split()]
    mod = 1000000007
    total = pow(2, n, mod) - 1
    ans = total - combinations_mod(n, a) - combinations_mod(n, b)
    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def combinations_mod(n, r, mod=1000000007):
    """Returns nCr in mod."""
    r = min(r, n - r)
    combs = 1
    for i, j in zip(range(n - r + 1, n + 1), range(1, r + 1)):
        combs = combs % mod * i % mod * pow(j, mod - 2, mod) % mod
    return combs


def main():
    n, a, b = [int(x) for x in input().split()]
    mod = 1000000007
    total = pow(2, n, mod) - 1
    ans = total - combinations_mod(n, a) - combinations_mod(n, b)
    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def power(n,p,m):
    if p == 0:
        return 1
    elif p%2:
        return (power(n,p-1,m)*n)%m
    else:
        return ((power(n,p//2,m))**2)%m

def choose(n,t,m):
    x, y = 1, 1
    for i in range(t):
        x = x * (n - i) % m
        y = y * (i + 1) % m
    return x * power(y,m-2,m) % m


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


flower = (power(2,n,m)-1) - choose(n,a,m) - choose(n,b,m)
while flower < 0:
    flower += m

print(flower)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

def modpow(a: int, p: int, mod: int) -> int:
    # return a**p (mod MOD) O(log p)
    res = 1
    while p > 0:
        if p & 1 > 0:
            res = res * a % mod
        a = a**2 % mod
        p >>= 1
    return res

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 = modpow(denominator, MOD-2, MOD)
    return numerator * d
    
n,a,b=map(int,input().split())

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

Submission status: Accepted

Solution code:
def modpow(a, n, p):
    if n == 0:
        return 1
    elif n == 1:
        return a % p
    if n % 2 == 1:
        return (a * modpow(a, n-1, p)) % p
    tmp = modpow(a, n//2, p)
    return (tmp * tmp) % p


def modfactrial(a, p):
    ret = 1
    for i in range(a, 1, -1):
        ret = ret * i % p
    return ret


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

    # まずは繰り返し2乗法によって全部の組み合わせを求める
    # すべての組み合わせは、花を選ぶ/選ばないで組み合わせを決めれる

    ans = (modpow(2, n, mod) - 1) % mod

    # a本選んだときの数を引く
    c_a = 1
    for i in range(n, n-a, -1):
        c_a *= i
        c_a %= mod
    c_a *= modpow(modfactrial(a, mod), mod-2, mod)
    ans -= c_a
    ans %= mod

    # b本選んだときの数を引く
    c_b = 1
    for i in range(n, n-b, -1):
        c_b *= i
        c_b %= mod
    c_b *= modpow(modfactrial(b, mod), mod-2, mod)
    ans -= c_b
    ans %= mod

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import factorial


def modpow(a, n, p):
    if n == 0:
        return 1
    elif n == 1:
        return a % p
    if n % 2 == 1:
        return (a * modpow(a, n-1, p)) % p
    tmp = modpow(a, n//2, p)
    return (tmp * tmp) % p


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

    # まずは繰り返し2乗法によって全部の組み合わせを求める
    # すべての組み合わせは、花を選ぶ/選ばないで組み合わせを決めれる

    ans = (modpow(2, n, mod) - 1) % mod

    # a本選んだときの数を引く
    c_a = 1
    for i in range(n, n-a, -1):
        c_a *= i
        c_a %= mod
    c_a *= modpow(factorial(a), mod-2, mod)
    ans -= c_a
    ans %= mod

    # b本選んだときの数を引く
    c_b = 1
    for i in range(n, n-b, -1):
        c_b *= i
        c_b %= mod
    c_b *= modpow(factorial(b), mod-2, mod)
    ans -= c_b
    ans %= mod

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

def modpow(a, n, p):
    if n == 0:
        return 1
    elif n == 1:
        return a % p
    elif n%2 == 1:
        return (a * modpow(a, n-1, p)) % p
    else:
        temp = modpow(a, n//2, p)
        return (temp * temp) % p

def n_permutations(n, a):
    p = 7 + pow(10, 9)
    ans = 1
    for i in range(n-a+1, n+1):
        ans = ans * i
        ans = ans % p
    return ans

def permutations(a):
    p = 7 + pow(10, 9)
    ans = 1
    for i in range(1, a+1):
        ans = ans * i
        ans = ans % p
    return ans

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

ans = modpow(2, n, p) - 1
ans = ans - ((n_permutations(n, a) * modpow(permutations(a), (p-2), p))%p)
ans = ans - ((n_permutations(n, b) * modpow(permutations(b), (p-2), p))%p)

print(ans%p)

Submission status: Accepted

Solution code:
from math import factorial


def modpow(a, n, p):
    if n == 0:
        return 1
    elif n == 1:
        return a % p
    if n % 2 == 1:
        return (a * modpow(a, n-1, p)) % p
    tmp = modpow(a, n//2, p)
    return (tmp * tmp) % p


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

    # まずは繰り返し2乗法によって全部の組み合わせを求める
    # すべての組み合わせは、花を選ぶ/選ばないで組み合わせを決めれる

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

    # a本選んだときの数を引く
    c_a = 1
    for i in range(n, n-a, -1):
        c_a *= i
        c_a %= mod
    c_a *= modpow(factorial(a), mod-2, mod)
    ans -= c_a
    ans %= mod

    # b本選んだときの数を引く
    c_b = 1
    for i in range(n, n-b, -1):
        c_b *= i
        c_b %= mod
    c_b *= modpow(factorial(b), mod-2, mod)
    ans -= c_b
    ans %= mod

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

    def choose(n, a, mod=MOD):
        x, y = 1, 1
        for i in range(a):
            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())

    ans = pow(2, N, MOD) - choose(N, A) - choose(N, B) - 1  # 0本の組み合わせを差し引く
    ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
c=d=1
e=0
m=10**9+7
for i in range(1,b+1):
    c=(c*(n+1-i))%m
    d=(d*i)%m
    if i==a or i==b:
        e+=c*pow(d,m-2,m)%m
print((pow(2,n,m)-e-1)%m)

Submission status: Accepted

Solution code:
import sys
import numpy as np

m = 10**9+7

def syuke(n,r):
    ue=1
    sit=1
    r =min(r,n-r)
    for i in range(r):
        ue = (ue*(n-i))%m
        sit = (sit*(i+1))%m
    return(ue*pow(sit,(m-2),m))

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

syu = 0
if n<3:
    print(0)
    sys.exit()
syu = pow(2,n,m)-1
syu -= syuke(n,a)%m
syu -= syuke(n,b)%m
print(syu%m)

Submission status: Accepted

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

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

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

A = comb( n, a )
B = comb( n, b )
print( ( N - A - B ) % mod )

Submission status: Accepted

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

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

n = pow( 2, N, MOD ) - 1
a = comb( N, A )
b = comb( N, B )
print(( n - a - b ) % MOD )

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

def comb(n, a, mod):
    ans = 0
    u = 1
    for i in range(a):
        u *= n-i
        u %= mod
    d = 1
    for i in range(a):
        d *= i+1
        d %= mod
    ans = u*pow(d, mod-2, mod) % mod
    return ans
ans -= comb(n, a, mod)
ans -= comb(n, b, mod)
ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import math
# 検索用タグ、繰り返し2乗法、膨大な組み合わせ、フェルマーの小定理
# https://math.nakaken88.com/textbook/cp-binary-exponentiation-and-recursive-function/
# ちなみに、pythonでは(pow())にて実装済みなので、自作不要。
# https://note.com/keyem/n/n526ee14fe3de
# 「繰り返し2乗法」はプログラム数学とでも呼ぶべき分野(高校、大学数学とは多分違う。「プログラムに対してのみ」効果があるので・・)
# --------------------------------------------------
# この問題のポイントは・・「組み合わせをXの(y)-2乗」という形に変換する事。
# https://img.atcoder.jp/abc156/editorial.pdf
# https://qiita.com/ofutonfuton/items/92b1a6f4a7775f00b6ae
# 10億種類の花から10万個を選ぶ・・というのは処理速度的に無理だが、
# 「Xの?乗」という形に変換できれば、繰り返し2乗法で高速に計算できる!(pythonならpow()を使うだけでOK)
# --------------------------------------------------

# 膨大な組み合わせ(10億C10万とか)の数を求める関数。
def cmb(n, r):
    mod = 10**9+7
    ans = 1
    for i in range(r):
        ans *= n-i
        ans %= mod
    for i in range(1, r+1):
        ans *= pow(i, mod-2, mod)
        ans %= mod
    return ans

def resolve():

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

    # 10の9乗+7を算出しておく。
    div = pow(10, 9) + 7

    # 合計 = a,bを無視した総パターン数 - patternAの数 - patternbの数
    total = pow(2, n, div) - 1 - cmb(n, a) - cmb(n, b)
    print(total % div)

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4 1 3"""
        output = """7"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """1000000000 141421 173205"""
        output = """34076506"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

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

N = pow(2,n,mod)-1
A = combination(n,a)
B = combination(n,b)
print((N-A-B)%mod)

Submission status: Accepted

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n,a,b=n1()

def comb(n,k):
    nCk = 1
    MOD = 10**9+7

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= MOD

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

MOD = 10**9+7
a1=comb(n, a)
b1=comb(n, b)
ans=pow(2,n,MOD)-a1-b1-1
print(ans%MOD)

Submission status: Accepted

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

def nCr(n_, r_, m_):
  c = min(r_ , n_ - r_)
  bunshi = 1
  bunbo = 1
  for i in range(1,c+1):
    bunshi = bunshi * (n_+1-i) % m_
    bunbo = bunbo * i % m_
  return bunshi * pow(bunbo, m_-2, m_) % m_


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

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
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


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

Submission status: Accepted

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

def cmb(n, r, p):
	if (r < 0) or (n < r):
		return 0
	s = 1
	for i in range(r):
		s = (s * (n-i)) % p
	return (s * factinv[r]) % p

p = 10 ** 9 + 7
N = 2 * 10 ** 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)

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

Submission status: Accepted

Solution code:
from functools import reduce

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

mod=10**9+7
def nCk(n,k):
    if n<k or (n<0 or k<0):
        return 0
    k=min(k,n-k)
    up,down=1,1
    for i in range(k):
        up=up*(n-i)%mod
        down=down*(i+1)%mod
    return up*pow(down,mod-2,mod)%mod

all=pow(2,n,mod)
nCa=nCk(n,a)
nCb=nCk(n,b)

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

Submission status: Accepted

Solution code:
from functools import reduce

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

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

all=pow(2,n,mod)
nCa=nCk(n,a)
nCb=nCk(n,b)

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

Submission status: Accepted

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


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


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

Submission status: Accepted

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

def inverse(n, mod):
    return pow(n, mod - 2, mod)

def cmb(n, r, mod):
    p, q = 1, 1
    for i in range(r):
        p = p * (n - i) % mod
        q = q * (i + 1) % mod
    return p * inverse(q, mod) % mod

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

Submission status: Accepted

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

A = 1
for i in range(1,a+1):
  A = (A*(n-i+1))%(10**9+7)
  x = pow(i,10**9+5,10**9+7)
  A *= x

B = 1
for i in range(1,b+1):
  B = (B*(n-i+1))%(10**9+7)
  y = pow(i,10**9+5,10**9+7)
  B *= y

ans = ans-A-B
if ans < 0:
  ans = ans+10**9+7
ans = int(ans%(10**9+7))
print(ans)

Submission status: Accepted

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

A = 1  
for i in range(a):
  A = A*(N-i)*pow(i+1,MOD-2,MOD)%MOD

B = 1  
for i in range(b):
  B = B*(N-i)*pow(i+1,MOD-2,MOD)%MOD

alll = pow(2,N,MOD) -1
#nota = cmb(N,a,MOD)
#notb = cmb(N,b,MOD)
ans = alll - (A+B)
ans = ans%MOD
print(ans)

Submission status: Accepted

Solution code:
def inverse(n, mod):
    return pow(n, mod - 2, mod)

def cmb(n, r, mod):
    p, q = 1, 1
    for i in range(r):
        p = p * (n - i) % mod
        q = q * (i + 1) % mod
    return p * inverse(q, mod) % mod

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    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

    total = pow(2, n, mod) - 1
    res = total - cmb_mod(n, a, mod) - cmb_mod(n, b, mod)
    print(res % mod)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
MOD = 10**9+7

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())
ans = pow(2, n, MOD) - comb(n, a) - comb(n, b) - 1
print(ans%MOD)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0

c = Factorial(max(a, b) + 1, MOD)

def combination(n, r): #nCrを求める
    if n - r < r:
        r = n - r
    tmp = 1
    for i in range(n - r + 1, n + 1):
        tmp *= i
        tmp %= MOD
    tmp *= c.ifactorial(r)
    return tmp

MOD = 10 ** 9 + 7


ans = pow(2, n, MOD) - 1 #選ばないのを除く

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

print (ans)

Submission status: Accepted

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

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

#nCx(mod)
def comb_speed(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)
    return (rec*rec2)%mod

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

Submission status: Accepted

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

def solve():
    n, a, b = map(int, input().split())
    mod = 10**9+7
    ans = pow(2,n,mod)-comb_mod(n,a)-comb_mod(n,b)-1
    ans %= mod
    return ans
print(solve())

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
from functools import reduce

stdin = open(0)
N, A, B = map(int, stdin.read().split())
MOD = 10 ** 9 + 7


def f(A):
    num = reduce(lambda x, y: x * y % MOD, range(N, N - A, -1))
    den = reduce(lambda x, y: x * y % MOD, range(1, A + 1))
    return num * pow(den, MOD - 2, MOD) % MOD


answer = pow(2, N, MOD) - f(A) - f(B) - 1
answer %= MOD
print(answer)

Submission status: Accepted

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

ans = 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*pow(fac, mod-2, mod)%mod

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

print(ans%mod)

Submission status: Accepted

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


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


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

Submission status: Accepted

Solution code:
def comb(n, k, mod):

    m = 1
    for i in range(n, n - k, -1):
        m = m * i % mod

    n = 1
    for i in range(1, k + 1):
        n = n * i % mod

    return (m * pow(n, mod - 2, mod) % mod)


def main():

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

MOD = int(1e9) + 7

s = pow(2, n, MOD)-1

def cbn(n, a, MOD):
    x = 1
    for i in range(a):
        x = (x * (n-i)) % MOD

    y = math.factorial(a) % MOD
    return x * pow(y, MOD-2, MOD) %MOD

s = (s- cbn(n, a, MOD)) %MOD
s = (s- cbn(n, b, MOD)) %MOD


print(s)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from math import factorial
def C(n, m, P):
    c = 1
    for i in range(m):
        c *= n-i
        c %= P
    m = factorial(m)%P
    return c*pow(m, P-2, P)%P

def main():
    P = int(1e9)+7
    n, a, b = map(int, readline().split())
    print((pow(2, n, P)-1-C(n, a, P)-C(n, b, P))%P)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

def comb(n, r):
    p, q = 1, 1
    for i in range(r):
        p = p*(n-i) % mod
        q = q*(r-i) % mod
        #print(p,q)
    return p * pow(q, mod-2, mod)%mod
    
print((ans- comb(n, a) - comb(n, b)) % mod)

Submission status: Accepted

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


res=0
pat=1
for i in range(0,n+1):
  res=pat
  if i==a:
    maxx-=res
  if i==b:
    maxx-=res
    break
  #res=patとすれば,print(res)でnCkが求まる
  pat*=(n-i)*pow(i+1,mod-2,mod)
  pat%=mod
  
print(maxx%mod)