Problem:


Score : 400 points

Problem Statement

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

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

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

How many different bouquets are there that Akari can make?

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

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

Constraints

All values in input are integers.

2 \leq n \leq 10^9

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

Input

Input is given from Standard Input in the following format:

n a b

Output

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

Sample Input 1

4 1 3

Sample Output 1

7

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

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

Sample Input 2

1000000000 141421 173205

Sample Output 2

34076506

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



Sample input:
4 1 3


Sample output:
7

Submission status: Accepted

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


def modInverse(a, p):
    return pow(a, p-2, p)

def modBinomial(n, k, p):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n-i)) % p

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

    return (numerator * modInverse(denominator, p)) % p

def solve(n: int, a: int, b: int):
    p = 10**9+7
    ans = pow(2, n, p) - 1 - modBinomial(n, a, p) - modBinomial(n,b,p)
    print((ans+p)%p)
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

mod = 10 **9 +7
kinds = 0

def mod_factorial(nr, nl, m):
    r = 1
    for i in range(nl+1, nr+1):
        r *= i
        r %= m
    return r

def mod_inv_factorial(n1, n2, m):
    n = max(n1, n2)
    invs = [0] * (n + 1)
    invs[1] = 1
    for i in range(2, n + 1):
        invs[i] = m - invs[m % i] * (m//i) % m
        
    r1 = 1
    r2 = 1
    for i in range(1, n1+1):
        r1 *= invs[i]
        r1 %= m
    for i in range(1, n2+1):
        r2 *= invs[i]
        r2 %= m
    return r1, r2
        
        



kinds = 2 ** n -1

la = max(a, n-a)
sa = min(a, n-a)
lb = max(b, n-b)
sb = min(b, n-b)

upper1 = mod_factorial(n, la, mod)
upper2 = mod_factorial(n, lb, mod)

r1, r2 = mod_inv_factorial(sa, sb, mod)

print((kinds - upper1 * r1 - upper2 * r2)% mod)
t = 0

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, a, b = map(int, input().split())

def get_combi_mod(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

ans = 1
div_num = 10 ** 9 + 7
two_thou = (2 ** 1000) % div_num
for i in range(N // 1000):
    ans = (ans * two_thou) % div_num

ans = (ans * (2 ** (N % 1000))) % div_num
print((ans - 1 - get_combi_mod(N, a, div_num) - get_combi_mod(N, b, div_num)) % (10 ** 9 + 7))

Submission status: Accepted

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

N,A,B = map(int,input().split())
if (N == 2):
    print(0)
else:
    print((2**N - 1 - combination(N, A) - combination(N, B)) % (10**9+7))

Submission status: Accepted

Solution code:
def ruijo(n, l, mod):
    a = n
    tmp = n-1
    while(tmp >= l):
        a = a*tmp%mod
        tmp -= 1
    return a

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

mod = 10**9+7 #出力の制限
N = 10**6
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 )

def power(a,n,mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod

mod = 10**9+7 #出力の制限
    
n,a,b = map(int, input().split())
ans = power(2,n,mod) - 1 - cmb(n, a, mod) - cmb(n ,b ,mod)
if ans < 0:
    ans += mod
if ans < 0:
    ans += mod
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n, a, b = map(int, input().split())
a, b = min(a, b), max(a, b)
MOD = 10**9 + 7
v = pow(2, n, MOD) - 1


def cumprod(arr, MOD):
    L = len(arr)
    Lsq = int(L**.5 + 1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n - 1]
        arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n - 1, -1]
        arr[n] %= MOD
    return arr.ravel()[:L]


def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64)
    x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64)
    x[0] = pow(int(fact[-1]), MOD - 2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv


# a / b = (a % N * pow(b, N - 2, N)) % N(mod=N)
fact, fact_inv = make_fact(2 * 10**5 + 1, MOD)
# print(fact)
# a_fact = fact[a]
# b_fact = fact[b]

n_fact = [n % MOD] * (b + 1)
for i in range(1, b + 1):
    n_fact[i] = (n_fact[i - 1] * (n - i)) % MOD
an_fact = n_fact[a - 1]
bn_fact = n_fact[b - 1]
# print('an a_fact', an_fact, a_fact)
# print('bn b_fact', bn_fact, b_fact)
# print('an a_fact', an_fact)
# print('bn b_fact', bn_fact)


def f(a, b, MOD):
    a, b = int(a), int(b)
    return (a % MOD * pow(b, MOD - 2, MOD)) % MOD


ca = an_fact
for i in range(1, a + 1):
    ca = f(ca, i, MOD)

cb = bn_fact
for i in range(1, b + 1):
    cb = f(cb, i, MOD)

# ca = f(an_fact, a_fact, MOD)
# cb = f(bn_fact, b_fact, MOD)
# print('v, ca, cb', v, ca, cb
print((v - ca - cb) % MOD)

Submission status: Accepted

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

nf = 10 ** 5 * 2 + 100
fact = [0] * (nf + 1)
fact[0] = 1
for i in range(nf):
    # fact[i + 1] = (fact[i] * (n - i) / (i + 1)) % m
    fact[i + 1] = (fact[i] * (n - i) * pow((i + 1), m - 2, m)) % m





ans = pow(2, n, m) - 1 - fact[a] - fact[b]
# ans = (2 ** n - 1) % m - fact[a] - fact[b]


ans = ans % m
print(int(ans))

Submission status: Accepted

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

cmba=1
cmbb=1
p=(10**9)+7
lst=[]
num=pow(2,n,p)-1
for i in range(1,b+1):
  cmbb*=((n-i+1)*(pow(i,p-2,p)))%p
  if cmbb>p:
    cmbb=cmbb%p
  cmba=cmbb
  if i==a:
    lst.append(cmba)
    
num=num-lst[0]-cmbb
num=num%p

print(num)

Submission status: Accepted

Solution code:
mod=10**9+7

def add(a, b):
    return (a + b) % mod

def sub(a, b):
    return (a + mod - b) % mod

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

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

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

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


n2=power(2,n)
#n2=1
#for i in range(n):
#    n2=mul(n2,2)
n2=sub(n2,1)
#print(n2)
    
na=1
pna=1
for i in range(a):
    na=mul(na,(n-i))
    pna=mul(pna,(i+1))    
#print(na,pna)
na=div(na,pna)
       
nb=1
pnb=1
for i in range(b):
    nb=mul(nb,(n-i))
    pnb=mul(pnb,(i+1))    
#print(nb,pnb)
nb=div(nb,pnb)

#print(na,nb)

n2=sub(n2,na)
n2=sub(n2,nb)
print(n2)

Submission status: Accepted

Solution code:
import numpy as np
mod = 1000000007

def init(inv, finv):
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, inv.shape[0]):
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod

