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:
from math import factorial
def cmb(N2,n,r):
  return N2 / factorial(r) / factorial(n - r)

list = input().split()
N = int(list[0])
a = int(list[1])
b = int(list[2])
N2 = factorial(N)
S = 0
k = N // 2
x = 10**9 + 7


if N % 2 == 0:
  for i in range(1,k):
    S += cmb(N2,N,i)
  S += S + cmb(N2,N,k) + 1
else:
  for i in range(1,k+1):
    S += cmb(N2,N,i)
  S += S + 1
S += -cmb(N2,N,a) -cmb(N2,N,b)
S = S % x
print(int(S))

Submission status: Time Limit Exceeded

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

    return result

ai  = cmb(n, a)
bi  = cmb(n, b)

ans = (2 ** n  - ai - bi - 1)% mod
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce
MOD = 10**9 + 7
def modpow(a:int, p:int, mod:int)->int:
    if p==0: return 1
    if p%2==0:
        half = modpow(a, p//2, mod)
        return half*half % mod
    else:
        return a * modpow(a, p-1, mod) % mod

def cmb2(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

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 )

A = list(map(int, input().split()))
n = A[0]
a = A[1]
b = A[2]

tot = modpow(2, n, MOD)

tot = tot-1
tot -= cmb2(n,a)
tot -= cmb2(n,b)
tot = tot % MOD

print(tot)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

def modpow(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 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())
mod = 10 ** 9 + 7
ans = modpow(2, n, mod) - 1
ans -= (cmb(n, a) + cmb(n, b))

print(ans % 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

def main():
    from math import factorial
    import sys
    input = sys.stdin.readline
    N,A,B = map(int,input().split())
    ans = 0
    ans_s = [cmb(N,n) % ((10**9)+7) for n in range(1,N+1) if n != A and n != B]
    ans += sum(ans_s)
    print(int(ans))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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


print(pow(2,n,p) -A - B-1)

Submission status: Time Limit Exceeded

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

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
s = 0
for i in range(n):
  s += combinations_count(n, i)
s = s - combinations_count(n, a) - combinations_count(n, b)
t = s %(10**9 + 7)
print(t)

Submission status: Time Limit Exceeded

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

    return result


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


s = pow_k(2, n) - cmb(n, a) - cmb(n, b) - 1
print(s % MAX)

Submission status: Time Limit Exceeded

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



D=[1,2,4]
d=[0,1,2]
for i in range(3,31):
    d.append(d[-1]*2)
    D.append((D[-1]**2)%mod)
D=D[::-1]
d=d[::-1]
#print(len(D),D)
#print(len(d),d)
Num=NN
ALL=1
for i in range(31):
    if Num>=d[i]:
        Num-=d[i]
        ALL*=D[i]
        ALL%=mod
if Num==1:
    Num-=1
    ALL*=2
    ALL%=mod
#print(ALL,Num)

A=cmb(NN,a)%mod
B=cmb(NN,b)%mod
#print(A,B)

if NN<a or NN<b:
    print(0)
else:
    if ALL-A-B-1<0:
        print((ALL-A-B-1+mod*2)%mod)
    else:
        print(ALL-A-B-1)

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

comb_sum = 0
pn = math.factorial(n)
pnc = n - 1
pc = 1

dd = math.factorial(4 - 2)
cc = math.factorial(2)

for c in range(1, n + 1):
    pnc *= n - c
    pc *= c
    if c != a and c != b:
        comb_sum += pn // (math.factorial(n - c) * pc)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math

NAB = input()

nab_array = NAB.split(" ")
N = int(nab_array[0])
a = int(nab_array[1])
b = int(nab_array[2])
result = 0

for i in range(N):
    if i+1 != a and i+1 != b:
        result += math.factorial(N)/(math.factorial(i+1)*math.factorial(N-(i+1)))


print(int(result%(10**9+7)))

Submission status: Time Limit Exceeded

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

f = 1
for i in range(1, n+1):
  f *= i
  f %= mod
     
# n!^-1 の計算
inv = pow(f, mod - 2, mod)
# n!^-1 - 1!^-1 の計算
invs = {}
invs[n] = inv
for m in range(n, 1, -1):
    inv *= m
    inv %= mod
    invs[m - 1] = inv

memo = {}

for i in range(1, n//2+1):
  memo[i] = f*invs[i]*invs[n-i]%mod

for i in range(1, n+1):
  if i != a and i != b:
    if i == n:
      ans += 1
    elif i <= n//2:
      ans += memo[i]
    else:
      ans += memo[n-i]
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
n,a,b = map(int, input().split())
ans = 0
c = 1
x = n
y = 1
if a!=n and b!=n: ans+=c
for i in range(1,(n+2)//2):
    c = c*x//y
    x-=1
    y+=1
    ans += c*2
    if i==a or n-i==a:
        ans -= c
    if i==b or n-i==b:
        ans -= c
    if i==n/2:
        ans -= c
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
d = input().split(" ")
n = int(d[0])
a = int(d[1])
b = int(d[2])
m = 1000000007
p = n
t = (2 ** n) % m - 1
def ncr(n, r):
	if n - r < r:
		r = n  - r
	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]) % m) % m)

	return result

