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:
from functools import reduce

def combinations_count_mod(n, r, m):
    num = reduce(lambda x, y: x * y % m, range(n, n - r, -1))
    den = reduce(lambda x, y: x * y % m, range(1, r + 1))
    return num * pow(den, m - 2, m) % m

N, A, B = map(int, input().split())

MOD = 10 ** 9 + 7
 
answer = pow(2, N, MOD) - 1 - combinations_count_mod(N, A, MOD) - combinations_count_mod(N, B, MOD)
answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
from functools import reduce

N, A, B = map(int, input().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) - 1 - f(A) - f(B)
answer %= MOD
print(answer)

Submission status: Accepted

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

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

def cmb(n, k):
    numerator = 1
    denominator = 1

    for i in range(k):
        numerator *= n-i
        numerator %= mod
        denominator *= i+1
        denominator %= mod
    return numerator*pow(denominator, mod-2, mod) % mod


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

Submission status: Accepted

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

def combi( n, r ):
  r = min( n - r, r )
  a = 1
  b = 1
  for i in range( 1, r + 1 ):
    a = ( a * ( n - i + 1 )) % MOD
    b = ( b * i ) % MOD

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

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

Submission status: Accepted

Solution code:
def cmb(s, t, r):
    x = 1
    y = 1
    for i in range(t):
        x = (x*(s-i))%r
        y = (y*(i+1))%r
 
    y_inverse = pow(y, r-2, r)
    return (x*y_inverse)%r


# inputを高速化する。
import sys
input = sys.stdin.readline

rid = 10 ** 9 + 7

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

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

ans -= cmb(n, a, rid) + cmb(n, b, rid)

print(ans % rid)

Submission status: Accepted

Solution code:

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

r = 10**9 + 7

def comb(s, t):
    x = 1
    y = 1
    for i in range(t):
        x = (x*(s-i))%r
        y = (y*(i+1))%r

    y_inverse = pow(y, r-2, r)
    return (x*y_inverse)%r

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

ans = (total-comb(n,a)-comb(n,b))%r

print(ans)

Submission status: Accepted

Solution code:
from functools import reduce

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

mod = 10 ** 9 + 7

def combi(c):
    numerator = reduce(lambda x, y: x * y % mod, range(n, n - c, -1))
    denominator = reduce(lambda x, y: x * y % mod, range(1, c + 1))
    return numerator * pow(denominator, mod - 2, mod) % mod

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

def calc(n,r):
    x = 1
    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

n, a, b = map(int, input().split())
res = pow(2, n, mod) - 1
 
for i in [a, b]:
    res -= calc(n, i)
print(res % mod)

Submission status: Accepted

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


all_c = pow(2, n, MOD)-1
a_c = 1
b_c = 1
for i in range(n-a+1, n+1):
    a_c *= i
    a_c %= MOD
for i in range(1, a+1):
    a_c *= pow(i, MOD-2, MOD)
    a_c %= MOD
for i in range(n-b+1, n+1):
    b_c *= i
    b_c %= MOD
for i in range(1, b+1):
    b_c *= pow(i, MOD-2, MOD)
    b_c %= MOD

ans = (all_c - a_c - b_c) % MOD
print(ans)

Submission status: Accepted

