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

M = 10**9 + 7

import math

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

from scipy.misc import comb

all_pattern = my_pow(2, n)
dislike = comb(n, a, exact=True) + comb(n, b, exact=True)
dislike = dislike % M

print( (all_pattern - dislike - 1) )

Submission status: Time Limit Exceeded

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

fac = [0 for _ in range(n+1)]
inv = [0 for _ in range(n+1)]
finv = [0 for _ in range(n+1)]

fac[0] =fac[1]= 1
inv[0] =inv[1]= 1
finv[0] = finv[1] = 1

p = 10**9 + 7
#p = 31
#inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
for i in range(2,n+1):
    fac[i] = (fac[i-1]*i)%p
    inv[i] = (p - inv[p%i]*int(p/i)%p)%p
    finv[i] = (finv[i-1]*inv[i])%p
    
#print(fac)
#print(inv)
#print(finv)

def cal(m,k):
    return fac[m]*(finv[k]*finv[m-k]%p)%p

ans=pow(2,n,p) - 1
ans = (ans - cal(n,a) - cal(n,b))%p

if(ans<0):
    ans = -1*ans

print(ans)

Submission status: Time Limit Exceeded

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

fac = [0 for _ in range(n+1)]
inv = [0 for _ in range(n+1)]
finv = [0 for _ in range(n+1)]

fac[0] =fac[1]= 1
inv[0] =inv[1]= 1
finv[0] = finv[1] = 1

p = 10**9 + 7
#p = 31
#inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
for i in range(2,n+1):
    fac[i] = (fac[i-1]*i)%p
    inv[i] = (p - inv[p%i]*int(p/i)%p)%p
    finv[i] = (finv[i-1]*inv[i])%p
    
#print(fac)
#print(inv)
#print(finv)

def cal(m,k):
    return fac[m]*(finv[k]*finv[m-k]%p)%p

ans = (2**n -1)%p
ans = (ans - cal(n,a) - cal(n,b))%p

if(ans<0):
    ans = -1*ans

print(ans)

Submission status: Time Limit Exceeded

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

fac = [0 for _ in range(n+1)]
inv = [0 for _ in range(n+1)]
finv = [0 for _ in range(n+1)]

fac[0] =fac[1]= 1
inv[0] =inv[1]= 1
finv[0] = finv[1] = 1

p = 10**9 + 7
#p = 31
#inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
for i in range(2,n+1):
    fac[i] = (fac[i-1]*i)%p
    inv[i] = (p - inv[p%i]*int(p/i)%p)%p
    finv[i] = (finv[i-1]*inv[i])%p
    
#print(fac)
#print(inv)
#print(finv)

def cal(m,k):
    return fac[m]*(finv[k]*finv[m-k]%p)%p

ans = 0
for i in range(1,n+1):
    if not (i == a or i== b):
        #print(cal(n,i))
        ans += cal(n,i)
        ans = ans%p

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
[n,a,b]=list(map(int,input().split(" ")))
L=pow(2,n)-1-math.factorial(n)/math.factorial(n-a)/math.factorial(a)-math.factorial(n)/math.factorial(n-b)/math.factorial(b)
if L==0:
  print(0)
else:
  print(int(L%(10**9+7)))

Submission status: Time Limit Exceeded

Solution code:
import math
[n,a,b]=list(map(int,input().split(" ")))
count=0
L=0
for i in range(1,n+1):
  M=math.factorial(n)/math.factorial(n-i)/math.factorial(i)
  if i!=a and i!=b:
    L+=M
    count+=1
if count==0:
  print(0)
else:
  print(int(L%(10**9+7)))

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 10 ** 9 + 7


def cmb(n, r):
    total = 1
    for i in range(r):
        total *= (n - i) % MOD
    return total * pow(math.factorial(r), MOD - 2, MOD) % MOD


if __name__ == '__main__':
    n, a, b = list(map(int, input().split(" ")))

    total = pow(2, n, MOD)
    a_total = cmb(n, a)
    b_total = cmb(n, b)
    # print((total - a_total - b_total - 1) % MOD)

    print(max(0, (pow(2, n, MOD) - ((cmb(n, a) + cmb(n, b)) % MOD) - 1) % MOD))

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 10 ** 9 + 7
n, a, b = list(map(int, input().split(" ")))


def cmb(r):
    total = 1
    for i in range(r):
        total *= (n - i) % MOD
    return total * pow(math.factorial(r), MOD - 2, MOD) % MOD


