Problem:


Score : 400 points

Problem Statement

Akari has n kinds of flowers, one of each kind.

She is going to choose one or more of these flowers to make a bouquet.

However, she hates two numbers a and b, so the number of flowers in the bouquet cannot be a or b.

How many different bouquets are there that Akari can make?

Find the count modulo (10^9 + 7).

Here, two bouquets are considered different when there is a flower that is used in one of the bouquets but not in the other bouquet.

Constraints

All values in input are integers.

2 \leq n \leq 10^9

1 \leq a < b \leq \textrm{min}(n, 2 \times 10^5)

Input

Input is given from Standard Input in the following format:

n a b

Output

Print the number of bouquets that Akari can make, modulo (10^9 + 7). (If there are no such bouquets, print 0.)

Sample Input 1

4 1 3

Sample Output 1

7

In this case, Akari can choose 2 or 4 flowers to make the bouquet.

There are 6 ways to choose 2 out of the 4 flowers, and 1 way to choose 4, so there are a total of 7 different bouquets that Akari can make.

Sample Input 2

1000000000 141421 173205

Sample Output 2

34076506

Print the count modulo (10^9 + 7).



Sample input:
4 1 3


Sample output:
7

Submission status: Accepted

Solution code:
n,a,b=map(int, input().split())
MAX_NUM = 3*10**5
pr = 10**9+7
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
g=pow(2,n,pr)-1
t=1
for i in range(n,n-a,-1):
    t=t*i%pr
g-=t*finv[a]
t=1
for i in range(n,n-b,-1):
    t=t*i%pr
g-=t*finv[b]
print(g%pr)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

#　制約を考えないの組み合わせ数は重複組み合わせでわかる
# そこから、移動がk回のことを考え、0人の部屋が何個あるかで場合分け、全事象から引く。
#　全事象考える必要ない?

m, a, b = LI()
n = 2 * 10 ** 5
fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod


a_ret = 1
for i in range(m, m - a, -1):
    a_ret = a_ret * i % mod

a_ret = a_ret * inv[a] % mod


b_ret = 1
for i in range(m, m - b, -1):
    b_ret = b_ret * i % mod

b_ret = b_ret * inv[b] % mod

print((pow(2, m, mod) - a_ret - b_ret - 1) % mod)

Submission status: Accepted

Solution code:
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

n, a, b = map(int, input().split())
base = (pow(2, n) - 1) % M
inv_t = [0]+[1]
ns = [0, n % M]
max_ab = max(a, b)
min_ab = min(a, b)
for i in range(2,max_ab+1):
    inv_t += [inv_t[M % i] * (M - int(M / i)) % M]
    n -= 1
    ns += [(ns[-1] * n) % M]
aa = ns[a]
bb = ns[b]
for i in range(2,min_ab+1):
    aa = (aa * inv_t[i]) % M
for i in range(2,max_ab+1):
    bb = (bb * inv_t[i]) % M
print(((base - aa)%M - bb)%M)

Submission status: Accepted

Solution code:
import socket
import sys

hostnames = ['N551J', 'F551C', 'X553M']
input_file = 'd1.in'
if socket.gethostname() in hostnames:
    sys.stdin = open(input_file)


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


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