def comb(n, r):
    a = 1
    for i in range(n - r + 1, n + 1):
        a = a * i % mod
    return (a * finv[r]) % mod


n, a, b = [int(x) for x in input().split()]
m = max(a, b) + 1
inv = np.zeros(m, np.int64)
finv = np.zeros(m, np.int64)
init(inv, finv)
ans = (pow(2, n, mod) - comb(n, a) - comb(n, b) - 1) % mod
print(ans)

Submission status: Accepted

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


def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = r2
        w = w2
    # [x,y]
    return [w[0], w[1]]


def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m+x % m) % m


def comb(n, r, mod):
    u = 1
    d = 1
    for i in range(r):
        u *= n-i
        d *= i+1
        if u >= mod:
            u %= mod
        if d >= mod:
            d %= mod
    return u*mod_inv(d, mod)


def binary(n):
    return bin(n)[2:]


def pow_by_binary_exponentiation(a, x, n):  # a^x mod n
    x = [int(b) for b in binary(x)]
    y = a
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * a) % n
    return y


ac = comb(n, a, mod)
bc = comb(n, b, mod)
ans = pow_by_binary_exponentiation(2, n, mod)
print(((ans - ac - bc - 1) % mod)//1)

Submission status: Accepted

Solution code:
def binary(n):
    return bin(n)[2:]


# バイナリ法
def pow_by_binary_exponentiation(a, x, n):  # a^x mod n
    x = [int(b) for b in binary(x)]
    y = a
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * a) % n
    return y


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


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