Solution code:
MOD=10**9+7
mod=MOD
def comb(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%MOD
    for i in range(2,k+1):
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        ans=ans*(n-k+i)*inv[i]%MOD
    return ans
Num,a,b=map(int,input().split())
Max=pow(2,Num,mod)
A=comb(Num,a)
B=comb(Num,b)
print((Max-A-B)%mod-1)

Submission status: Accepted

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def power(x, y, p):
    res = 1  # Initialize result

    x = x % p  # Update x if it is
    # more than or equal to p

    while (y > 0):

        # If y is odd,
        # multiply x with result
        if (y & 1):
            res = (res * x) % p

            # y must be even now
        y = y >> 1  # y = y/2
        x = (x * x) % p

    return res
def ncr(n, r, p):
    # initialize numerator
    # and denominator
    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

n,a,b = MAP()

print(int((power(2, n, mod)-1-ncr(n, a, mod)-ncr(n, b, mod))%mod))

# print(ncr(10**9,10**5 ,10**9+7))

Submission status: Accepted

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

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

Submission status: Accepted

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

p=10**9+7
ans1=1
ans2=1

for i in range(n-a+1,n+1):
    ans1*=i
    ans1%=p

for i in range(1,a+1):
    ans1*=pow(i,p-2,p)
    ans1%=p
    
for i in range(n-b+1,n+1):
    ans2*=i
    ans2%=p

for i in range(1,b+1):
    ans2*=pow(i,p-2,p)
    ans2%=p

print((pow(2,n,p)-ans1-ans2-1)%p)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def framod(x,y,p=10**9+7):
  for i in range(x+1,y+1):
    x = (x*i)%p
  return x
    
#########################################

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

ans=0
for i in [a,b]:
  upper = framod(n-i+1,n,p)
  lower = framod(1,i,p)
  ret = (upper*pow(lower,p-2,p))%p
  ans = (ans+ret)%p
print((pow(2,n,p)-ans-1)%p)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = pow(10, 9) + 7
 
def comb(N, x):
    X = 1
    for i in range(N-x+1, N+1):
        X = X * i % mod
    Y = 1
    for j in range(1, x+1):
        Y = Y * j % mod
    Ym = pow(Y, mod-2, mod)
    return X * Ym

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

Submission status: Accepted

Solution code:
def comb(x, y):
    temp1 = 1
    temp2 = 1
    for i in range(x, x-y, -1):
        temp1 = temp1 * i % mod
    for i in range(1, y+1):
        temp2 = temp2 * i % mod
    temp = pow(temp2, mod-2, mod)
    return temp1 * temp % mod
n,a,b = map(int, input().split())
mod = 10 ** 9 + 7
total = pow(2, n, mod) - 1
a = comb(n, a)
b = comb(n, b)
print((total - a - b) % mod)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
MOD=10**9+7
total=(pow(2,n,MOD)-1)%MOD
na=1
nb=1
atotal=1
btotal=1
for i in range(a):
    na=(na*(n-i))%MOD
for i in range(b):
    nb=(nb*(n-i))%MOD
for i in range(1,a+1):
    atotal=(atotal*i)%MOD
for i in range(1, b + 1):
    btotal = (btotal * i) % MOD
atotal=pow(atotal,MOD-2,MOD)%MOD
btotal=pow(btotal,MOD-2,MOD)%MOD
ans=total%MOD-(na*atotal)%MOD-(nb*btotal)%MOD
print(ans%MOD)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

mod = 1000000007
ruiseki1 = 1
for i in range(a):
    ruiseki1 = (ruiseki1*(n-i)*pow(i+1, mod-2, mod)) %mod

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

Submission status: Accepted

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

modular = 1000000007

mod_value = pow(2, n, modular)
all_combination_modular = mod_value - 1 if mod_value != 0 else modular - 1

# print(all_combination_modular)

p = 1
q = 1
for i in range(a):
    p = p * (n - i) % modular
    q = q * (i + 1) % modular

mod_a = p * pow(q, modular - 2, modular) % modular

p = 1
q = 1
for i in range(b):
    p = p * (n - i) % modular
    q = q * (i + 1) % modular

mod_b = p * pow(q, modular - 2, modular) % modular

result = all_combination_modular - mod_a - mod_b

while True:
    if result < 0:
        result += modular
    else:
        break
print(result)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000000)
p = 10**9+7
n, a, b = map(int, input().split())
fact=[0,1]
for i in range(2,max(a,b)+1):
  fact.append(fact[-1]*i % p)

def exp(y,x):
  xbin=str(bin(x))[2:]
  ans=1
  yl=[0]*(len(xbin)+1)
  yl[0]=y
  yl[1]=y**2
  for d,i in enumerate(xbin[::-1],start=0):
    if d > 1:
      yl[d]=yl[d-1]**2%p
    if i == "1":
      ans=(ans*yl[d])%p
  return ans%p

def ff(n,ca):
  if ca == 1:
    return n
  return n*ff(n-1,ca-1)%p
ssum=exp(2,n)-1
asum=ff(n,a)*exp(fact[a],p-2)%p
bsum=ff(n,b)*exp(fact[b],p-2)%p
print((ssum-asum-bsum)%p)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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

nca %= mod
ncb %= mod


ans = pow(2, n, mod) - nca - ncb - 1
# print(pow(2, n, mod), nca, ncb)
while ans < 0:
    ans += mod
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit

MOD = 10 ** 9 + 7