t = t - ncr(n, a) - ncr(n, b)
if t < 0:
	t = t + m
print(int(t))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

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

Ci = n
Si = n
Ai = 0
Bi = 0

if a == 1:
    Ai = Ci
if b == 1:
    Bi = Ci
    
for k in range(2,n+1):
    Ci = Ci*(n-k+1)//k
    Ci %= MOD
    Si += Ci
    Si %= MOD
    if k == a:
        Ai = Ci
    if k == b:
        Bi = Ci

ans = (Si - Ai - Bi) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
n, a, b = (int(x) for x in input().split())
sum = 0
for i in range(n):
    if i != a-1 and i != b-1:
        x = math.factorial(i+1)
        y = math.factorial(n-i-1)
        sum += math.factorial(n) / (x * y)
ans = sum % 1000000007
print(round(ans))

Submission status: Time Limit Exceeded

Solution code:
import math

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

n, a, b = map(int, input().split())
c_lst = [i for i in range(1, n + 1) if (i != a) and (i != b) ]
lst_s = []
for i in c_lst:
    lst_s.append(count(n,i))

lst_s = sum(lst_s) % (10**9 + 7)
print(lst_s)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, a, b = map(int, input().split())
mod = 10**9 + 7
# def pow1(x, n):
#     if n == 0: return 1
#     value = pow1(x, int(n / 2)) % mod
#     value *= value % mod
#     if n % 2 == 1: value *= x
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
all = (pow_k(2, n) % mod) - 1
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

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

Submission status: Time Limit Exceeded

Solution code:

def fact(a,b):
  f=1
  for i in range(a,b+1):
    f *= i 
  return f

def C(n, r):
  if(r>n-r):
    return fact(r+1,n)//fact(1,n-r)
  else:
    return fact(n-r+1, n)//fact(1,r)

