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 sys import stdin
from math import factorial


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


def _main(N, A, B):
    result = 0
    for i in range(1, N + 1):
        if i != A and i != B:
            result += comb(N, i)
    return result


def main():
    N, A, B = [int(x) for x in stdin.readline().rstrip().split()]
    result = _main(N, A, B)
    print(int(result % (1e9+7)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#D

n,a,b = map(int,input().split())
p = 10 ** 9 + 7
fact = [1 , 1]
inv = [0 , 1]
factinv = [1 , 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)
q = fact[n] * (factinv[a] * factinv[n - a] + factinv[b] * factinv[n - b]) % p
print((2 ** n % p - 1 - q) % p)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
def combinationsCount(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))
n,a,b = map(int, input().split())
print(int( (2**n - 1 - combinationsCount(n, a) - combinationsCount(n, b)) % (10e9+7) ))

Submission status: Time Limit Exceeded

Solution code:

import itertools
import sys
import math

sys.setrecursionlimit(10**9)

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

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

    # print(comb(10**5,5000,10**9+7))
    nCa = comb(N,a)
    nCb = comb(N,b)

    _, ans = divmod(2**N-1 - nCa - nCb,10**9+7)
    print(ans)

if __name__ == "__main__":
  main()

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

n, a, b = list(map(int, input().split()))
t = 0
for N in range(1, n+1):
    if N != a and N != b:
        t += combinations_count(n, N)        
print(t)

Submission status: Time Limit Exceeded

Solution code:
import math

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

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



countlist = []

for i in range(1,n+1):
    if i == a or i == b:
        pass
    else:
        countlist.append(i)

result = 0
for i in range(len(countlist)):
    result += comb_count(n,countlist[i])

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

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce
def cmb(n, r):
    mod = 1000000007
    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) % mod


def pow_k(x, n):
    mod = 1000000007

    if n == 0:
        return 1

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

    return (K * x) % mod


n, a, b = map(int, input().split())
if n == 2:
    print(0)
