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: Time Limit Exceeded

Solution code:
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

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

##########################

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

N = int(N%1000000007)
a = int(a%1000000007)
b = int(b%1000000007)

ans = int( (2**(N)-1) % 1000000007 )
aa = cmb(N, a, p)
bb = cmb(N, b, p)

print(int(ans-aa-bb) )

Submission status: Time Limit Exceeded

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

    return result

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from collections import deque, defaultdict
import bisect
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
    return [w[0],w[1]]

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


def comb(n, k):
    m = 10**9+7
    res = 1
    for i in range(1,n+1):
        res = res*i%m
    for i in range(1,k+1):
        res = res*mod_inv(i,m)%m
    for i in range(1,n-k+1):
        res = res*mod_inv(i,m)%m

    return res


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

    result = 2 ** n % mod - comb(n, a) - comb(n, b) % mod - 1
    result = int(result % mod)

    print(result)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

nm = pow(2,n,mod) -1
am = cmb(n,a)
bm = cmb(n,b)
ans = (nm - am - bm)
if ans < 0:
    ans += mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
p=10**9+7
nCa=1
nCb=1
if a>n/2:
    a=n-a
if b>n/2:
    b=n-b

for i in range(1,max(a,b)+1):
    if i<=a:
        nCa=(n-i+1)*nCa//i
    if i<=b:
        nCb=nCb*(n-i+1)//i
    if i>a+1 and i>b+1:
        break
    
ans=2**n-1-nCa-nCb
print(ans%p)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

n,a,b = map(int,input().split())
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

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

#print(cmb(n, r, p))


ans = all - cmb(n,a,p) - cmb(n,b,p)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import math
#あらかじめmax(a,b)までinv　を計算する
n,a,b = map(int,input().split())
P = 10**9 + 7
N = max(a,b)+1
inv_t = [0]+[1]
for i in range(2,N):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
def cmb(n, a, p):
    ans = 1
    for i in range(a):
        ans *= (n-i) * inv_t[i+1] % p
    return ans
#print(cmb(n,a,p),cmb(n,b,p))
print((2**n - 1 - cmb(n,a,P) - cmb(n,b,P))%P)

Submission status: Time Limit Exceeded

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


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])

    return result


count = (2 ** N) - 1
count -= cmb(N, A)
count -= cmb(N, B) 
print(count % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

for i in range(1,n+1):
	if i == a or i == b:
		continue
	else:
		num = combinations_count(n, i)
		numnum = num + numnum

num2 = numnum % (10 ** 9 + 7)
print(num2)

Submission status: Time Limit Exceeded

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

def factorial(n):
    fact = 1
    while n > 1:
        fact *= n
        n -= 1
    return fact

sumv = 0
f = factorial(n)
for i in range(1, n + 1):
    sumv += f // (factorial(i) * factorial(n-i))
sumv -= f // (factorial(a) * factorial(n - a))
sumv -= f // (factorial(b) * factorial(n - b))
print(sumv)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

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

ans = 0
total = pow(2, n, MOD)


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


ans = total - (comb(n, a) + comb(n, b)) - 1
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def cmb_prepare(n, p=10**9+7):
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    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)
    return fact, factinv


def cmb(n, r, fact, factinv, p=10**9+7):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p


# not AC
def get_result(data):
    n, a, b = data[0]
    fact, factinv = cmb_prepare(n)
    mod = 10**9 + 7
    out = ((2 ** n - 1) % mod - cmb(n, a, fact, factinv) - cmb(n, b, fact, factinv)) % mod
    return out

if __name__ == '__main__':
    raw_data = [val.rstrip('\n') for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)

Submission status: Time Limit Exceeded

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

import math
from collections import defaultdict

(n, a, b) = [int(s) for s in input().split()]

c_list = [s for s in range(1, n + 1) if s != a and s != b]

comb_sum = 0
pn = math.factorial(n)
for c in c_list:
    comb_sum += pn // (math.factorial(n - c) * math.factorial(c))

ans = int(comb_sum % (1e9 + 7))

print(ans)

Submission status: Time Limit Exceeded

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

mod = 10 **9 +7
kinds = 0

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

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

    R = [1] * (n+1)

    for i in range(1, n+1):
        if i > 1:
            R[i] = R[i-1]*invs[i]
            R[i] %= m
        else:
            R[i] = invs[i]
    return R


fact_n = mod_factorial(n, mod)
Rs = mod_inv_factorial(n, mod)


for i in range(1, n+1):
    if i != a and i != b:
        kinds += fact_n * Rs[i] * Rs[n-i]
        kinds %= mod