def solve():
    n, a, b = read_int_list()
    total = pow(2, n, mod)
    res = total - 1
    c = 1
    for i in range(b):
        c = (c * (n - i) * inv[i + 1]) % mod
        if i == a - 1:
            res -= c
    res -= c
    res %= mod
    return res


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod=10**9+7
def c(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod
def power(a,n):
    x = 1
    while n:
        if n & 1:
            x *= a%mod
        n >>= 1
        a *= a%mod
    return x
    
n,a,b=map(int,input().split())
ans=power(2,n)%mod-1-c(n,a)%mod-c(n,b)%mod
for _ in range(10):
    if ans<0:
        ans+=mod
print(ans)

Submission status: Accepted

Solution code:

def main():
    n, a, b = map(int, input().split())
    MOD = 10 ** 9 + 7
    ans = pow(2, n, MOD)
    e = 1
    f = 1
    for i in range(1,a+1):
        e *= (n - i + 1)
        f *= i 
        e %= MOD
        f %= MOD
    c = e * pow(f, MOD-2, MOD)
    e = 1
    f = 1
    for i in range(1,b+1):
        e *= (n - i + 1)
        f *= i 
        e %= MOD
        f %= MOD
    d = e * pow(f, MOD-2, MOD)
    ans -= (c + d)
    ans %= MOD
    print(ans-1)



if __name__ == "__main__":
    main()

Submission status: Accepted

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

def bi(x):
    o = []
    while x != 0:
        o.append(x%2)
        x //= 2
    return o

def modpow(m,n):
    o = bi(n)
    leo = len(o)
    p = [m]*leo
    for i in range(1,leo):
        a = p[i-1]
        a *= a
        a %= mod
        p[i] = a
    b = 1
    for i in range(leo):
        if o[i] != 1:
            continue
        b *= p[i]
        b %= mod
    return b

def combi(a,b):
    aa = a
    mom = 1
    child = 1
    for _ in range(1,b+1):
        mom *= aa
        aa -= 1
        mom %= mod
        child *= _
        child %= mod
    return mom * modpow(child,mod-2) % mod

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

Submission status: Accepted

Solution code:
def sq(a, b, mod):  # aのb乗を剰余,kは初期値#20191116-D-Knight
    if b == 0:
        return 1
    elif b % 2 == 0:
        return sq(a, b // 2, mod)**2 % mod
    else:
        return sq(a, b - 1, mod) * a % mod


def nCk(n, k, mod=10 ** 9 + 7):
    x = max(k, n - k)
    y = min(k, n - k)
    kkai = 1
    for i in range(2, y + 1):
        kkai = (kkai * i) % mod
    nkkai = 1
    for i in range(x + 1, n + 1):
        nkkai = (nkkai * i) % mod
    answer = sq(kkai, mod - 2, mod) * nkkai % mod
    return answer

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

def modpow(x, y):
    res = 1
    while y > 0:
        if y & 1:
            res = res*x % (10**9+7)
        x = x*x%(10**9+7)
        y >>= 1
        y = int(y)
    return res
ans = 0
ans -= nCk(n, b)
ans -= nCk(n, a)
ans -= 1
ans += modpow(2, n)
print((ans+10**9+7)%(10**9+7))

Submission status: Accepted

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

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

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

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

q = 1
for i in range(n,n-b,-1):
    q = q*i%mod

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


print((res-p-q)%mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

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


A = comb(n, a, p) % p
B = comb(n, b, p) % p

MAX = pow(2, n, p)-1

ans = MAX - A - B 
ans = ans%p

print(ans)

Submission status: Accepted

Solution code:
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

def cmb(n, r):
    x = 1
    for i in range(r):
        x = mul(x, n-i)
    return x * g2[r] % mod

NNN = (3*10**5)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
N, a, b = map(int, input().split())
print((power(2, N) - 1 - cmb(N, a) - cmb(N, b))%mod)

Submission status: Accepted

Solution code:

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


P = 10**9 + 7
N = 200001
inv_t = [0]+[1]
for i in range(2,N):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

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

def comb(x):
    res=1
    for i in range(n-x+1,n+1):
        res*=i
        res=res%mod
    for i in range(1,x+1):
        res*=inv_t[i]
        res=res%mod
    return res

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

Submission status: Accepted

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

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a


def combmod(n, k, mod):
    a=1
    for i in range(n-k+1,n+1):
        a*=i
        a%=mod
    c=framod(k, mod)
    return (a * pow(c, mod-2, mod)) % mod

if n>2:
    print((pow(2,n,mod)-1-combmod(n,a,mod)-combmod(n,b,mod)+mod)%mod)
elif n==2:
    print('0')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def power(val, n, mod):
    ret = 1
    while n:
        if n & 1:
            ret = (ret * val) % mod
        val = (val * val) % mod
        n = n >> 1
    return ret


def cmb(n, r, mod):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
            result = result % mod

    return result % mod


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

pow_val = power(2, n, 1000000007)
ans = pow_val - 1 - cmb(n, a, 1000000007) - cmb(n, b, 1000000007)

if ans >= 0:
    print(ans)
else:
    if ans + 1000000007 >= 0:
        print(ans + 1000000007)
    else:
        print(ans + (1000000007 * 2))

Submission status: Accepted

Solution code:
import math


P = (10**9) + 7

def ncr(n, r):
    """組み合わせ"""
    # 入山徳夫氏によるアルゴリズム
    r = min(r, n - r)
    # 桁が小さいときは直接 math.factorial を使ったほうが早い
    if n + r < 4000:
        return math.factorial(n) // math.factorial(n-r) // math.factorial(r)
    if r == 0:
        return 1
    if r == 1:
        return n
    numerator = list(range(n - r + 1, n + 1))
    denominator = list(range(1, r+1))
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] //= pivot
                denominator[k] //= pivot
    result = 1
    for k in range(r):
        result *= numerator[k]
        result %= P
    return result


def solv(n, a, b):
    ans = 2 ** n - ncr(n, a) - ncr(n, b) - 1
    return ans % P


if __name__ == "__main__":

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

    print(ans)

Submission status: Accepted

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


def modInverse(a, p):
    # calculates the modular multiplicative of a mod m.
    # (assuming p is prime).
    return modPow(a, p-2, p)


def modBinomial(n, k, p):
    # calculates C(n,k) mod p (assuming p is prime).

    numerator = 1  # n * (n-1) * ... * (n-k+1)
    for i in range(k):
        numerator = (numerator * (n-i)) % p

    denominator = 1  # k!
    for i in range(1, k+1):
        denominator = (denominator * i) % p

    # numerator / denominator mod p.
    return (numerator * modInverse(denominator, p)) % p


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

nn = modPow(2, n, mod)
nn = (nn+mod-1) % mod


ab = (modBinomial(n, a, mod) + modBinomial(n, b, mod)) % mod

ans = (nn-ab+mod) % mod

print(ans)

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

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

def cob(n,a):
	rr=1
	for i in range(n, n-a, -1):
		rr = (rr *i ) % mod
	
	r=1
	for i in range(1, a+1):
		r = (r *i ) % mod
	
	#ww=pow(r,-1,mod)
	ww=modinv(r, mod)
	ret = rr * ww
	return ret
	
	

def main():
	n, a , b = IN()
	
	mm=(pow(2,n,mod)-1)%mod
	ret=(mm-cob(n,a)-cob(n,b))%mod
	
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

def nCmMOD(A,B,Mod):
    num,den=1,1
    for i in range(B):
        num*=(A-i)
        den*=(i+1)
        num%=Mod
        den%=Mod
    return (num*pow(den,Mod-2,Mod))%Mod

A=nCmMOD(n,a,mod)
B=nCmMOD(n,b,mod)

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
An=power_func(2,n,mod)

print((An-1+mod*2-A-B)%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

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

def fact_mod(a):
  if a<=1:
    return 1
  else:
    return a*fact_mod(a-1)%MOD
  
def perm_mod(n,a):
  if a==1:
    return n
  else:
    return (n*perm_mod(n-1,a-1))%MOD

def inv_mod(a):
  return pow_mod(a,MOD-2)%MOD
  
def comb_mod(na,fa):
  ainv=inv_mod(fa)
  return (na*ainv)%MOD
  
num_all=pow_mod(2,n)-1
perm_na=perm_mod(n,a)
fact_a=fact_mod(a)
comb_na=comb_mod(perm_na,fact_a)
#print(perm_na,fact_a,comb_na)
perm_nb=perm_mod(n,b)
fact_b=fact_mod(b)
comb_nb=comb_mod(perm_nb,fact_b)
#print(perm_nb,fact_b,comb_nb)
#print(num_all,comb_na,comb_nb)
print((num_all-comb_na-comb_nb+MOD)%MOD)

Submission status: Accepted

Solution code:
p = 10 ** 9 + 7
N = (10 ** 5)*2 +10  # 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 cmb(n, r, p):
    mm = 1
    for i in range(n,n-r,-1):
        mm *= i
        mm %= p
    return mm*factinv[r]%p



def pwr(n,k): #nのk乗高速版 n^k
    mod = 10**9+7
    memo = chng2(k)
    lng = len(memo)

    li = [0 for i in range(lng-1)]
    li[0] = 1
    
    a = 2
    ans = 1
    for i in range(1,lng-1):
        li[i] = a
        a *= a
        a %= mod 
 
    for i in range(1,lng-1):
        if memo[-i]=='1':
            ans *= li[i]%mod

    return ans%mod

def chng2(n): #10進数nを2進数に変換(配列)
    ans = list(bin(n))
    return ans


mod = 10**9+7
N,A,B = map(int,input().split())
mm1 = pwr(2,N)
mm2 = cmb(N,A,mod)
mm3 = cmb(N,B,mod)

ans = mm1-mm2-mm3-1
if ans < 0:
    ans += mod

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
cma=1
a,b=min(a,b),max(a,b)
for i in range(1,a+1):
  cma=cma*(n-i+1)*pow(i,mod-2,mod)%mod
ans-=cma
if a==b:
  print(ans);exit()
for i in range(a+1,b+1):
  cma=cma*(n-i+1)*pow(i,mod-2,mod)%mod
print((ans-cma)%mod)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,a,b = inpl()
def calc(x):
    ret = 1
    for i in range(N-x+1,N+1):
        ret *= i
        ret %= mod

    for i in range(1, x+1):
        ret *= pow(i,mod-2,mod)
        ret %= mod

    return ret%mod

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

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
Mod=10**9+7
c=max(a,b)
f=[1]*(c+1)
g=[n]*(c+1)
for i in range(2,c+1):
    f[i]=f[i-1]*i%Mod
    g[i]=g[i-1]*(n-i+1)%Mod
def f_inv(i):
    return pow(f[i],Mod-2,Mod)
def h(i):
    return g[i]*f_inv(i)%Mod
Ans=pow(2,n,Mod)-h(a)-h(b)-1
print(Ans%Mod)

Submission status: Accepted

Solution code:
N,A,B = map(int,input().split())
mod = 10**9+7
X = 210000
inv_t = [0]+[1]
for i in range(2,X):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

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

def comb(n,k):
    value = 1
    for i in range(n-k+1,n+1):
        value *= i
        value %= mod
    for i in range(1,k+1):
        value *= inv_t[i]
        value %= mod
    return value

ans = fast_mod_pow(2,N,mod)-1
ans -= comb(N,A)
ans -= comb(N,B)
print(ans%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,a,b=map(int,input().split())
    def modinv(a, mod):
        b,u,v = mod,1,0
        while b:
            t=a//b
            a-=t*b
            a,b=b,a
            u-=t*v
            u,v=v,u
        u%=mod
        if u < 0:
            u+=mod
        return u
    
    def COM(N,k):
        tmp=1
        k=min(k,N-k)
        for i in range(N,N-k,-1):
            tmp*=i
            tmp%=MOD
        for i in range(1,k+1):
            tmp*=modinv(i,MOD)
            tmp%=MOD
        return tmp
            
    ans=pow(2,N,MOD)-1-COM(N,a)-COM(N,b)
    while ans<0:
        ans+=+MOD
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def mod_inverse(a, p):
    mod = 1
    p_bin = bin(p-2)
    for i in range(len(p_bin) - 1, 1, -1):
        if i == len(p_bin) - 1:
            mul = a
            mul %= p
            mod *= (mul ** int(p_bin[i]))
            mod %= p
        else:
            mul = mul ** 2
            mul %= p
            mod *= (mul ** int(p_bin[i]))
            mod %= p
    return mod

c = [2]
for i in range(len(bin(n)) - 3):
    c.append(c[-1] ** 2 % p)
ans = -1
temp = 1
bin_n = bin(n)[2:]
for i in range(len(bin_n)):
    if bin_n[-i-1] == "1":
        temp *= c[i]
        temp %= p
d = []
for i in range(max(a, b)):
    d.append(mod_inverse(i + 1, p))
temp2 = 1
for i in range(a):
    temp2 *= (n - i)
    temp2 %= p
    temp2 *= d[i]
    temp2 %= p
temp3 = 1
for i in range(b):
    temp3 *= (n - i)
    temp3 %= p
    temp3 *= d[i]
    temp3 %= p
ans += temp
ans -= temp2
ans -= temp3
ans %= p
print(ans)

Submission status: Accepted

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

def getInvs(n, MOD):
    invs = [0] * (n+1)
    invs[1] = 1
    for x in range(2, n+1):
        invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
    return invs
invs = getInvs(200000, MOD)

def combi(n, k):
    if k > n-k:
        k = n-k
    ret = 1
    for x in range(n, n-k, -1):
        ret *= x
        ret %= MOD
    for x in range(k, 1, -1):
        ret *= invs[x]
        ret %= MOD
    return ret

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

Submission status: Accepted

Solution code:
# 乗法のmod逆元（mod-2乗）
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

# nCr mod m
# modinvが必要
# rがn/2に近いと非常に重くなる
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

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

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

ans = ((2**n - 1) % mod) - (combination(n, a) % mod) - (combination(n, b) % mod)
print(ans % mod)

Submission status: Accepted

Solution code:
def main():
    mod=1000000007
    n,a,b=map(int,input().split())
    ans=(pow(2,n,mod)-1)%mod
    tmp=1
    for i in range(a):
        tmp*=n-i
        tmp*=pow(i+1,mod-2,mod)
        tmp%=mod
    #print(tmp)
    ans-=tmp
    ans%=mod
    tmp=1
    for i in range(b):
        tmp*=n-i
        tmp*=pow(i+1,mod-2,mod)
        tmp%=mod
    #print(tmp)
    ans-=tmp
    ans%=mod
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
if 2*10**5>=n:
    def cmb(n, r, mod):#コンビネーションの高速計算　
        if ( r<0 or r>n ):
            return 0
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % mod

    mod = 10**9+7 #出力の制限
    N = 2*10**5
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル

    for i in range( 2, N + 1 ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )

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

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

    mod = 10**9+7
    N=2*10**5
    g1 = [n%mod,n*(n-1)%mod] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル
    for i in range( 2, N + 1 ):
        g1.append( ( g1[-1] * (n-i) ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )
    print((2**n-1-cmb(n,a,mod)-cmb(n,b,mod))%mod)

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
MOD = 10**9 + 7
def calc(a, b, p):
    if b == 0:
        return 1
    elif b%2 == 0:
        d = calc(a,b/2, p)
        return (d * d) % p
    else:
        return (a * calc(a,b-1,p)) % p




def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

print((calc(2, n, MOD) - combination(n, a) - combination(n, b) - 1) % MOD)

Submission status: Accepted

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


def comb(a, b, p):
    if (b > a - b):
        return comb(a, a - b, p)
    c = d = 1
    for i in range(b):
        c *= (a - i)
        d *= (b - i)
        c %= p
        d %= p
    return c * modpow(d, p - 2, p) % p


n, a, b = map(int, input().split())
mod = 10**9 + 7
all = modpow(2, n, mod)
res = (all - 1 - comb(n, a, mod) - comb(n, b, mod)) % mod
print(res)

Submission status: Accepted

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

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
            result%=mod

    return result


allp=pow(2,n,mod)-1
ans=(allp-cmb(n,a)%mod-cmb(n,b)%mod+mod)%mod
if n==2:
    ans=0

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7
def inv_mod(a,p=MOD):
    def inv_mod_sub(a,p):
        if a == 1:
            return 1,0
        else:
            d,r = p//a,p%a
            x,y = inv_mod_sub(r,a)
            return y-d*x,x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n,k):
    if k < 0 or k > n:
        return 0
    else:
        c = 1
        for i in range(k):
            c *= n-i
            c %= MOD
        return c*f_mod_inverse[k] % MOD
f_mod=[1]*(10**6)
f_mod_inverse=[1]*(10**6)
for i in range(1,10**6):
  f_mod[i]=f_mod[i-1]*i%MOD
  f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i)%MOD
n,a,b = map(int,input().split())
print((pow(2,n,MOD)-comb_mod(n,a)-comb_mod(n,b)-1)%MOD)

Submission status: Accepted

Solution code:

MAX = 510000;
MOD = 1000000007;

finv = [0] * MAX
inv = [0] * MAX

def init():
    finv[0] = finv[1] = 1;
    inv[1] = 1
    for i in xrange(2, MAX):
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;


def com(n, k):
    ans = 1
    for i in xrange(n, n - k, -1):
        ans = (ans * i) % MOD
    return ans * finv[k] % MOD


def main():
    n, a, b = map(int, raw_input().split())
    init()
    print (pow(2, n, MOD) - 1 - com(n, a) - com(n , b)) % MOD

main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

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

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10**9+7
n,a,b=MI()
r_max =200005
com=[0]*r_max
com[0]=mint(1)
for i in range(1,r_max):
    com[i]=com[i-1]*(n-i+1)/i

ans=pow(2,n,md)-1-com[a]-com[b]
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def modNum(N, a):
    global MOD
    ans = 1
    for i in range(a):
        ans *= (N - i)
        ans %= MOD
    return ans


N, a, b = map(int, input().split())
total = pow(2, N, MOD) - 1
modFacts, invs = prepare(max(a, b))


A = (modNum(N, a) * invs[a]) % MOD
B = (modNum(N, b) * invs[b]) % MOD

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

Submission status: Accepted

Solution code:
MOD = 10 **9 + 7

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

all = pow(2,n,MOD)
if all:# not 0
  all -=1

for i in (a,b):
  sub = 1
  for j in range(i):
    sub *= n-j
    sub %= MOD
    sub *= pow(j+1,MOD-2,MOD)
    sub %= MOD
  all -= sub
  if all < 0:
    all += MOD
print(all)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,a,b=map(int,input().split())
INF=10**9+7
def modinv(a,m):
    b=m
    (x,lastx)=(0,1)
    (y,lasty)=(1,0)
    while not b==0:
        q=a//b
        (a,b)=(b,a%b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx%m
ans=0
ans=(ans+pow(2,n,INF)-1)%INF
bunsi=1
bunbo=1
for i in range(a):
    bunsi=(bunsi*(n-i))%INF
    bunbo=(bunbo*(i+1))%INF
x=(bunsi*modinv(bunbo,INF))%INF
bunsi=1
bunbo=1
for i in range(b):
    bunsi=(bunsi*(n-i))%INF
    bunbo=(bunbo*(i+1))%INF
y=(bunsi*modinv(bunbo,INF))%INF
ans=(ans-x-y)%INF
print(ans)