# 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


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

mod = 10**9 + 7
S = pow_by_binary_exponentiation(2, n, mod) - 1
A = combination(n, a, mod)
B = combination(n, b, mod)

ans = (S - A - B) % mod
if ans < 0:
    ans += mod
print(ans % mod)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
# sys.setrecursionlimit(10000000)
INF = 1<<32
# import numpy as np

MOD = 1000000007  # type: int

def solve(n: int, a: int, b: int):
    def combination_with_mod(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_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

    ans = 0
    ans = power_func(2, n, MOD)

    ans = ans-combination_with_mod(n, a)-combination_with_mod(n, b)-combination_with_mod(n, 0)
    if ans < 0:
        print((MOD+ans)%MOD)
    else:
        print(ans%MOD)

    return



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:

def binary(n):
    return bin(n)[2:]


def pow_by_binary_exponentiation(a, x, n):  # a^x mod n
    x = [int(b) for b in binary(x)]
    y = a
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * a) % n
    return y


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

mod = 10**9+7
fact = [1]
fact_inv = [1]
for i in range(max(a, b)):
    new_fact = fact[-1]*(i+1) % mod
    fact.append(new_fact)


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


A = pow_by_binary_exponentiation(2, N, mod) - 1

A -= mod_comb_k(N, a, mod)
A -= mod_comb_k(N, b, mod)
print(A % mod)

Submission status: Accepted

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

ans = (2 ** n - 1) % MOD

def cmb(n, r):
    if n - r > r:
        T = r
    else:
        T = n - r
    res = 1
    cnt = 0
    for i in range(1, T + 1):
        res *= (n - i + 1)
        res //= i
        res %= MOD
    return res

def cmb2(n, r):
    if n<0 or r<0 or r>n:
        return None
    r = min(r, n-r)
    if r == 0:
        return 1
    if r == 1:
        return n
    numerator = [0]*r
    denominator = [0]*r
    for k in range(r):
        numerator[k] = n-r+k+1
        denominator[k] = k+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
    res = 1
    for n in numerator:
        if n > 1:
            res *= n
            res %= MOD
    return res


A = cmb2(n, a)
B = cmb2(n, b)

ans -= (A + B) % MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
import math
N=1000000007;
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) % p 



	
def power(base,e):
	if e==0:
		return 1
	ans=int(base)
	e=int(e)
	base=int(base)
	e=e-1
	while(e>0):
		if(e&1==1):
		    ans=(ans*base)%N
		base=(base*base)%N
		e=int(e/2)
	return ans%N



n,a,b=(map(int,input().split()));
ans=(power(2,n)-1-ncr(n,a,N)-ncr(n,b,N)+N)%N



print(ans)
print()

Submission status: Accepted

Solution code:
def cmb(n, r, p):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = 1
    for i in range(n, n - r, -1):
        over = over * i % p
    under = 1
    for i in range(1, r + 1):
        under = under * i % p
    inv = pow(under, p - 2, p)
    return over * inv % p

def main():
    n, a, b = map(int, input().split())
    mod = 10**9 + 7
    ans = pow(2, n, mod) - cmb(n, a, mod) - cmb(n, b, mod) - 1
    while ans < 0:
        ans += mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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 combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
def 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
p=10**9+7
ans=(power_func(2,n,p)-1-combination(n,a,mod=10**9+7)-combination(n,b,mod=10**9+7))%p
print(ans)

Submission status: Accepted

Solution code:
from scipy.misc import comb
import math
n,a,b=list(map(int,input().split()))
mod=10**9+7

inv_t = [0]+[1]
for i in range(2,10**6+1):
  inv_t += [inv_t[mod % i] * (mod - int(mod/ i)) % mod]
#n=10**9
def binary(n):
    return bin(n)[2:]