def func(n, LIMI):
  if(n==0):
    return 1
  else:
    return (func(n//2,LIM) * func(n//2,LIMI)*(2**(n%2)))%LIMI

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

LIM=10**9+7
hana=  (func(N,LIM)-1)%LIM
hana -= C(N,a) + C(N,b)



print(hana)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,a,b = map(int,input().split())
    MOD = (10**9)+7
    # s = powpow(2,n)
    s=pow(2,n,MOD) -1
    f,inv_f=comInit(MOD,n)

    s-=calCom(n,a,MOD,f,inv_f)
    s-=calCom(n,b,MOD,f,inv_f)

    print(s)

def powpow(a,n):
    mod = (10**9)+7
    x = 1
    i = 0
    while n > 0:
        print(bin(n))
        if bin(n & 1):
            x=x*a
            # x%=mod
        a*=a
        print(x)
        # a%=mod
        i+=1
        n=n>>1

    print('aaa')
    return x

def comInit(MOD, n):
    fact=[1,1] # fact[n]はnの階乗
    invr=[0,1] # invr[n]はnの逆元
    invr_fact=[1,1] # invr_fact[n]は逆元の階乗

    for i in range(2,n+1):
        fact.append(fact[-1]*i%MOD)
        invr.append(-invr[MOD%i]*(MOD//i)%MOD)
        invr_fact.append(invr_fact[-1]*invr[-1]%MOD)
    return fact,invr_fact

def calCom(n,k,MOD,fact,invr_fact):
    k=min(k,n-k)
    return fact[n]*invr_fact[k]*invr_fact[n-k]%MOD



if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 22 21:56:01 2020

@author: H_Hoshigi
"""
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

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

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

answer =\
    (2**n)%mod\
    -cmb(n, a, mod)\
    -cmb(n, b, mod)\
    -1
print((answer+mod)%mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
from collections import deque as deq
import math

N, A, B = map(int, input().split())
Z = (10 ** 9) + 7

# 階乗を計算しておく
s = 1
for i in range(N):
    s *= (i + 1)
t = s
u = 1

d = 0
for i in range(N):
    u *= (i + 1)
    s /= N - i
    # 嫌いでなければ
    if (i + 1) != A and (i + 1) != B:
        d += int(t / (u * s))
    d = d % Z if d >= Z else d

print(d)

Submission status: Time Limit Exceeded

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

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

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

    ans = 0

    if n % 2 == 0:
        for i in range(0, (n//2)):
            tmp = comb(n, i, mod)
            if (a != i) and (b != i):
                ans += tmp
            if (a != (n - i)) and (b != (n - i)):
                ans += tmp
        ans -= 1
        if (a != (n//2)) and (b != (n//2)):
            ans += comb(n, n//2, mod)
    else:
        for i in range(0, (n//2)+1):
            tmp = comb(n, i, mod)
            if (a != i) and (b != i):
                ans += tmp
            if (a != (n - i)) and (b != (n - i)):
                ans += tmp
        ans -= 1

    print(ans)
    return 0



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8

MOD = 1000000007

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

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

def div(a, b):
    return mul(a, pow(b, MOD-2, MOD))

    
def nCr(n, r, mod=MOD):
  return frac(n) * pow(frac(r), mod-2, mod) * pow(frac(n-r), mod-2, mod) % MOD

def frac(n):
    v = 1
    for i in range(2, n+1):
        v = mul(v, i)
    return v

def main():
    n, a, b = map(int, input().split())
    sumv = 1
    for _ in range(n):
        sumv = mul(sumv, 2)
    sumv = sub(sumv, nCr(n, a, MOD))
    sumv = sub(sumv, nCr(n, b, MOD))
    sumv = sub(sumv, 1)
    print(sumv)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
n,a,b=map(int, input().split())
mom = 10**9+7
sum=0
for i in range(1,n+1):
  if (i-a)*(i-b)!=0:
    Cn = 1
    for i2 in range(i):
#      print(i,i2)
#      i3 = min(i2,n-i2)
      i3 = i2
      Cn = Cn * (n-i3) / (i3+1)
    sum = sum + Cn % mom
print(round(sum))

Submission status: Time Limit Exceeded

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

c = factorial(n)/(factorial(n)*factorial(n-n))
total = 0
k=factorial(n)
for i in range(1,n+1):
    if i==a or i ==b:continue
    total += k/(factorial(i)*factorial(n-i))

print(int(total)%(10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

n, a, b = map(int,input().split())
sum = 0
for i in range(n, 0, -1) :
    if i != a and i != b :
        x = factorial(n) / factorial(i) / factorial(n - i)
        sum = sum + x

print(round(sum))

Submission status: Time Limit Exceeded

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

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

for i in range(n+1):
    if i == a or i == b or i == 0:continue
    sums += cmb(n,i)
if sums >= (10**9 + 7):
    sums %= (10**9 + 7)
print(sums)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

import time
start = time.time()


# x ** a をmodで割った余りを、O(log(a))時間で求める。
def power(x, a):
	if a == 0:
		return 1
	elif a == 1:
		return x
	elif a % 2 == 0:
		return power(x, a//2) **2 % mod
	else:
		return power(x, a//2) **2 * x % mod

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
	return power(x, mod-2)

modinv_table = [-1] * (b+1)
for i in range(1, b+1):
    modinv_table[i] = modinv(i)

end = time.time()
# print("time: ", end - start)

def binomial_coefficients2(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans

# (2 ** n - 1) - nCa - nCb
ans = power(2, n) - 1

end = time.time()
# print("time: ", end - start)

# nCa
binomi = 1
for i in range(a):
    binomi *= n-i
    binomi *= modinv_table[i + 1]
    binomi %= mod
ans -= binomi

# nCb
for i in range(a, b):
    binomi *= n-i
    binomi *= modinv_table[i + 1]
    binomi %= mod

ans -= binomi
# ans -= (binomial_coefficients2(n, a) + binomial_coefficients2(n, b))
print(ans % mod)

end = time.time()
# print("time: ", end - start)

# print(binomial_coefficients2 (5, 2) % mod)

Submission status: Time Limit Exceeded

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

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

tmp1, tmp2 = cmb(n,a,mod), cmb(n,b,mod)
result = (all - tmp1 - tmp2)%(10**9 + 7)
print(result)

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
p=10**9+7
k = 1
for i in range(n):
  k = 2*k % p
N = k - 1

fact = [1]
k = 1
for i in range(1, 10**5+1):
    k = k*i%p
    fact.append(k)
    
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 mod_e(n,p):
    res = 0
    while n >= p:
        res += n//p
        n = n//p
    return res

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

def mod_comb(n,k,p):
    a1 = mod_fact(n,p)
    a2 = mod_fact(k,p)
    a3 = mod_fact(n-k,p)
    return a1 * mod_inv(a2*a3%p,p) %p
  
A = mod_comb(n,a,p)
B = mod_comb(n,b,p)

if a == b:
  print((N-A) % p)
else:
  print((N-A-B) % p)

Submission status: Time Limit Exceeded

Solution code:
import math
n,a,b = map(int, input().split())
def permutations_count(n, r):
    return math.factorial(n) // (math.factorial(r)*math.factorial(n - r))
m = n//1000000006
p = (2**(n-m*1000000006))%(10**9+7)
ans = p-1-(permutations_count(n, a))%(10**9+7)-(permutations_count(n, b))%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
ans=0
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
max_=min(n,2*(10**5))
com=[0]
if max_%2==0: #偶数の時
    for i in range(1,max_//2+1): #comを計算
        com.append(combination(n,i))
    for i in range(1,max_+1):
        #print(i)
        if i==a or i==b:
            continue
        now=i
        if max_//2<now:
            now=n-now
        if i==max_:
            ans+=1
            #print("a")
            break
        ans+=(com[now]%(10**9+7))
else: #奇数の時
    for i in range(1,max_//2+1): #comを計算
        com.append(combination(n,i))
    for i in range(1,max_+1):
        if i==a or i==b:
            continue
        now=i
        if max_//2<now:
            now=n-now
        if i==max_:
            ans+=1
            break
        ans+=com[now]
print(ans)
#print(com)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
X = input().split()
X = [int(s) for s in X]

n = X[0]
a = X[1]
b = X[2]
mod = 10 ** 9 +7

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


sum = 0
for i in range(n):
	sum += comb(n, i, mod)
sum -= comb(n, a, mod)
sum -= comb(n, b, mod)
sum = sum % (1000000007)
print(int(sum))

Submission status: Time Limit Exceeded

Solution code:
import math

def f(x, y):
    return math.factorial(x) // (math.factorial(x - y) * math.factorial(y))

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

sum = 0
for i in range(n//2):
    x = f(n, i+1)
    sum += x
ans = sum*2+1

if n%2 == 0:
    ans = sum*2+1-x
ans = ans - f(n, a) - f(n, b)
ans %= ((10**9)+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
x = list(map(int,input().split(" ")))
n = x[0]
a = x[1]
b = x[2]
import math

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

l_cc = []
l_all = 0
for i in range(n):
    cci = combinations_count(n, i+1)
    # print(cci)
    l_cc.append(cci)
    l_all += cci
# print(l_cc)
# print(l_all)

ans = l_all - l_cc[a-1] - l_cc[b-1]
print(ans)

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

P = 2**n - 1

ans = P - cmb(n,a) - cmb(n,b)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def mod_comb(a,b,mod):
    #print(a,b)
    if a-b < b: return mod_comb(a,a-b,mod)
    ans_mul = 1
    ans_div = 1
    for i in range(b):
        ans_mul *= a-i
        ans_div *= i+1
        ans_mul %= mod
        ans_div %= mod
    return (ans_mul * modpow(ans_div, mod-2, mod)) % mod

def modpow(a,b,mod):
    if b == 0: return 1
    if b % 2 == 0:
        h = modpow(a, b//2, mod)
        return (h * h) % mod
    else:
        return (a * modpow(a, b-1, mod)) % mod


words = lambda t : list(map(t, input().split()))
n,a,b = words(int)


top = 1
btm = 1
ans = 0
mod = 1000000007
for i in range(1,n+1):
    top *= n - i + 1
    top %= mod
    btm *= modpow(i, mod-2, mod)
    btm %= mod
    if i != a and i != b:
        ans += top * btm
        ans %= mod

print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
def modpow(a:int, p:int, mod:int)->int:
    if p==0: return 1
    if p%2==0:
        half = modpow(a, p//2, mod)
        return half*half % mod
    else:
        return a * modpow(a, p-1, mod) % mod

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 )

A = list(map(int, input().split()))
n = A[0]
a = A[1]
b = A[2]

tot = modpow(2, n, MOD)

tot = tot-1
tot -= cmb(n, a, MOD)
tot -= cmb(n, b, MOD)
tot = tot % MOD

print(tot)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
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


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

ans = 0
for i in range(1, n + 1):
    if i != a and i != b:
        #print(combinations_count(n, i))
        ans += combinations_count(n, i) % (10 ** 9 + 7)
print(ans % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb
N,a,b=map(int,input().split())
MOD=10**9+7
cnt=0
for i in range(1,N+1):
  cnt+=comb(N, i, exact=True)
A=comb(N, a, exact=True)
B=comb(N, b, exact=True)
cnt=cnt-A-B
ans=cnt%MOD
print(ans)

Submission status: Time Limit Exceeded

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

import math

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

l = [int(i) for i in range(1,n+1)]
#print(l)

x = 0
for j in range(n):
    x += combinations_count(n, l[j])

y = combinations_count(n, a) + combinations_count(n, b)

print((x-y)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.misc import comb

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

total = 0

for i in range(1, n+1, 1):
  total += comb(n, i, exact = True)

total -= comb(n, a, exact = True)
total -= comb(n, b, exact = True)

print(total)

Submission status: Time Limit Exceeded

Solution code:
import math
n,a,b= map(int,input().split())
p = 10**9 + 7
c = (math.factorial(n)%p) // ((math.factorial(a)%p)*(math.factorial(n-a)%p))
d = (math.factorial(n)%p) // ((math.factorial(b)%p)*(math.factorial(n-b)%p))
print(2**n -c -d -1)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

def comb(n,i):
  i = min(i, n - i) 
  if(i == 0):
    return 1

  over = reduce(mul, range(n, n - i, -1))
  under = reduce(mul, range(1, i + 1))
  
  return over // under
  
if __name__ == '__main__':
  n, a, b = input().split()
  n = int(n)
  a = int(a)
  b = int(b)
  
  sum_div = 0
  for i in range(1, n + 1):
    if(i == a or i ==b):
      continue
    else:
      sum_div += comb(n, i) % (pow(10,9) + 7)

  print("\n")
  print(sum_div)