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:
n,a,b = map(int,input().split())
import math
ans = 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 and i != b:
        ans += (combinations_count(n,i)) % (10*9+7)
ans = ans % (10*9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def c(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# xのn乗
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())

ans = pow_k(2,n) - c(n,a) - c(n,b) - 1

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

Submission status: Time Limit Exceeded

Solution code:
import operator as op
from functools import reduce

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


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


total = 0
for x in range(1, n + 1):
    if x != a and x != b:
        total += ncr(n, x) % (pow(10, 9) + 7)

print(total)

Submission status: Time Limit Exceeded

Solution code:
import math

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

for num in range(n):
  check_num = num+1
  if check_num == a or check_num == b:
    continue
  fl += math.factorial(n) // (math.factorial(n - check_num) * math.factorial(check_num))

print(fl%(10^9+7))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import math
def cmb(n, a, p):
    ans = 1
    for i in range(a):
        ans *= (n-i)
    return (ans // math.factorial(a)) % p

p = 10 ** 9 + 7
n,a,b = map(int,input().split())
#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, 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 #出力の制限
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 )

ans=0
for r in (a,b):
    ans += cmb(n,r,mod)
    ans = ans%mod
#print(ans)
all=(2**n - 1)%mod
print((all-ans)%mod)

Submission status: Time Limit Exceeded

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

MAX = 10**9 + 7

def pow_mod_p(n, k, p):
  x = 1
  while k:
    if k % 2 == 1:
      x *= n
      x %= p
    n **= 2
    n %= p
    k >>= 1
  return x

def comb_mod_p(n, k, p):
  x = 1
  for ik in range(k):
    x *= ((n-ik) * pow_mod_p(ik+1, p-2, p))
    x %= p
  return x


def main():
  n, a, b = map(int, input().strip().split())
  sum = 1
  for i in range(1, n+1):
    sum *= 2
    sum %= MAX
  sum -= 1
  sum = sum - comb_mod_p(n, a, MAX) - comb_mod_p(n, b, MAX)
  if sum < 0:
    print(MAX + sum)
  else:
    print(sum)


if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce
mod=10**9+7
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%mod

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

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

r1 = min(a, n - a)
r2 = min(b, n - b)

if r1 > r2:
  r1, r2 = r2, r1

numer1 = reduce(mul, range(n, n - r1, -1), 1)
denom1 = reduce(mul, range(1, r1 + 1), 1)
numer2 = reduce(mul, range(n - r1, n - r2, -1), numer1)
denom2 = reduce(mul, range(r1 + 1, r2 + 1), denom1)

print((2 ** n - 1 - numer1 // denom1 - numer2 // denom2) % (10 ** 9 + 7))

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

def func(a,b,p):
    if b==0:
        return 1
    else:
        if b%2 == 0:
            return (func(a,b//2,p)*func(a,b//2,p))%p
        else:
            return (a*func(a,b-1,p))%p

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

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

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)
s=0
for j in range(1,n+1):
    s = s + cmb(n,j,p)
print(s -cmb(n,a,p)-cmb(n,b,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(2**n - 1 - combinationsCount(n, a) - combinationsCount(n, b))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline
N,a_,b_=map(int,input().split())
l=[min(a_,N-a_),min(b_,N-b_)]
a=min(l)
b=max(l)
#print(a,b)
cmb=1
mod=10**9+7
for i in range(1,a+1):
    cmb*=N-(a-i)
    cmb=cmb//i
    cmb=cmb%mod
ans=-1-cmb
for i in range(a+1,b+1):
    cmb*=N-(b-i)
    cmb=cmb//i
    cmb=cmb%mod

ans-=cmb

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
ans+=pow_k(2,N)
print(ans%mod)

Submission status: Time Limit Exceeded

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

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

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

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

def two_to(n):
    bi = format(n,"b")
    bi_list = list(bi)
    bi_list.reverse()
    s = 1
    for i in range (0,len(bi_list)):
        if bi_list[i] == "1":
            s *= 2**(2**i)
            s = s%1000000007
    return s

sum = two_to(n)
sub = comb_fast(n,a)+comb_fast(n,b)
ans = sum - sub -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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


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

res = 2 ** n - 1

res = res - ncr_count(n, a) - ncr_count(n, b)

print(res%MOD)

Submission status: Time Limit Exceeded

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

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

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


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

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

    return K * x


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

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

def func(a,b,p):
    if b==0:
        return 1
    else:
        if b%2 == 0:
            return ((func(a,b//2,p))**2)%p
        else:
            return (a*func(a,b-1,p))%p

base=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:
import scipy.misc as scm

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

t = 0
for i in range(1, n+1, 1):
    if i == a or i == b:
        continue
    t += scm.comb(n, i, exact=True)

if t == 0:
    print(0)
else:
    print(t % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import math

nab = list(map(int, input().split()))
n = nab[0]
ab = nab[1:]
res = 0
for i in range(1, n+1):
    if i in ab:
        continue
    else:
        res += (math.factorial(n) // math.factorial(n-i)) / math.factorial(i)

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

Submission status: Time Limit Exceeded

Solution code:
def combi(n, r):
    p = 1
    for i in range(1, r+1):
        p = p * (n-i+1) // i
    return p

n, a, b = [int(n) for n in input().split()]
c = 0
for i in range(1, n+1):
    if i not in [a, b]:
        c += combi(n, i)
print(c)

Submission status: Time Limit Exceeded

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

result = 0

numerator = 1
denominator = 1
MOD = 10**9+7

for i in range(1, (N+1)%MOD):
    denominator *= (N-i+1)
    denominator %= MOD

    numerator *= i
    numerator %= MOD

    if i == A or i == B:
        continue

    result += denominator // numerator
    result %= MOD

print(result)

Submission status: Time Limit Exceeded

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

from math import factorial
ans = 0
for i in range(n):
    ans += factorial(n) // factorial(i) // factorial(n - i)

ans -= factorial(n) // factorial(a) // factorial(n - a)
ans -= factorial(n) // factorial(b) // factorial(n - b)
print(ans)

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
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 = 1
for i in range(n-b+1,n+1):
    x2 = x2 * i % MOD
for i in range(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())
k = 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

for i in range(1, N+1):
    if i == A or i == B:
        k -= cmb(N, i)
        if i == B:
            print(k % ((10 ** 9) + 7))
            exit()

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
n,a,b = map(int,input().split())
ans = 0
for i in range(1,n+1):
    if i != a and i !=b:
        ans += factorial(n)/factorial(i)/factorial(n-i)
print(int(ans%(10**9+7)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,a,b= map(int,input().split())
from functools import reduce
from fractions import Fraction
nca = int(reduce(lambda x,y:x*y, (Fraction(n-i, i+1) for i in range(a)), 1) )
ncb = int(reduce(lambda x,y:x*y, (Fraction(n-i, i+1) for i in range(b)), 1) )
print(2**n - 1 - nca - ncb)

Submission status: Time Limit Exceeded

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


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)

s=(2**n-1)%p-cmb(n,a,p)-cmb(n,b,p)

print(s)

Submission status: Time Limit Exceeded

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

#処理
import math
Z=[[-1 for i in range(b+1)] for j in range(n+1)]

def comb(n,r):
    if r==0 or r==n:
        Z[n][r]=1
        return 1
    elif Z[n][r]>0:
        return Z[n][r]
    else:
        Z[n][r]=comb(n-1,r-1)+comb(n-1,r)
        return Z[n][r]
        

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

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
mod=10*9+7

def comb(a,r):
  return factorial(a) / factorial(r) / factorial(a - r)%mod

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb
n,a,b=map(int, input().split())
if n==2:
    print(0)
else:
    ans=2**n-1-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().split())

mod = 10 ** 9 + 7
f = [1]
for i in range(1,2*(10 ** 9)+1):
    f.append((f[-1] * i) % mod)
def comb(n,r):
    return f[n] * (pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod) % mod


ans = pow(2, n, mod) - 1 - comb(n, a) - comb(n, b)
if ans < 0:
    ans += mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
def kai(n):
    kai=1
    for i in range(1,n+1):
        kai=kai*i
    return kai
k=(2**n-1)%(10*9+7)
def com(n,r):
    return (kai(n))/(kai(r)*kai(n-r))
l=(com(n,a))%(10*9+7)
m=(com(n,b))%(10*9+7)
print(int(k-l-m))

Submission status: Time Limit Exceeded

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

def cmb(n,r, mod):
  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 cmb2(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 = list(map(int, input().split()))
mod = 10**9+7

#print((pow(2, n, 1000000000+7) - combinations_count(n, a) - 1 - combinations_count(n, b))%(1000000000+7))
print((pow(2, n, mod) - cmb(n, a, mod) - 1 - cmb(n, b, mod)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
    def calc(n, mod):
        f = 1
        for m in range(1, n + 1):
            f *= m
            f %= mod
        fn = 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 fn, invs

    mod = 10**9+7 
    n,a,b=map(int,input().split())
    ans=0
    fn,invs=calc(n,mod)
    for i in range(1,n+1):
        if i==a or i==b:
            continue
        else:
            ans+=(fn*invs[i]*invs[n-i])%mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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())
if n == 2:
    print(0)
else:
    print((2 ** n - cmb(n, a) - cmb(n, b) - 1) % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
M,A,B = [int(x) for x in 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 = 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 = cmb(n,r,mod)
d = 0
for i in range(N):
    f = cmb(M,i+1,mod)
    d = d + f
    
d1 = cmb(M,A,mod)
d2 = cmb(M,B,mod)
print((d-d1-d2)%mod)

Submission status: Time Limit Exceeded

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

total = 0
cur = 1
for r in range(1, n + 1):
    cur = cur * (n - r + 1) // r
    if a == r or b == r:
        continue
    total += cur
print(total % denom)

Submission status: Time Limit Exceeded

Solution code:
import math
def nCr(n,r):
    f = math.factorial
    return f(n) / f(r) / f(n-r)

n,a,b=map(int,input().split())
r = 2**n - 1
a_c = nCr(n,a)
b_c = nCr(n,b)
inf = 10**9+7
print(int(r-a_c-b_c)%inf)

Submission status: Time Limit Exceeded

Solution code:
def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact

if __name__ == '__main__':
    n ,a, b = map(int, input().split())
    sum = 2 ** n -1
    nf = factorial(n)


    sum = sum - nf / (factorial(a) * factorial(n-a) )
    sum = sum - nf / (factorial(b) * factorial(n-b) )


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

    print(int(sum))

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
N = 2**n - 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:
n, a, b = map(int, input().split())
sub = 0
#１個目のたす
hozonn = 1

for i in range(1,n+1):
    hozonn = (hozonn*(n-i+1)//i)
    if ((i != a) and (i != b)):
        #print(i)
        #print("hozonn",hozonn)
        sub+=hozonn
        sub%=(10**9+7)
print(sub)

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 = 0
for i in range(1,n+1):
    if i in [a,b]:
        continue
    x += cmb(n,i)
print(x%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
from functools import lru_cache
#from scipy.special import comb
from operator import mul
from functools import reduce

n,a,b=map(int,input().split())
'''
def memoize(f): #メモ化関数
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func

@memoize
def memFrac(n):
    if ( n==0 ):
        return 1
    else:
        return n*memFrac(n-1)

def perm(n,r):
    return memFrac(n) // (memFrac(n - r)*memFrac(r))

sys.setrecursionlimit(1000000007)
@lru_cache(maxsize=1000)
def frac(n):
    if n<2:
        return n
    else:
        return n*frac(n-1)

def perm(n,r):
    return frac(n) // (frac(n - r)*frac(r))

a1 = comb(n, a, exact=True)
b1 = comb(n, b, exact=True)

'''
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
a1=cmb(n,a)
b1=cmb(n,b)

print(int(pow(2,n)-a1-b1-1)%1000000009)

Submission status: Time Limit Exceeded

Solution code:
#ax+by=1の解
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]]
m = 10**9+7
#aの逆元(mod m) a,mは互いに素
def mod_inv(a,m):
  x = extgcd(a,m)[0]
  return x%m
#n!(mod m)
fact = [1]
def fact1(n):
  for i in range(1,n+1):
    x = fact[i-1]*i%m
    fact.append(x)


if __name__ == '__main__':
  n,a,b = (int(i) for i in input().split())
  p = 10**9+7
  ans = 0
  fact1(n)
  for i in range(1,n+1):
    #print(i,fact[i],mod_inv(fact[i],p))
    if i == a or i == b:
      continue
    else:
      tmp = fact[n] * (mod_inv(fact[i],p) * mod_inv(fact[n-i],p) % p) % p
      ans = (ans + tmp) % p
  print(ans)

Submission status: Time Limit Exceeded

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

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

ans = power_func(2, n, mod) - 1

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

ans -= comb(n,aa,mod) + comb(n,bb,mod)
ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import scipy.misc as scm

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

t = 0
for i in range(1, n+1, 1):
    if i == a or i == b:
        continue
    t += scm.comb(n, i, exact=True)

print(t)

Submission status: Time Limit Exceeded

Solution code:
#!python3.4.3
import math

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(' '))
result = 2**n - 1
mod = 10**9 + 7

result -= cmb(n, a)
result -= cmb(n, b)

print(result % mod)

Submission status: Time Limit Exceeded

Solution code:
n,a,b = map(int,input().split())
mod = 10 ** 9 + 7
fact = [1]
fact_inv = [1]
for i in range(2*(10**5)+5):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))
fact2 = 1
for i in range(n,n-a,-1):
    fact2 = fact2 * i %mod
fact3 = fact2
for i in range(n-a,n-b,-1):
    fact3 = fact3 * i %mod
#print(fact2,fact3,fact_inv[a],fact_inv[b])
ans = (2 ** n - 1) % mod
ans -= fact2 * fact_inv[a] % mod
if ans < 0:
    ans += mod
ans -= fact3 * fact_inv[b] % mod
if ans < 0:
    ans += mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, a, b = map(int, input().split(' '))
    cmb = []
    cmb.append(n)

    ans = 0
    for i in range(1, n+1):
        if i == a or i == b:
            pass
        else:
            ans += cmb[i-1]
        cmb.append(cmb[-1]*(n-i)/(i+1))

    print(int(ans%(pow(10,9)+7)))

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
	
	num = [n - r + k + 1 for k in range(r)] #numerator(分子)
	den = [k + 1 for k in range(r)] #denominator(分母)
	
	for p in range(2, r + 1):
		pivot = den[p - 1]
		if pivot > 1:
			offset = (n - r) % p
			for k in range(p - 1, r, p):
				num[k - offset] /= pivot
				den[k] /= pivot
	
	result = 1
	for k in range(r):
		if num[k] > 1:
			result *= int(num[k])
	
	return result

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

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

Submission status: Time Limit Exceeded

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

def cmb(n, r):
    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 resolve():
    n,a,b=map(int,input().split())
    sm=pow_r(2,n)-1

    aa=cmb(n,a)%mod
    bb=cmb(n,b)%mod
    sm-=aa
    if sm<0:
        sm+=mod
    sm-=bb
    if sm<0:
        sm+=mod
    
    print(sm)
    







if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

input = sys.stdin.readline
sys.setrecursionlimit(10**9)

div = 10**9 + 7


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


def f(n):
    if n == 1:
        return 1
    return f(n-1) * 2 + 1


def main():
    n, a, b = map(int, input().split())
    score = f(n)
    score -= combination(n, a)
    score -= combination(n, b)
    print(score)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

s=(2**n)-cmb(n,a)-cmb(n,b)-1

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

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def get_fraction_mod(numerator, denominator):
    '''
        returns numerator / denominator (mod MOD)
    '''
    inv = pow(denominator, MOD - 2, MOD)
    return numerator * inv % MOD

def make_facts(n):
    '''
        make factorials
        0!(=1), 1!, 2!, 3! .... n!
    '''
    fact = [1]
    for i in range(n):
        fact.append((fact[i] * (i + 1)) % MOD)
    return fact

def make_combs(n, k):
    '''
        make [C(n, 0), C(n, 1), C(n, 2) ..... C(n, k)]
        n! / (n - k)! k!
    '''
    facts = make_facts(n)
    invs = [] # inverted for fraction
    for fact in facts:
        invs.append(pow(fact, MOD - 2, MOD))

    ret = []
    for i in range(0, n + 1):
        a = facts[n]
        #b = facts[i]
        #c = facts[n - i]
        ret.append(a * invs[i] * invs[n - i] % MOD)
    return ret


def _calc(n):
    ret = 2
    tmp = 1
    while tmp < n:
        print(tmp, ret)
        ret = (ret * ret) % MOD
        tmp *= 2
    if n - tmp > 0:
        t = _calc(n - tmp)
        ret *= t
    return ret

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
        x %= MOD
        n //= 2

    return K * x % MOD


def solve(n: int, a: int, b: int):
    #ret = ((2 ** n) - 1) % MOD
    #ret = (_calc(n) - 1) % MOD
    ret = (pow(2, n, MOD) - 1) % MOD
    #ret = (pow_k(2, n) - 1) % MOD
    combs = make_combs(n, n)
    ret = (ret + MOD * 2 - combs[a] - combs[b]) % MOD
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = int(next(tokens))  # type: int
    b = int(next(tokens))  # type: int
    solve(n, a, b)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)

def mod_combination(n, k, mod):
    # nCk (mod m)
    def mod_permutation(n, k, mod):
        if n<=k:
            return 1
        else:
            return (n * mod_permutation(n-1,k,mod))%mod

    def mod_inv_permutation(k, mod):
        k, mod = int(k), int(mod)
        if k<=1:
            return 1
        else:
            return (pow(k,mod-2,mod) * mod_inv_permutation(k-1, mod))%mod

    return (mod_permutation(n,n-k,mod) * mod_inv_permutation(k, mod))%mod

n,a,b = map(int,input().split())
ans = (2**n - 1) 
k = mod_combination(n, a,10**9+7)
l = mod_combination(n, b,10**9+7)
ans -= k
ans -= l
ans %= 10**9+7
print(ans)

Submission status: Time Limit Exceeded

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

from math import factorial

all = 2 ** n - 1
rem_a = factorial(n) // factorial(a) // factorial(n - a)
rem_b = factorial(n) // factorial(b) // factorial(n - b)

ans = (all - rem_a - rem_b) % (10**9 + 7)

print(ans)

Submission status: Time Limit Exceeded

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

def count(n, r):
    ue = 1
    sita = 1
    for i in range(r):
        ue *= (n-i)
        sita *= (r-i)
    return ue // sita

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