# モンゴメリ冪乗法
def pow_by_montgomery_ladder(a, x, n): # a^x mod n
    x = [int(b) for b in binary(x)[::-1]]
    k = len(x)
    a1 = a
    a2 = a**2
    for i in range(k - 2, -1, -1):
        if x[i] == 0:
            a2 = (a1 * a2) % n
            a1 = (a1**2) % n
        else:
            a1 = (a1 * a2) % n
            a2 = (a2**2) % n
    return a1

if n<3:
    print(0)
    exit()

ans=pow_by_montgomery_ladder(2,n,mod)
hoge=1
for i in range(1,a+1):
    hoge=(hoge*(n+1-i))%mod
    hoge=(hoge*inv_t[i])%mod
ans-=hoge

hoge=1
for i in range(1,b+1):
    hoge=(hoge*(n+1-i))%mod
    hoge=(hoge*inv_t[i])%mod
ans-=hoge
ans%=mod
print(ans-1)

Submission status: Accepted

Solution code:
import sys
from math import factorial


def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    # [x,y]
    return [w[0], w[1]]


# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m

def nCr(n, r, mod):
    a = factorial(r)
    b = 1
    for i in range(1, r + 1):
        b = b * (n - i + 1) % mod
    a = mod_inv(a, mod)
    return b * a

n, a, b = [int(i) for i in sys.stdin.readline().split()]
mod = 10 ** 9 + 7
res = 2 ** n % mod
res -= (nCr(n, a, mod) + nCr(n, b, mod) + 1) % mod
if res < 0:
    res += mod
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

def powr(i, j, d):
    p = j
    ans = 1
    while p != 0:
        if p % 2 == 1:
            ans = (ans * i) % d
        i = i**2 % d
        p >>= 1
    return ans

def div(i, j):
    # 1/i mod(j)
    # calc i**(j-2) mod(j)
    return powr(i, j-2, j)

# def make_comb(m, d):
#     fac = [0] * (m+1)
#     ifac = [0] * (m+1)
#     # nCk
#     fac[0] = 1
#     ifac[0] = 1
#     for i in range(m):
#         fac[i+1] = (fac[i] * (i+1)) % d
#         ifac[i+1] = (ifac[i] * div(i+1, d)) % d
#     def comb(n, k):
#         if n == 0 and k == 0:
#             return 1
#         if n < k or n < 0:
#             return 0
#         return (fac[n] * ifac[k] * ifac[n-k]) % d
#     return comb

def nck(n, k, d):
    ans = 1
    for i in range(n-(k-1), n+1):
        ans *= i % d
        ans %= d
    for i in range(1, k+1):
        ans *= div(i, d)
        ans %= d
    return ans % d

def main():
    n, a, b = list(map(int, input().strip().split()))
    d = 10**9+7
    # comb = make_comb(10**6, d)
    ans = (powr(2, n, d) - 1 - nck(n, a, d) - nck(n, b, d)) % d
    if ans < 0:
        print(ans + d)
    else:
        print(ans)

    # print(comb(10, 2))
    # print(comb(5, 2))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def inv(x):
    return pow(x, MOD-2, MOD)

def nPk(n,k):
    return fac(n) * inv(fac(n-k)) % MOD

def nCk(n,k):
    return nPk(n,k) * inv(fac(k))

MOD = 10**9+7