def cmd(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():
    n, a, b = map(int, stdin.readline().split())

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

    ans -= cmd(n, a, MOD)
    ans -= cmd(n, b, MOD)

    print(ans % MOD)


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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import combinations
def run():
    n,a,b = map(int, input().split())
    mod = 10 ** 9 + 7
    S = 0
    S += pow_mod(2, n, mod)
    S += (-1) % mod

    sub = 0
    for _a in (a,b):
        up = -1
        down = 1
        for i in range(_a):
            up *= n - i
            up %= mod
            down *= i + 1
            down %= mod
        down = pow_mod(down, mod - 2, mod)
        sub += (up * down) % mod

    S += sub % mod
    print(S % mod)
def pow_mod(n, k, mod):
    res = 1
    nk = n
    while True:
        if k // 2 >= 1:
            if k % 2 == 1:
                res = (res * nk) % mod
            nk = (nk ** 2) % mod
            k = k // 2
        else:
            break
    return (nk * res) % mod


if __name__ == "__main__":
    run()

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:
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:
import sys
from functools import reduce

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N, A, B = lr()

answer = pow(2, N, MOD) - 1 

def cmb(n, r): 
    X = reduce(lambda x, y: x * y % MOD, range(n, n - r, -1))
    Y = reduce(lambda x, y: x * y % MOD, range(1, r + 1)) 
    return X * pow(Y, MOD - 2, MOD) % MOD

answer -= cmb(N, A) + cmb(N, B)
print(answer % MOD)

Submission status: Accepted

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

S = [0]*(2*10**5+2)
S[1] = 1
for i in range(2, 2*10**5+1):
    S[i] = S[MOD%i]*(MOD-int(MOD/i))%MOD
temp = 1
for i in range(min(A, N-A)):
    temp *= (N-i)*S[i+1]
    temp %= MOD
ans -= temp
temp = 1
for i in range(min(B, N-B)):
    temp *= (N-i)*S[i+1]
    temp %= MOD
ans -= temp
print((ans-1)%MOD)

Submission status: Accepted

Solution code:
def main():
  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)
  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    for i in [a, b]:
        count -= modcomb(n, i, p)

    print(count % (10**9 + 7))


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
n,a,b = map(int,input().split())
mod = 10**9 + 7
s = pow(2,n,mod) - 1
a_ue = 1
a_shita = 1
b_ue = 1
b_shita = 1
for i in range(1,a+1):
    a_ue = a_ue * (n-i+1) % mod
    a_shita = a_shita * i % mod
a_tmp = a_ue * pow(a_shita,mod-2,mod) % mod
# pow(a_shita,mod-2,mod) で逆元を求める
for j in range(1,b+1):
    b_ue = b_ue * (n-j+1) % mod
    b_shita = b_shita * j % mod
b_tmp = b_ue * pow(b_shita,mod-2,mod) % mod
#print('j',j,b_ue,b_shita,b_ue/b_shita)
print((s-a_tmp-b_tmp)%mod)

Submission status: Accepted

Solution code:
# D - Bouquet

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

def choose(n, r):
    X = 1
    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

A = choose(n, a)
B = choose(n, b)
print((total - A - B) % MOD)

Submission status: Accepted

Solution code:
def calc(n, x):
    up = 1
    bottom = 1
    for i in range(x):
        up *= (n - i)
        up = up % mod
        bottom *= (i + 1)
        bottom = bottom % mod
    return (up * pow(bottom, mod - 2, mod)) % mod

mod = (10 ** 9) + 7

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

ans = pow(2, n, mod) - 1
for i in [a, b]:
    ans -= calc(n, i)