print(kinds % mod)

Submission status: Time Limit Exceeded

Solution code:
def ncr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i 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 *= numerator[k]
    return int(result)
  
n, a, b = map(int, input().split())
whole_sum = (2 ** n) - 1
mod = 10 ** 9 + 7

whole_sum -= ncr(n, a)
whole_sum -= ncr(n, b)

print(whole_sum % mod)

Submission status: Time Limit Exceeded

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

def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p

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

plus = pow_r(2, (n - 1))
sum = 2 * plus - 1 % p

fact = [1, 1] 
factinv = [1, 1] 
inv = [0, 1] 

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)
print(sum - cmb(n,a) % p - cmb(n,b) % p)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
def cmb(n,r):
  return factorial(n) / factorial(r) / factorial(n - r)

list = input().split()
N = int(list[0])
a = int(list[1])
b = int(list[2])
S = 0
for i in range(1,N+1):
  if i != a and i != b:
    S += cmb(N,i)
x = 10**9 + 7
S = S % x
print(int(S))

Submission status: Time Limit Exceeded

Solution code:
import math
n,a,b = [int(x) for x in input().rstrip().split()]
l=[]
n1=1
st=1
ans=0
for i in range(1,n+1):
    n1=n1*(n-i+1)
    st=st*i
    ans1 = (n1//st)
    if i==a or i==b:
        l.append(n1//st)
        continue
    else:
        if n<(i/2):
            ans+=l[n-i]
        else:
            ans+=ans1
            l.append(ans1)

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

Submission status: Time Limit Exceeded

Solution code:
def ncr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i 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 *= numerator[k]
    return int(result)
  
n, a, b = map(int, input().split())
whole_sum = (2 ** n) - 1
mod = 10 ** 9 + 7

whole_sum -= ncr(n, a)
whole_sum -= ncr(n, b)

print(whole_sum % mod)

Submission status: Time Limit Exceeded

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

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

total = 2**n - 1
acomb = cmb(n, a)
bcomb = cmb(n, b)

ans = total - acomb - bcomb
print(ans % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
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 = 10**9
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 main():
	n,a,b=map(int, input().split())
	count = 0
	for i in range(1,n+1):
		if i!=a and i!=b:
			count +=cmb(n,i,mod)
		else:
			count = count
	print(count%(1000000000+7))
main()

Submission status: Time Limit Exceeded

Solution code:
import math

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

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
if N < 3:
    print(0)
else:
    for val in range(1, N + 1):
        cnt += combinations_count(N, val)
    cnt_exc = combinations_count(N, a) + combinations_count(N, b)
    print((cnt - cnt_exc) % (10**9 + 7))

Submission status: Time Limit Exceeded

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())
cnk = []
now = 1
for i in range(b+2):
    cnk.append(now)
    now = (now*(n-i)*power(i+1,mod-2))%mod

ans = power(2, n)%mod - cnk[a] - cnk[b] - 1
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import math

def factorial(num):
    value = 1
    if num == 0:
        return 1
    else:
        for j in range(1, num+1):
            value *= j
        return value

def main():
    n, a, b = map(int, input().split())
    sum = 0

    for i in range(1, n+1):
        if i == a or i == b:
            continue
        sum += factorial(n)/(factorial(n-i)*factorial(i))
    
    print(int(sum%(10**9+7)))

main()

Submission status: Time Limit Exceeded

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

import math
def nCr(n,r):
    temp=math.factorial(n)//(math.factorial(r)*math.factorial(n-r))
    return temp


answer=2**n-nCr(n,a)-nCr(n,b)-1

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

Submission status: Time Limit Exceeded

Solution code:
import math

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

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(1,n+1):
	if i == a or i == b:
		continue
	else:
		num = combinations_count(n, i)
		numnum = num + numnum

num2 = numnum % (10 ** 9 + 7)
print(num2)

Submission status: Time Limit Exceeded

Solution code:
def ncr(n, r, mod):
    r = min(r, n - r)
    if r == 0:
        return 1
    if r == 1:
        return n
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i 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] *= modpow(pivot, mod-2, mod)
                denominator[k] *= modpow(pivot, mod-2, mod)
                denominator[k] = denominator[k]%mod
    result = 1
    for k in range(r):
        if numerator[k] > 1: 
            result *= numerator[k]%mod
            result = result%mod
    return result

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

def resolve():
    n, a, b = map(int, input().split())
    mod = 10 ** 9 + 7
    print((modpow(2, n, mod) - ncr(n, a, mod) - ncr(n, b, mod) - 1)%mod)
resolve()

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb
n, a, b = map(int, input().split())
ans = 1
if n % 2 == 0:
    nn = n
else:
    nn = n + 1
for k in range(1, nn // 2):
    ans += 2 * comb(n, k, exact = True)
if n % 2 == 0:
    ans += comb(n, n // 2, exact = True)
ans -= comb(n, a, exact = True) + comb(n, b, exact = True)
print(ans % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
N,A,B = map(int, input().strip().split())
MOD = int(1e9+7)
ans = 0
nCr = 1
for r in range(N):
    nCr = nCr * (N - r) // (r + 1)
    if r == A-1 or r == B-1: continue
    ans = (ans+nCr%MOD)%MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2000000)
input=sys.stdin.readline


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

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 mul(a, b):
    return ((a % mod) * (b % mod)) % mod
def div(a, b):
    return mul(a, power(b, mod-2)) % mod


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


cnt=(power(2,n)-1)%mod

cnt-=cmb(n,a)+cmb(n,b)
print(cnt%mod)

Submission status: Time Limit Exceeded

Solution code:
p = 10 ** 9 + 7
n,a,b = map(int,input().split())
k=max(a,b)
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
com=[0]*(k+1)
com[0]=1
for i in range(1, k+1):
  com[i]=((com[i-1]*(n-i+1))*modinv(i,p))%p
print((2**n-1-com[a]-com[b])%p)

Submission status: Time Limit Exceeded

Solution code:
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 = 10 ** 9
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)

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

# mod = 10 ** 9 + 7
ans = (2 ** n - 1) - (cmb(n, a, mod) + cmb(n, b, mod))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC156d


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    # 再帰関数を使わない限りPypyで出すこと
    import math
    MOD = 10**9+7

    def combinations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

    n, a, b = map(int, input().split())
    # print(2**n)
    #print(2**n % MOD-1-combinations_count(n, a)-combinations_count(n, b))

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

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

        return K % MOD * x % MOD

    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 = result*int(numerator[k]) % MOD

        return result % MOD

    _FAC_TABLE = [1, 1]

    def factorial(n):
        if n < len(_FAC_TABLE):
            return _FAC_TABLE[n]

        last = len(_FAC_TABLE) - 1
        total = _FAC_TABLE[last]
        for i in range(last + 1, n + 1):
            total *= i
            _FAC_TABLE.append(total)
    # print(factorial(n))

    def mod_fact(n, p, e):
        e = 0
        if n == 0:
            return 1
        res = mod_fact(n / p, p, e)
        e += n / p
        if n / p % 2 != 0:
            return res * (p - fact)

    def range_prod(lo, hi):
        if lo+1 < hi:
            mid = (hi+lo)//2
            return range_prod(lo, mid) * range_prod(mid+1, hi)
        if lo == hi:
            return lo
        return lo*hi

    def treefactorial(n):
        if n < 2:
            return 1
        return range_prod(1, n)

    # print(treefactorial(n))

    def comb(n, k):
        deno = 1
        num = 1
        result = 1
        # set the value of deno and num bounds
        if k > n - k:
            num_val = k + 1
            den_val = n - k
        else:
            num_val = n - k + 1
            den_val = k
        i = n
        # calculate n * (n - k) *....* (n-num_value))
        while i != num_val - 1:
            if i == 0:
                result *= 1
            else:
                result *= i
            if i == num_val:
                num = result
            i -= 1
        i = 0
        result = 1
        # calculate den_val! (factorial of denominator)
        while i != den_val + 1:
            if i == 0:
                result *= 1
            else:
                result *= i
            if i == den_val:
                deno = result
            i += 1
        ans = num/deno
        return ans
    #print(cmb(n, a))

    #print(prepare(n, MOD))
    #print(cmb(n, b) % MOD)
    #print(cmb(n, a))
    ans = pow_k(2, n) - 1 - cmb(n, a) - cmb(n, b)
    while ans < 0:
        ans += MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    return result

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

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
ans = 0
from math import factorial

for i in range(n):
	ans += factorial(n) / factorial(i) / factorial(n - i)

A = factorial(n) / factorial(a) / factorial(n - a)
B = factorial(n) / factorial(b) / factorial(n - b)
    
print(int((ans-A-B)%(10**9+7)))

Submission status: Time Limit Exceeded

Solution code:
import math

def combinations_count(n, r):
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r)))%(10**9+7)
    