def fac(N):
    known = { 0: 1, 1000000000: 698611116, 320000000: 30977140, 820000000: 629786193, 740000000: 375297772, 470000000: 909210595, 200000000: 933245637, 940000000: 83868974, 400000000: 429277690, 130000000: 623534362, 870000000: 256473217, 600000000: 724464507, 330000000: 522049725, 60000000: 27368307, 800000000: 203191898, 530000000: 256141983, 260000000: 135498044, 730000000: 663307737, 460000000: 275105629, 190000000: 109838563, 930000000: 778983779, 660000000: 769795511, 390000000: 917084264, 120000000: 661224977, 860000000: 116667533, 10000000: 682498929, 590000000: 131772368, 50000000: 67347853, 790000000: 748510389, 520000000: 608823837, 250000000: 112390913, 990000000: 847549272, 720000000: 852304035, 450000000: 462639908, 180000000: 547665832, 920000000: 193781724, 650000000: 92255682, 380000000: 940567523, 110000000: 281863274, 850000000: 823845496, 580000000: 848924691, 310000000: 128487469, 40000000: 723816384, 780000000: 624500515, 510000000: 97830135, 240000000: 136026497, 980000000: 377329025, 710000000: 435887178, 440000000: 780072518, 170000000: 66404266, 20000000: 491101308, 670000000: 373745190, 910000000: 172114298, 640000000: 903466878, 370000000: 148528617, 100000000: 927880474, 840000000: 814362881, 570000000: 811575797, 300000000: 668123525, 30000000: 76479948, 770000000: 671734977, 500000000: 733333339, 230000000: 268838846, 970000000: 492741665, 700000000: 957939114, 430000000: 568392357, 160000000: 195888993, 900000000: 586445753, 630000000: 456152084, 360000000: 189239124, 90000000: 888050723, 830000000: 672850561, 560000000: 637939935, 290000000: 500780548, 760000000: 624148346, 490000000: 703397904, 220000000: 368925948, 270000000: 217544623, 960000000: 965785236, 690000000: 825871994, 420000000: 358655417, 150000000: 261384175, 890000000: 245795606, 620000000: 326159309, 350000000: 386027524, 80000000: 199888908, 550000000: 696628828, 280000000: 419363534, 750000000: 217598709, 480000000: 99199382, 210000000: 724691727, 950000000: 315103615, 680000000: 606241871, 410000000: 996164327, 140000000: 970055531, 880000000: 627655552, 610000000: 272814771, 340000000: 309058615, 70000000: 625544428, 810000000: 423951674, 540000000: 141827977}

    ans = known[ N - N % int( 1e7 ) ]
    for i in range( N - N % int( 1e7 ) + 1, N + 1, 1 ):
        ans = ans * i % MOD
    return ans

n,a,b = get_nums_l()

nCa = nCk(n,a)
nCb = nCk(n,b)
ans = pow(2, n, MOD) - 1 - nCa - nCb
print(ans % (10**9 + 7))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
LARGE = 10 ** 9 + 7

def prepare(n, mod):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= mod
    return pow(f, mod - 2, mod)

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

Ca = prepare(a, LARGE)
for i in range(n - a + 1, n + 1):
    Ca *= i
    Ca %= LARGE

Cb = prepare(b, LARGE)
for i in range(n - b + 1, n + 1):
    Cb *= i
    Cb %= LARGE

print((pow(2, n, LARGE) - Ca - Cb - 1 + LARGE) % LARGE)

Submission status: Accepted

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

def aaa(base, n):
#     base = 2
    ans = 1
    nn = n
    while True:
    #     print(base, nn)
        if nn == 0:
            break
        if nn % 2 == 0:
            base = base ** 2
            base = base % mod
            nn /= 2
        else:
            ans *= base
            ans = ans % mod
            nn -= 1
    return ans

xn = aaa(2, n)

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

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//2)**2 * x % mod

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


def fac(start, length, mod):
    x = 1
    for k in range(start, start + length):
        x *= k
        x %= mod
    return x

aa = fac(n - a + 1 , a, mod)
aaa = fac(1, a, mod)
xa = div(aa, aaa)
if aa == 0:
    if aaa == 0:
        xa = 1


bb = fac(n - b + 1 , b, mod)
bbb = fac(1, b, mod)
xb = div(bb, bbb)
if bb == 0:
    if bbb == 0:
        xb = 1
        

x = xn - xa - xb - 1
x = x % mod
if x < 0:
    x += mod
print(x)

Submission status: Accepted

Solution code:
def mpow(x, n):
    result = 1
    while n != 0:
        if n & 1 == 1:
            result *= x
            result %= 1000000007
        x *= x
        x %= 1000000007
        n >>= 1
    return result


def mcomb(n, k):
    a = 1
    b = 1
    for i in range(k):
        a *= n - i
        a %= 1000000007
        b *= i + 1
        b %= 1000000007
    return a * mpow(b, 1000000005) % 1000000007


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

result = mpow(2, n) - 1
result -= mcomb(n, a)
result + 1000000007
result %= 1000000007
result -= mcomb(n, b)
result + 1000000007
result %= 1000000007
print(result)