total = pow(2, n, MOD)
a_total = cmb(a)
b_total = cmb(b)
print((total - a_total - b_total - 1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 10 ** 9 + 7


def cmb(n, r):
    total = 1
    for i in range(r):
        total *= (n - i) % MOD
    return total * pow(math.factorial(r), MOD - 2, MOD) % MOD


if __name__ == '__main__':
    n, a, b = list(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)

    total = pow(2, n, MOD)
    # print(total)
    a_total = cmb(n, a)
    # print(a_total)
    b_total = cmb(n, b)
    print((total - a_total - b_total - 1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import math
n,a,b=map(int,input().split())
def comb(n,r):
    return math.factorial(n)/(math.factorial(n-r)*math.factorial(r))

cnt=0
for k in range(1,n+1):
    cnt+=comb(n,k)
cnt=cnt-comb(n,a)-comb(n,b)
ans=int(cnt%(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

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

Submission status: Time Limit Exceeded

Solution code:
import math
numbers =input().rstrip().split(" ")
N =int(numbers[0])
a =int(numbers[1])
b =int(numbers[2])
Ya=math.factorial(a)
Yb=math.factorial(b)
Xa=1
Xb=1
for i in range(a):
    Xa=Xa*(N-i)
for i in range(b):
    Xb=Xb*(N-i)

d=1000000007
#answer is 2**N-nca-ncb-1 mod d
A=pow(2,N)
B=Xa*pow(Ya,d-2)
C=Xb*pow(Yb,d-2)
answer=(A+B+C-1)%d
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from functools import reduce


def comb_mod(n, a, mod=10**9+7):
    # https://img.atcoder.jp/abc156/editorial.pdf
    # nCk は, k回の積で計算できる
    num = reduce(lambda x, y: x * y % mod, range(n, n - a, -1))
    den = reduce(lambda x, y: x * y % mod, range(1, a + 1))
    # nCk mod = X/Y mod = X * Y^(10**9+7-2) mod
    return num * pow(den, mod - 2, mod) % mod


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

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

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
binary=(format(n,"b"))#二進数に変換
templi=[binary[i] for i in range(len(str(binary)))]
templi.reverse()
res=2
beki=1
for i in range(0,len(templi)):
    if templi[i]=="1":
        beki*=res
    else:
        beki*=1
    res=res**2
firs=beki-1
#conbination_algorithm
def kaijo(k):
    sum=1
    for j in range(1,k+1):
        sum*=j
    return sum
def comb(n,k):
    ans=int(kaijo(n))/(int(kaijo(k))*int(kaijo(n-k)))
    return int(ans)
#subtract
sub_1=comb(n,a)+comb(n,b)
print((firs-sub_1)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
mod = 10**9+7
def comb(n, r, mod):
    if r == 0 or r == n:
        return 1
    r = min([r, n-r])
    x, y = 1, 1
    for i in range(1, r+1):
        x *= n+1-i
        y *= i
    return x*pow(y, mod-2, mod)%mod

ans = (pow(2, n, mod)+3*mod-1-comb(n, a, mod)-comb(n, b, mod))%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
mod = 10**9+7
def comb(n, r, mod):
    if r == 0 or r == n:
        return 1
    r = min([r, n-r])
    x, y = 1, 1
    for i in range(1, r+1):
        x *= n+1-i
        y *= i
    return x*pow(y, mod-2, mod)%mod

ans = (2**n+3*mod-1-comb(n, a, mod)-comb(n, b, mod))%mod
print(ans)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

def comb_mod(n, r, mod):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    else:
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fac.append(fac[-1] * i % mod)
            inv.append(-inv[mod % i] * (mod // i) % mod)
            finv.append((finv[-1] * inv[-1]) % mod)
        return int(fac[n] * finv[r] * finv[n - r] % mod)

m = pow(2,n,mod) - 1

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

s = perm(n,a) * pow(math.factorial(a),mod-2,mod)
# print(s)

t = perm(n,b) * pow(math.factorial(b),mod-2,mod)
# print(t)

ans = m - s - t

print(ans%mod)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

def comb_mod(n, r, mod):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    else:
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fac.append(fac[-1] * i % mod)
            inv.append(-inv[mod % i] * (mod // i) % mod)
            finv.append((finv[-1] * inv[-1]) % mod)
        return int(fac[n] * finv[r] * finv[n - r] % mod)

m = pow(2,n,mod) - 1

a = comb_mod(n,a,mod)

b = comb_mod(n,b,mod)

ans = m - a - b

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
n,a,b = 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

def comb_mod(n, r, mod):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    else:
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fac.append(fac[-1] * i % mod)
            inv.append(-inv[mod % i] * (mod // i) % mod)
            finv.append((finv[-1] * inv[-1]) % mod)
        return int(fac[n] * finv[r] * finv[n - r] % mod)

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

a = comb_mod(n,a,mod)

b = comb_mod(n,b,mod)

ans = m - a - b

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
firs=2**n-1
#conbination_algorithm
def kaijo(k):
    sum=1
    for j in range(1,k+1):
        sum*=j
    return sum
def comb(n,k):
    ans=int(kaijo(n))/(int(kaijo(k))*int(kaijo(n-k)))
    return int(ans)
#subtract
sub_1=comb(n,a)+comb(n,b)
print((firs-sub_1)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
ans = ((1 << n) - 1)
A = 1
for i in range(a):
  A *= (n - i)
for i in range(1, a + 1):
  A //= i

B = 1
for i in range(b):
  B *= (n - i)
for i in range(1, b + 1):
  B //= i
print(ans - A - B)

Submission status: Time Limit Exceeded

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

def kurikaeshi(x, n, mod):
    if n == 1:
        return x%mod
    elif n %2 == 0:
        return kurikaeshi(x, n//2, mod)**2%mod
    elif n %2 == 1:
        return kurikaeshi(x, n//2, mod)**2*x%mod
    
def combination(n, a, mod):
    bunbo = 1
    bunshi = 1
    for i in range(a):
        bunshi *= n-i
        bunbo *= a-i
        
    return bunshi*kurikaeshi(bunbo, mod-2, mod)%mod
        
        
mod = 1000000007
answer = kurikaeshi(2, n, mod)
answer -= 1
answer -= combination(n, a, mod)
answer -= combination(n, b, mod)
print(answer%mod)

Submission status: Time Limit Exceeded

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

def kurikaeshi(x, n, mod):
    if n == 1:
        return x%mod
    elif n %2 == 0:
        return kurikaeshi(x, n//2, mod)**2%mod
    elif n %2 == 1:
        return kurikaeshi(x, n//2, mod)**2*x%mod
    
    
def combination(n, a, mod):
    bunbo = 1
    bunshi = 1
    for i in range(a):
        bunshi *= n-i
        bunbo *= a-i
        
    return bunshi*(pow(bunbo, mod-2, mod)%mod)
        
        
mod = 1000000007
answer = pow(2, n, mod)
answer -= 1
answer -= combination(n, a, mod)
answer -= combination(n, b, mod)
print(answer%mod)

Submission status: Time Limit Exceeded

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

def kurikaeshi(x, n, mod):
    if n == 1:
        return x%mod
    elif n %2 == 0:
        return kurikaeshi(x, n//2, mod)**2%mod
    elif n %2 == 1:
        return kurikaeshi(x, n//2, mod)**2*x%mod
    
def combination(n, a, mod):
    bunbo = 1
    bunshi = 1
    for i in range(a):
        bunshi *= n-i
        bunbo *= a-i
        
    return bunshi*(kurikaeshi(bunbo, mod-2, mod)%mod)
        
        
mod = 1000000007
answer = kurikaeshi(2, n, mod)
answer -= 1
answer -= combination(n, a, mod)
answer -= combination(n, b, mod)
print(answer%mod)

Submission status: Time Limit Exceeded

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

def kurikaeshi(x, n, mod):
    if n == 1:
        return x
    elif n %2 == 0:
        return kurikaeshi(x, n//2, mod)**2%mod
    elif n %2 == 1:
        return kurikaeshi(x, n//2, mod)**2*x%mod
    
    
def combination(n, a, mod):
    bunbo = 1
    bunshi = 1
    for i in range(a):
        bunshi *= n-i
        bunbo *= a-i
        
    return bunshi*(kurikaeshi(bunbo, mod-2, mod)%mod)
        
        
mod = 10*9+7
answer = kurikaeshi(2, n, mod)
answer -= 1
answer -= combination(n, a, mod)
answer -= combination(n, b, mod)
print(answer%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().strip()
n,a,b=map(int,input().split())
mod=10**9+7
def fur(n,r):
    p,q = 1,1
    for i in range(r):
        p = p*(n-i)%mod
        q = q*(i+1)%mod
    return p * pow(q,mod-2,mod)%mod
print(((2**n)-1-fur(n,a)-fur(n,b))%mod)

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
mod=10**9+7
def fur(n,r):
    p,q = 1,1
    for i in range(r):
        p = p*(n-i)%mod
        q = q*(i+1)%mod
    return p * pow(q,mod-2,mod)%mod
print(((2**n)-1-fur(n,a)-fur(n,b))%mod)

Submission status: Time Limit Exceeded

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

def comb(n, k, p, exp_table):
  """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 = power_func(exp_table[k], p-2, p)
  c = power_func(exp_table[n-k], p-2, p)
  return (a*b*c)%p
  
n, a, b = map(int, input().split())

MOD = 10**9 + 7
exp_table = [1]
for i in range(1, b+1):
    exp_table.append(exp_table[-1]*i%MOD)


print(2**n - 1 - comb(n, a, MOD, exp_table) - comb(n, b, MOD, exp_table))

Submission status: Time Limit Exceeded

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

def comb(n, k, p, exp_table):
  """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 = exp_table[n]
  b = power_func(exp_table[k], p-2, p)
  c = power_func(exp_table[n-k], p-2, p)
  return (a*b*c)%p
  
n, a, b = map(int, input().split())

MOD = 10**9 + 7
exp_table = [1]
for i in range(1, n+1):
    exp_table.append(exp_table[-1]*i%MOD)


print(2**n - 1 - comb(n, a, MOD, exp_table) - comb(n, b, MOD, exp_table))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def comb_mod(n, a, m):
  if a > n:
    return 0
  a = min(a, n-a)
  # tbl = [[0]*(a+1) for _ in range(2)]
  tbl = np.zeros((2, a+1), dtype=np.int64)
  tbl[0][0] = 1
  tbl[1][0] = 1
  # for i in tqdm(range(n)):
  for i in range(n+1):
    # tbl[i%2][0] = 1
    tbl[i%2][1:] = (tbl[(i+1)%2][1:] + tbl[(i+1)%2][:-1]) % m
    # for k in range(min(i+1, len(tbl[i%2]))):
    #   if i == k:
    #     tbl[i%2][k] = 1
    #   elif i < k:
    #     tbl[i%2][k] = 0
    #   elif k == 0:
    #     tbl[i%2][k] = 1
    #   else:
    #     tbl[i%2][k] = (tbl[(i-1)%2][k-1] + tbl[(i-1)%2][k]) % m
  return tbl[(n+1)%2][a]

n, a, b = map(int, input().split(' '))
c = 0
for i in range(1, n+1):
  if i == a or i == b:
    continue
  c += comb_mod(n, i, 1000000007)
print(c)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

if a > n//2:
	a = -1 * (a-n)
if b > n//2:
	b = -1 * (b-n)

#print(a,b)

num = 1
ans = 1
for i in range(n//2):
	num = (num * (n-i)) // (i+1)
	ans += num * 2
	if a == i+1:
		ans -= num
	if b == i+1:
		ans -= num
if n % 2 == 0:
	ans -= num
if a == 0:
	ans -= 1
if b == 0:
	ans -= 1

print(ans)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

ans = 0
num = 1
for i in range(n):
	num = (num * (n-i)) // (i+1)
	if a != i+1 and b != i+1:
		ans += num

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

ans = 0
mod = 10 ** 9 + 7

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)

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def comb(n, i):
  tbl = [[0]*(i+1) for _ in range(n+1)]
  for n in range(len(tbl)):
    for k in range(len(tbl[n])):
      if n == k:
        tbl[n][k] = 1
      elif n < k:
        tbl[n][k] = 0
      elif k == 0:
        tbl[n][k] = 1
      else:
        tbl[n][k] = tbl[n-1][k-1] + tbl[n-1][k]
  return tbl[n][i]

n, a, b = map(int, input().split(' '))
c = 0
for i in range(1, n+1):
  if i == a or i == b:
    continue
  c += comb(n, i)
  c %= 1000000007
print(c)

Submission status: Time Limit Exceeded

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

ans = 0 
mod = 7+10**9

def expo(x,n):
  var = 1
  while n>0:
    if n%2 == 1:
      var = (var*x) % mod
    x = (x*x)%mod
    n = n>>1
  return var

def combi(n,k):
  N = 1
  mK = 1
  mN_K = 1
  for i in range(1,n+1):
    N = (N*i)%mod
  for i in range(1,k+1):
    mK = (mK * expo(i,mod-2))%(mod)
  for i in range(1,n-k+1):
    mN_K = (mN_K*expo(i,mod-2))%mod
  return (((N*mK)%mod)*mN_K)%mod

print(expo(2,N)-1-combi(N,A)-combi(N,B))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

def comb(n, k, p):
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 0
    n_fact = factorial(n) % p
    k_fact = factorial(k) % p
    n_k_fact = factorial(n - k) % p
    return (n_fact * pow(k_fact, p - 2, p) * pow(n_k_fact, p - 2, p)) % p

mod = 10**9 + 7
n, a, b = map(int, input().split())
result = pow(2, n) - 1

for i in (a, b):
    result -= comb(n, i, mod)

result %= mod

print(result)

Submission status: Time Limit Exceeded

Solution code:
def pre_cmb_mod(n, mod):
    if n == 0:
        return [1], [1]
    fact = [1, 1]
    inv = [0, 1]
    factinv = [1, 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)
    return fact, factinv


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


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

fact, factinv = pre_cmb_mod(n, mod)

result = 0
for r in range(1, n+1):
    if r == a or r == b:
        continue
    result += cmb_mod(n, r, mod, fact, factinv)
    result %= mod

print(result)

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
ans = 2 ** n -1
val = 1
val2 = 1
for i in range(a):
    val *= n - i
    val2 *= i + 1
ans -= (val // val2)
val = 1
val2 = 1
for i in range(b):
    val *= n - i
    val2 *= i + 1
ans -= (val // val2)
print(ans % (int(1e9) + 7))

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:
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:
n,a,b = list(map(int,input().split()))
mod = 10**9 + 7
ans = (pow(2,n) - 1)% mod
numerator = 1
denominator = 1

for i in range(1,n+1):
    numerator = (numerator*(n-i+1))%mod
    denominator = (denominator*i)%mod
    if i == a or i == b:
        ans -= (numerator*pow(denominator,mod-2,mod))%mod
        if i == b:
            break

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
#binary exponentiation for 2^big number -1
#sum of n choose. ... 2^n -1
# how to compute n choose a
# euler's quotient theorem
# special case fermats little theoreom


#n kinds of flowers, 1 of each kind
# choose 1 more of each to make bouquet
# a b, total num of flowers cannot be a or b
# how many diff ouquets can she make?
# find the count modulo (10^9 + 7)

#two bouquets are considered different

# (x^y)%p
def powerMod(x,y,p):
    #initialize result
    res = 1
    #update x if it is more than or equal to p
    x = x%p
    
    while (y>0):
        #if y is odd, multiply x with result
        if ((y&1)==1):
            res = (res*x)%p
        
        #y must be even now
        y = y >> 1 #y = y/2
        x = (x*x)%p
    return res

def power(x,y):
    #initialize result
    res = 1
    while (y>0):
        #if y is odd, multiple x with result
        if((y&1)==1):
            res = res*x
        
        #y is even
        y = y >> 1 #divide y by 2
        x = x*x
    return res


input = [int(x) for x in input().split()]
numFlowers = input[0]
a = input[1]
b = input[2]

allchoices = power(2,numFlowers)-1

#compute n choose k in O(k) time and O(1) space
def binomial(n,k):
    #since C(n,k) = C(n,n-k)
    if(k>n-k):
        k = n=k
    
    #initialize result
    res = 1
    #calculate value of simplified n choose k expansion
    for i in range(k):
        res = res*(n-i)
        res = res/ (i+1)
    return res

aX = 1
aY = 1

#need to compute x and y for a and b, clearly separate them
for i in range(a):
    aX = aX*(numFlowers-i)
    aY = aY*(i+1)


bX = 1
bY = 1

#need to compute x and y for a and b, clearly separate them
for i in range(b):
    bX = bX*(numFlowers-i)
    bY = bY*(i+1)

tenToNine = power(10,9)
#subtract and we're done

countA = aX*powerMod(aY,tenToNine+7-2,tenToNine+7)
countB = bX*powerMod(bY,tenToNine+7-2,tenToNine+7)

numBouquet = (allchoices-countA-countB)%(tenToNine+7)

print(numBouquet)

Submission status: Time Limit Exceeded

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

def comb(n, r):
    x = 1; y = 1
    for i in range(r):
        x *= n-i
        y *= r-i
    return x*pow(y, MOD-2, MOD)

print((pow(2, n, MOD)-1 -comb(n, a) -comb(n, b)) % MOD)

Submission status: Time Limit Exceeded

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

def comb(n, r):
    x = 1; y = 1
    for i in range(r):
        x *= (n-i) % MOD
        y *= (r-i) % MOD
    return (x*pow(y, MOD-2, MOD)) % MOD

print((pow(2, n, MOD)-1 -comb(n, a) -comb(n, b)) % MOD)

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

l = set(range(1, n+1))
l.remove(a)
l.remove(b)
print(sum([combinations_count(n, r) for r in l])%(10**9+7))

Submission status: Time Limit Exceeded

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

def nCr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i in range(r)]
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] = (numerator[k - offset] *pow(pivot, mod-2, mod))%mod
                denominator[k] = (denominator[k] *pow(pivot, mod-2, mod))%mod
    result = 1
    for k in range(r):
        if numerator[k] > 1: 
            result *= numerator[k]
            result %= mod
    return int(result)

ans = ((pow(2, n, mod)-1)%mod-nCr(n, a)-nCr(n, b))%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
ans = 0
for i in range(2 ** n):
    num = format(i, 'b')
    count = num.count('1')
    if count == 0 or count == a or count == b:
        pass
    else:
        ans += 1
ans %= 10 ** 9 + 7
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

#参考: https://qiita.com/ophhdn/items/e6451ec5983939ecbc5b
def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans


def main():
    n,a,b  = map(int, input().split())
    #a,bの制約がなければ，2^n - 1通りだけ使える
    # 2^n ^ nCa - nCb
    mod = 10**9 +7
    
    mab = max(a, b)
    ncr = [1 for i in range(mab+1)]
    for i in range(mab+1):
        if i == 0:
            continue
        else:
            ncr[i] = ncr[i-1] * (n-i+1) // i % mod

    n2 = pow(2, n) 
    nca = ncr[a]
    ncb = ncr[b] 
    print((n2 - nca - ncb - 1) % mod )
    eprint(n2)
    eprint(nca)
    eprint(ncb)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
ans = 0
for i in range(n):
    if (i + 1) == a or (i + 1) == b:
        pass
    else:
        count = 1
        for j in range(i + 1):
            count *= n - j
            count /= (i + 1) - j
        ans += count
ans = int(ans % (10 ** 9 + 7))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Mar  3 00:13:14 2020

@author: Kanaru Sato
"""
import math


mod = 10**9+7 #出力の制限
nn = 10**10
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

T = 7+10**9
Max = 2*(10**5)

Nocase = c_count(N,a,T)+c_count(N,b,T)

S = 0

if N <= Max:
    for i in range(1,N+1):
        S += c_count(N,i,T)
else:
    for i in range(1,Max+1):
        S += c_count(N,i,T)

Case = S - Nocase
ans = Case % T
print(ans)

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
    
n,a,b = map(int,input().split())
mod = 10**9 + 7
def pow(n,b,mod):
  if n == 0: return 1
  if n % 2: return 2 * pow(n//2,b,mod)**2 % mod
  else: return pow(n//2,b,mod)**2 % mod
print((pow(n,2,mod) - 1 - cmb(n,a,mod) - cmb(n,b,mod))%mod)

Submission status: Time Limit Exceeded

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

def pow2(n,base):
    if n==1:return base
    if n%2==0:return pow2(n//2,base)**2%mod
    else:return base*pow2(n//2,base)**2%mod

def fac(n,a):
    ans=1
    for i in range(n,n-a,-1):
        ans*=i
        ans%=mod
    return ans

def inv_fac(n):
    ans=1
    for i in range(1,n+1):
        ans*=pow2(mod-2,i)
        ans%=mod
    return ans



ans=pow2(n,2)-fac(n,a)*inv_fac(a)-fac(n,b)*inv_fac(b)
print(ans%mod-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
mod = 10**9+7
bouquet = 0
n,a,b = map(int,input().split())
for i in range(1,n+1):
    if i != a and i != b:
        bouquet += cmb(n,i) % mod
        bouquet = bouquet % mod
print(bouquet % mod)

Submission status: Time Limit Exceeded

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