div = 10**9+7
n,a,b = [int(i) for i in input().split()]
ans = 1
for i in range(n):
    ans = (2*ans)%div

print((ans-1- combinations_count(n,a) - combinations_count(n,b))%div)

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb

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

ans = 2**n-1
ans -= comb(n ,a , exact=True)
ans -= comb(n ,b, exact=True)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

def main(n,a,b):
    return (2**n - 1) - (ccount(n,a) + ccount(n,b))
def ccount(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

Submission status: Time Limit Exceeded

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

def prepare(n, mod):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= mod
        factorials.append(f)
    inv = pow(f, mod - 2, mod)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= mod
        invs[m - 1] = inv
    return factorials, invs

factorials, invs = prepare(N,mod)
sum = 1
for i in range(N) :
    sum = (sum * 2) % mod

nCa = (factorials[N] * invs[N-a] % mod * invs[a] % mod)
nCb = (factorials[N] * invs[N-b] % mod * invs[b] % mod)

sum = (sum - nCa - nCb - 1) % mod
print(sum)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from math import factorial


def comb(n, x):
    return factorial(n) // (factorial(x) * factorial(n - x))


def main():
    N, A, B = [int(x) for x in stdin.readline().rstrip().split()]
    result = sum([comb(N, i) for i in range(1, N + 1) if i != A and i != B])
    print(int(result % (1e9+7)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def modpow(a,m,n):
    b=bin(n)
    bi=[]
    for i in range(len(b)-2):
        c=str(b)[len(b)-1-i]
        c=int(c)
        bi.append(c)
    pre_pow=[a%m]
    num=a
    for j in range(len(b)-1):
        num*=num
        num=num%m
        pre_pow.append(num)
    ans=1
    for k in range(len(b)-2):
        if bi[k]!=0:
            ans*=pre_pow[k]
    return(ans%m)

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

print(num)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
    
N, a, b = map(int,input().split())
print(power_func(2, N, 1000000007) - comb(N, a, 1000000007) - comb(N, b, 1000000007) - 1)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

ax = cmb(N, a)
bx = cmb(N, b)

sum = pow(2, N)

print((sum - ax - bx - 1)%10000000)

Submission status: Time Limit Exceeded

Solution code:
l = input().split(" ")

import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

a = 2 ** int(l[0]) - 1

print(a - comb(int(l[0]), int(l[1])) - comb(int(l[0]), int(l[2])))

Submission status: Time Limit Exceeded

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

#処理
import math

from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

print((2**n-combinations_count(n, a)-combinations_count(n, b)-1)%(10**9+7))

Submission status: Time Limit Exceeded

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

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

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 )

sum = (2 ** n - 1) % mod
a_com = cmb(n, a, mod)
b_com = cmb(n, b, mod)
print(sum - a_com - b_com)

Submission status: Time Limit Exceeded

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
base = comb(5,3)

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

#nが奇数の時
if n %2 ==1:
    for r in range(n//2):
        nCr_1 = nCr * (n - r) // (r + 1)
        nCr = nCr_1
        ans += nCr_1%mod
    ans = (ans*2+1)%mod

#nが偶数の時
if n % 2 == 0:
    for r in range(n//2):
        nCr_1 = nCr * (n - r) // (r + 1)
        nCr = nCr_1
        ans += nCr_1%mod
    ans = (ans*2+1-nCr_1)%mod
print(ans - comb(n,a) - comb(n,b))

Submission status: Time Limit Exceeded

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

import math
from collections import defaultdict

(n, a, b) = [int(s) for s in input().split()]

c_list = [s for s in range(1, n + 1) if s != a and s != b]

comb_sum = 0
for c in c_list:
    comb_sum += math.factorial(n) // (math.factorial(n - c) * math.factorial(c))

ans = int(comb_sum % (1e9 + 7))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
I=10**9+7
def g(k,r):
  return 1 if k<2 or r in (0,k) else (g(k-1,r-1)+g(k-1,r))%I
p=1
for i in range(n):
  p=p*2%I
print((p-g(n,a)-g(n,b)-1)%I)

Submission status: Time Limit Exceeded

Solution code:
import math
def cc(m,r):
    return math.factorial(m) // (math.factorial(m - r) * math.factorial(r))
n,a,b=map(int,input().split(" "))
ans=0
for i in range(1,n+1):
  ans+=cc(n%1000000007,i)%1000000007
ans-=cc(n%1000000007,a)%1000000007
ans-=cc(n%1000000007,b)%1000000007
print(ans)

Submission status: Time Limit Exceeded

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

mod = 1000000007

def cmb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
  
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

print(pow(2,n,mod)-1-(cmb(n,a,mod)+cmb(n,b,mod)))

Submission status: Time Limit Exceeded

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