print(ans % mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools
import math
from operator import mul
from functools import reduce


MOD = 1000000007  # type: int

def combination_(n,k,mod):
    r = min(n-k,k)
    k = max(n-k,k)
    res = 1

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

    res = res % mod
    for i in range(1,r+1):
        res = res//i
    return res

def combination(n, r, mod):
    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

def solve(n: int, a: int, b: int):
    print((pow(2, n, MOD) - combination(n, a, MOD) - combination(n, b, MOD) - 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:
MOD = 10 ** 9 + 7
n, a, b = map(int, input().split())

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


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


A = comb(n, a)
B = comb(n, b)
print((all - A - B)%MOD)

Submission status: Accepted

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


def C(n, k):
    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


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

print(ans)

Submission status: Accepted

Solution code:
MOD = 1000000007

n,a,b = map(int,input().split())
A =1
B =1
for i in range(0,a,1):
    A = (A*(n-i)*pow((a-i),1000000005,1000000007))%MOD
for i in range(0,b,1):
    B = (B*(n-i)*pow((b-i),1000000005,1000000007))%MOD

print((pow(2,n,MOD) - A%MOD - B%MOD -1)%MOD)

Submission status: Accepted

Solution code:
def cmb(n,r,mod=10**9+7):
    if r<0 or r>n:return 0
    return g1[r]*g2[r]%mod


mod=10**9+7
n,a,b=map(int,input().split())
k=max(a,b)
g1=[1,n]
g2=[1,1]
inverse=[0,1]

for i,j in enumerate(range(n-1,((n-k+1)-1),-1)):
    i=i+2
    g1.append((g1[-1]*j)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1]%mod))

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

Submission status: Accepted

Solution code:
# Python3 function to  
# calculate nCr % p 
mod=pow(10,9)+7
def ncr(n, r, p): 
    # initialize numerator 
    # and denominator 
    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 
n,a,b=map(int,input().split())
ans=pow(2,n,mod)-1
ans =ans- ncr(n,a,mod)
ans += mod
ans =ans%mod
ans =ans -ncr(n,b,mod)+mod
ans=ans%mod
print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7


def f(n, r):
    X = 1
    Y = 1
    for i in range(r):
        X *= n - i    # nCr の分子
        X %= mod
        Y *= i + 1    # nCr の分母
        Y %= mod

    # フェルマーの小定理より (X/Y)%mod = X*Y^(mod - 2) % mod
    return X * pow(Y, mod - 2, mod) % mod


N, A, B = map(int, input().split())
res = pow(2, N, mod) - 1

for i in [A, B]:
    res -= f(N, i)

print(res % mod)

Submission status: Accepted

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

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

so=10**9+7

large=(pow(2,n,so)-1)

def kumiawase(n,r):
    over=1
    for i in range(r):
        over *= n-i
        over %= so
    under = math.factorial(r)
    return over * pow(under,so-2,so)

ajogai = kumiawase(n,a) % so
bjogai = kumiawase(n,b) % so
print((large - ajogai - bjogai + 2*so) % so)

Submission status: Accepted

Solution code:
def calc_pow(a, n, mod):
    rev_bin_n_str = bin(n)[2:][::-1]
    val = 1
    base_a = a
    for b in rev_bin_n_str:
        if b == '1':
            val *= base_a
            val %= mod
        base_a *= base_a
        base_a %= mod
    return val


def ext_euc(a, b):
    # return (x, y, gcd(a, b)) such that ax + by = gcd(a, b)
    # assumed a > b
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    if a > mod:
        x, _, _ = ext_euc(a, mod)
    else:
        _, x, _ = ext_euc(mod, a)
    return x % mod


def calc_comb(n, k, mod):
    if k > n / 2:
        return calc_comb(n, n - k, mod)
    comb = 1
    for i in range(k):
        comb *= (n - i)
        comb %= mod
        comb *= mod_inv((k - i), mod)
        comb %= mod
    return comb


def main():
    MOD = 10**9 + 7
    n, a, b = list(map(int, input().split(' ')))
    ans = calc_pow(2, n, MOD) - calc_comb(n, a, MOD) - calc_comb(n, b, MOD) - 1
    print(ans % MOD)


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

nPa = 1
fac_a = 1
nPb = 1
fac_b = 1

for i in range(1, b + 1):
    if i <= a:
        nPa = nPa * (n - i + 1) % mod
        fac_a = fac_a * i % mod
    
    nPb = nPb * (n - i + 1) % mod
    fac_b = fac_b * i % mod

nCa = nPa % mod * pow(fac_a, mod - 2, mod) % mod
nCb = nPb % mod * pow(fac_b, mod - 2, mod) % mod

ans -= nCa + nCb

print(ans % mod)

Submission status: Accepted

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

for i in [a, b]:
    total -= choose(n, i)

print(total%mod)

Submission status: Accepted

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

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

def mod_comb(n,k,p):
    if n<0 or k<0 or n<k:
        return 0
    if n==0 or k==0:
        return 1
    a = 1
    b = 1
    for i in range(k):
        a = (a*((n-i)%p))%p
        b = (b*((i+1)%p))%p
    return (a*pow(b,p-2,p))%p

x = mod_comb(n, a, mod)
y = mod_comb(n, b, mod)
total = (total-x-y)%mod

print(total)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def cmb(a, b, mod):
    m, n = 1, 1
    b = min(b, a-b)
    for i in range(1, b+1):
        m *= (a-i+1)
        m %= mod
        n *= i
        n %= mod
    return m * pow(n, mod-2, mod) % mod
def main():
    n, a, b = map(int, input().split())
    mod = 10 ** 9 + 7
    total = pow(2, n, mod) - 1
    cmb1 = cmb(n, a, mod)
    cmb2 = cmb(n, b, mod)
    ans = total - cmb1 - cmb2
    ans %= mod
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

cax = 1
cay = 1
for i in range(a):
    cax *= (n-i) % mod
    cax %= mod
    cay *= (i+1) % mod
    cay %= mod

cbx = 1
cby = 1
for i in range(b):
    cbx *= (n-i) % mod
    cby *= (i+1) % mod
    cbx %= mod
    cby %= mod

ans -= cax * pow(cay, mod - 2, mod)
ans -= cbx * pow(cby, mod - 2, mod)
print(ans % mod)

Submission status: Accepted

Solution code:
mod=10**9+7
n,a,b=[int(x) for x in input().rstrip().split()]

def modpow(a,n):
  if n<1:
    return 1
  ans=modpow(a,n//2)
  ans=(ans*ans)%mod
  if n%2==1:
    ans*=a
  return ans%mod

def conb(n,i):
  inv,ans=1,1
  for j in range(1,i+1):
    ans=ans*(n-j+1)%mod
    inv=inv*j%mod
  return (ans*modpow(inv,mod-2))%mod

ans_n=pow(2,n,mod)-1
ans_a=conb(n,a)
ans_b=conb(n,b)

print((ans_n-ans_a-ans_b)%mod)

Submission status: Accepted

Solution code:
# coding: utf-8
MOD = 10**9+7

# 二分累積法による a^n mod の計算
def modpow(a, n):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % MOD
        a = a * a % MOD
        n >>= 1
    return res

# nCr mod.p (n <= 10**6)
MAX = 1000010
fac = [0] * MAX 
finv = [0] * MAX
inv = [0] * MAX
def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD//i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD
# より高速化が必要な場合
def COM(n, k):
    res = 1
    for i in range(k):
        res = res * (n-i) % MOD
    return res * finv[k] % MOD

COMinit()
n, a, b = map(int, input().split())
tot = modpow(2,n) - 1
ans = (tot - COM(n,a) - COM(n,b)) % MOD
print(ans)

Submission status: Accepted

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N, A, B = lr()
answer = pow(2, N, MOD) - 1  # ここから苦手なものを引く

# nCaのaが小さい場合
def cmb(n, r): # nCr
    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

answer -= cmb(N, A) + cmb(N, B)
print(answer % MOD)
# 50

Submission status: Accepted

Solution code:
import math

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

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

c_a_x = 1
c_a_y = 1
for i in range(a):
    c_a_x = c_a_x * (n-i) % mod
    c_a_y = c_a_y * (i+1) % mod

c_a = c_a_x * pow(c_a_y,mod-2,mod) % mod

c_b_x = 1
c_b_y = 1
for i in range(b):
    c_b_x = c_b_x * (n-i) % mod
    c_b_y = c_b_y * (i+1) % mod

c_b = c_b_x * pow(c_b_y,mod-2,mod) % mod

print((c_all - c_a - c_b) % mod)

Submission status: Accepted

Solution code:
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

    def combination2(self, k, r):
        """kCrを求める O(r) kが大きいが、r <= nを満たしているときに使用"""
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.MOD
        return (res * self.inv_fact[r]) % self.MOD


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

all_ptn =pow(2, n, MOD)
a_ptn = comb.combination2(n, a)
b_ptn = comb.combination2(n, b)

ans = (all_ptn - (a_ptn + b_ptn) - 1) % MOD
print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7

def modpow(a,n):
  if n<1:
    return 1
  ans=modpow(a,n//2)
  ans=(ans*ans)%mod
  if n%2==1:
    ans*=a
  return ans%mod

def conb(n,i):
  inv,ans=1,1
  for j in range(1,i+1):
    ans=ans*(n-j+1)%mod
    inv=inv*j%mod
  return (ans*modpow(inv,mod-2))%mod

n,a,b=map(int,input().split())
all_patterns=modpow(2,n)
a=a if n/2>a else n-a
b=b if n/2>b else n-b
print((all_patterns-conb(n,a)-conb(n,b)-1)%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

N, A, B = map(int, input().split())

tmp1 = pow(2, N, MOD) - 1 #1本以上の選び方

#計算量 log(m)くらい
def modinv(a, m): #mod. m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u


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

tmp2 = combination(N, A)
tmp3 = combination(N, B)

print ((tmp1 - tmp2 - tmp3) % MOD)

Submission status: Accepted

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

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

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