else:
    print(pow_k(2, n) - cmb(n, a) - cmb(n, b) - 1 % (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

mod=10**9+7

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

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, mod) - comb(n, b, mod) % mod - 1
    result = int(result % mod)

    print(result)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

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

input = sys.stdin.readline
n,a,b = map(int,input().split())
MOD = 10 ** 9 + 7
x1 = 1

a = min(a,n-a)
b = min(b,n-b)
if a > b:
    a,b = b,a

for i in range(n-a+1,n+1):
    x1 = x1 * i % MOD
for i in range(1,a+1):
    x1 = x1 * mod_inv(i,MOD)

x2 = x1
for i in range(n-b+1,n-a+1):
    x2 = x2 * i % MOD
for i in range(a+1,b+1):
    x2 = x2 * mod_inv(i,MOD)
    x2 = x2 % MOD

t = bin(n)
x0 = 1
for i in t:
    x0 = x0 ** 2
    x0 = x0 % MOD
    if i == '1':
        x0 *= 2
        x0 = x0 % MOD
print ((x0 - x1 - x2 - 1) % MOD)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7


def comb(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] *= pow(pivot, MOD - 2, MOD)
                numerator[k - offset] %= MOD
                denominator[k] *= pow(pivot, MOD - 2, MOD)
                denominator[k] %= MOD

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

    return result


# maxn = 2 * pow(10, 5)
# f = [1 for _ in range(2 * pow(10, 5) + 1)]
# invf = [1 for _ in range(2 * pow(10, 5) + 1)]

# for i in range(1, maxn + 1):
#     f[i] = (f[i - 1] * i) % MOD
# invf[maxn] = pow(f[maxn], MOD - 2, MOD)
# for i in range(maxn, -1, -1):
#     invf[i - 1] = (invf[i] * i) % MOD


# def comb(n, r):
#     return f[n] * invf[r] * invf[n - r] % MOD


res = pow(2, N, MOD)

res -= comb(N, A) + comb(N, B)
print((res - 1) % MOD)

Submission status: Time Limit Exceeded

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

print(ans)

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


import sys
sys.setrecursionlimit(2000000)

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:

import itertools
import sys
import math
import numpy as np
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

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

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

    # print(comb(10**5,5000,10**9+7))
    nCa = comb(N,a)
    nCb = comb(N,b)

    _, ans = divmod(2**N-1 - nCa - nCb,10**9+7)
    print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

t=1000000007

def mod(k):
    return k%t

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

base=power_func(2,n,t)
    
print(mod(2*t+base-1-comb(n,a,t)-comb(n,b,t)))

Submission status: Time Limit Exceeded

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

main()

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 ** 7  # 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())
ans=((2**n-1)%(10**9+7)-cmb(n,a,p)-cmb(n,b,p))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
n, a, b = [int(i) for i in input().split()]

def cmb(n, r, mod):
    return g1[n] * g2[r] * g2[n-r] % mod

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

total = 2**n - 1

at = cmb(n,a,mod)
bt = cmb(n,b,mod)

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

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce
n, a, b = map(int, input().split())
count=0
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

for i in range(n):
  count += cmb(n, i)

count -= cmb(n, a)
count -= cmb(n, b)
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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:
    d, e = (n, c)
    for f in range(n - c + 1, n):
        d *= f
    for g in range(1, c):
        e *= g

    comb_sum += (d // e)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, a, b = [int(x) for x in 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

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, n // 2)
    else:  # standard case ② n is odd
        return x * pow_r(x ** 2, (n - 1) // 2)

A = cmb(n,a)
B = cmb(n,b)
cmb_ = pow_r(2, n)
print((cmb_-A-B-1)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
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 = 10 ** 9 + 7
#N = 10 ** 6  # N は必要分だけ用意する
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)
num = 0
for i in range(N):
  if i+1 == a or i+1 == b:
    pass
  else:
    num += cmb(N,i+1, p)
print(num%p)

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

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)

plus = 2 ** (n - 1) % p
sum = 2 * plus - 1 % p
print(sum - cmb(n,a) % p - cmb(n,b) % p)

Submission status: Time Limit Exceeded

Solution code:
N,a,b = list(map(int,input().split()))
mod = 10**9 + 7
def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

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

    return (K * x) % mod
ans = pow_k(2,N)

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
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)
ans = ans - cmb(N, a, p) - cmb(N, b, p) - 1
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
k = 1
for i in range(n):
  k = 2*k % (10**9 + 7)
N = k - 1
import math
def combinations_count(m, r):
  return math.factorial(m) // (math.factorial(m - r) * math.factorial(r))
A = combinations_count(n, a)
B = combinations_count(n, b)
if a == b:
  print((N-A) % (10**9 + 7))
else:
  print((N-A-B) % (10**9 + 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())
ans=((2**n-1)%p-cmb(n,a,p)-cmb(n,b,p))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from math import factorial

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

count = (2**n - 1) - factorial(n) / factorial(a) / factorial(n - a)  - factorial(n) / factorial(b) / factorial(n - b)
print(int(count % 1000000007))

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
from functools import lru_cache

def input(): return sys.stdin.readline().rstrip()

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

    @lru_cache(maxsize=None)
    def f(n):
        return factorial(n)

    def comb_c(n, r):
        if r > n - r:
            r = n - r 
        a = f(n) % MOD
        b = f(n - r) * f(r)
        return a * pow(b, MOD - 2, MOD) % MOD

    n2 = (n - 1) // 2
    ans = 1
    for i in range(1, n2 + 1):
        ans += comb_c(n, i) * 2
    if n % 2 == 0:
        ans += comb_c(n, n2 + 1)
    ans -= comb_c(n, a)
    ans -= comb_c(n, b)
    ans %= MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
import math
from operator import mul
from functools import reduce

mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().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

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

Submission status: Time Limit Exceeded

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

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 = 3*(10**5)
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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=1
for i in range(1,a+1):
    A*=(NN-i+1)
    A//=i
A%=mod
B=1
for i in range(1,b+1):
    B*=(NN-i+1)
    B//=i
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:
import math
n, a, b=map(int, input().split())
ans=0
mod=10**9+7
def fa(x):
    return (math.factorial(x)%mod)
def fact(t, r):
    return fa(t)//(fa(t-r)*fa(r))
for i in range(n):
    p=fact(n, i)
    ans += p%mod
ans=ans-fact(n, a)-fact(n, b)
print(ans)

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

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

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)

ma = cmb(n, a, p)
mb = cmb(n, b, p)

print((pow(2, n, p) - 1 - ma - mb) % p)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from math import factorial
from scipy.misc import comb

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

counter = 0
UpperLimit = n//2
if n%2 == 0:
    for r in range(UpperLimit):
        counter += comb(n, r, exact = True)
    counter *= 2
    counter += comb(n, UpperLimit, exact = True)
    counter -= 1
else:
    for r in range(UpperLimit+1):
        counter += comb(n, r, exact = True)
    counter *= 2
    counter -= 1

counter -= factorial(n) // (factorial(n - a) * factorial(a))
counter -= factorial(n) // (factorial(n - b) * factorial(b))

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

Submission status: Time Limit Exceeded

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

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

ab=cmb(n,a)+cmb(n,b)

cnt=0
nCr=1
for r in range(n):
    nCr_1 = nCr * (n - r) // (r + 1)
    nCr = nCr_1
    cnt+=nCr_1
print(cnt-ab)

Submission status: Time Limit Exceeded

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

def cmb(n, k, mod, fac, ifac):
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def tables(mod, n):
    fac = [1, 1] 
    ifac = [1, 1] 
    inverse = [0, 1] 

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac

mo = 10 ** 9 +7
fac, ifac = tables(mo, N)
ans = (pow(2, N) - 1 - cmb(N, A, mo, fac, ifac) - cmb(N, B, mo, fac, ifac)) % mo
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N, a, b = map(int, input().split())
    
    MOD = 10 ** 9 + 7
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    
    # 必要なだけforを回す。N+1を書き換える
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)
    
    # nCr n個から重複を許さずr個の組み合わせを選ぶ
    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] % MOD
    
    ans = 0
    
    if N % 2 == 0:
        for i in range(1, N//2):
            ans += cmb(N, i) * 2 % MOD
        ans += 1
        ans += cmb(N, N//2) % MOD
        ans -= cmb(N, a) % MOD
        ans -= cmb(N, b) % MOD
    else:
        for i in range(1, N//2+1):
            ans += cmb(N, i) * 2 % MOD
        ans += 1
        ans -= cmb(N, a) % MOD
        ans -= cmb(N, b) % MOD

    return ans % MOD

print(solve())

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
if n == 2 and a == 1 and b==2:
    print(0)
    exit()

def nCr_mod_p(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 = n + 1  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p), 0! = 1! = 1
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p), 0! = 1! = 1
inv = [0, 1]  # inv[n] = n^(-1) mod p, 0! = 1　だけど便宜上inv[0]=0にしてる

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)


ans = 2**n - 1- nCr_mod_p(n, a, p) - nCr_mod_p(n, b, p)
if ans < 0:
    print(0)
else:
    print(ans%p)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


import sys
sys.setrecursionlimit(2000000)

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

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

Submission status: Time Limit Exceeded

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

LIM=10**9+7

hana=0
C=1
for i in range(1,N+1):
  C=C*(N-i+1)//(i)
  if(i==a or i==b):
    continue
  else:
    hana +=  C
  if(hana > LIM):
    hana = hana % LIM

if(hana > LIM):
  hana = hana % LIM
print(hana)

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


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


n, a, b = map(int, input().split())
if n == 2:
    print(0)
else:
    print(pow_k(2, n) - cmb(n, a) - cmb(n, b) - 1 % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
n,a,b=(int(x) for x in input().split())
mod=1000000007
list=[n]
for i in range(n-1):
	k=list[i]*(n-i-1)/(i+2)
	k%=mod
	list.append(k)
#print(list)
su=sum(list)%mod
su-=list[a-1]
su-=list[b-1]
print(int(su%mod))

Submission status: Time Limit Exceeded

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

ans = 2**n - 1

import math

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

ans = ans - f(n,a) - f(n,b) 
ans = ans % (10**9+7)

print(ans)

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

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

for j in range(1, n+1) :
    if j == a or j == b :
        continue
    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)
    
    plus = cmb(n, j, p)
    ans += plus

print(int(ans))

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)%mod for i in range(r)]
    denominator  = [(i + 1)%mod 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] *= pow(pivot, mod-2, mod)
                denominator[k] *= pow(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:
import math

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

n_in, a, b = map(int, input().split())
key = (10 ** 9) + 7
ans_raw = []

for i in range(1, n_in + 1):
    if i != a and i != b:
        ans_raw.append(combinations_count(n_in, i))

ans_sum = sum(ans_raw)

if ans_sum < key:
    print(str(ans_sum))

else:
    print(str(ans_sum % key))

Submission status: Time Limit Exceeded

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

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
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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

sum = 0
for i in range(n//2):
        sum = sum + 2 * cmb(n, i, p)
        sum = sum % p


if n % 2 == 0:
    sum = sum + cmb(n, n//2, p)

sum = sum - cmb(n, a, p) - cmb(n, b, p)

sum = sum % p

print(sum-1)

Submission status: Time Limit Exceeded

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

def input(): return sys.stdin.readline().rstrip()

def main():
    MOD = 10 ** 9 + 7
    n, a, b = map(int, input().split())
    ab = set([a, b])

    def comb_c(n, r):
        r = min(r, n - r)
        a = reduce(mul, range(n, n - r, -1), 1) % MOD
        b = reduce(mul, range(1, r + 1), 1)
        return a * pow(b, MOD - 2, MOD) % MOD

    n2 = (n - 1) // 2
    ans = 1
    for i in range(1, n2 + 1):
        ans += comb_c(n, i) * 2
    if n % 2 == 0:
        ans += comb_c(n, n2 + 1)
    ans -= comb_c(n, a)
    ans -= comb_c(n, b)
    ans %= MOD
    print(ans)

if __name__ == '__main__':
    main()