Submission status: Accepted

Solution code:
mod = 10**9+7 #出力の制限
def pow_r(x, n):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r((x ** 2)%1000000007 , n // 2) % mod
    else:  # standard case ② n is odd
        return x * pow_r((x ** 2)%1000000007, (n - 1) // 2) % mod

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    g1=1
    r = min(r, n-r)
    for i in range(n-r+1,n+1):
        g1*=i
        g1%=mod



    return g1 * g2[r] % mod


g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
def getgen(N):
    for i in range( 2, N + 1 ):

        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )




def resolve():
    n,a,b=map(int,input().split())
    sm=pow_r(2,n)-1
    getgen(max(a,b))
    aa=cmb(n,a,mod)
    bb=cmb(n,b,mod)

    sm-=aa

    if sm<0:
        sm+=mod
    sm-=bb
    if sm<0:
        sm+=mod
    
    print(sm)
    







if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def cmb(n, k, mod):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n-i)) % mod

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

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


def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x


def myPow(x, n, m):
    if(n == 0):
        return 1
    if(n % 2 == 0):
        return myPow(x * x % m, n / 2, m)
    else:
        return x * myPow(x, n - 1, m) % m


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

Submission status: Accepted

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

mod = 10**9 + 7

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//2)**2 * x % mod

def fact(n):
    if n == 1: 
        return 1
    else:
        return (fact(n-1)*n)%mod

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

n, a, b = map(int, input().split())
now = 1
for i in range(a):
    now = (now*(n-i))%mod
cnka = (now * power(math.factorial(a),mod-2) )% mod
for i in range(a,b):
    now = (now*(n-i))%mod
cnkb = (now * power(math.factorial(b),mod-2) )% mod

ans = power(2, n)%mod - cnka - cnkb - 1
print(ans % mod)

Submission status: Accepted

Solution code:
# 二項係数を"やるだけ"にしてくれるライブラリ
MAX = 1000005
MOD = 10**9+7
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()


def pow_r(x, n):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r((x ** 2) % MOD, n // 2) % MOD
    else:  # standard case ② n is odd
        return x * pow_r((x ** 2) % MOD, (n - 1) // 2) % MOD


N, A, B = map(int, input().split())
MOD = 1000000007
all_number = (pow_r(2, N)-1)
# nがさらに巨大な時
tmp_A = 1
for i in range(1, A+1):
    tmp_A %= MOD
    tmp_A *= (N-i+1)
    tmp_A *= inverse[i]

tmp_B = 1
for i in range(1, B+1):
    tmp_B %= MOD
    tmp_B *= (N-i+1)
    tmp_B *= inverse[i]
tmp_A %= MOD
tmp_B %= MOD
# print(all_number, tmp_A, tmp_B)
ans = (all_number - (tmp_A+tmp_B) + MOD)%MOD
print(ans % MOD)

Submission status: Accepted

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

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

at = combination(n,a)
bt = combination(n,b)

result = total - at - bt
result %= mod
if result < 0:
  result += mod
print(result)

Submission status: Accepted

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

def aaa(base, n):
#     base = 2
    ans = 1
    nn = n
    while True:
    #     print(base, nn)
        if nn == 0:
            break
        if nn % 2 == 0:
            base = base ** 2
            base = base % mod + mod
            nn /= 2
        else:
            ans *= base
            ans = ans % mod + mod
            nn -= 1
    return ans

xn = aaa(2, n)

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

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//2)**2 * x % mod

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


def fac(start, length, mod):
    x = 1
    for k in range(start, start + length):
        x *= k
        x %= mod
    return x

aa = fac(n - a + 1 , a, mod)
aaa = fac(1, a, mod)
xa = div(aa, aaa)
if aa == 0:
    if aaa == 0:
        xa = 1


bb = fac(n - b + 1 , b, mod)
bbb = fac(1, b, mod)
xb = div(bb, bbb)
if bb == 0:
    if bbb == 0:
        xb = 1
        

x = xn - xa - xb - 1
x = x % mod
if x < 0:
    x += mod
print(x)