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


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


def cmb(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

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

    return result


count = mod_pow(2, N, 10 ** 9 + 7) - 1
count -= cmb(N, A) % (10 ** 9 + 7)
count -= cmb(N, B) % (10 ** 9 + 7)
if count < 0:
    count += 10 ** 9 + 7
print(count)

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

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

    return result


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

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

print(ans % mod)

Submission status: Time Limit Exceeded

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

n, a, b= [int(x) for x in stdin.readline().rstrip().split()]

combi = 0
wari = (10 ** 9) + 7

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

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

print(combi % wari)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
import queue
import copy

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


#X = str(input()).split()
#a = [int(x) for x in input().split()]


NAB = str(input()).split()
N = int(NAB[0])
A = int(NAB[1])
B = int(NAB[2])

ans = 2**N-1
A = N-A
B = N-B

ans -= combinations_count(N, A)
ans -= combinations_count(N, B)

ans = ans%1000000007

print(ans)

Submission status: Time Limit Exceeded

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

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 10**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 )

A=cmb(n,a,mod)
B=cmb(n,b,mod)
C=1

for i in range(n):
    C*=2%mod

r=C-1-A-B
print(r)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce
A=list(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 = A[0]
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=3-(4*(1-2**(N-2)))
ans-=cmb(N,A[1],10**9+7)+cmb(N,A[2],10**9+7)

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

Submission status: Time Limit Exceeded

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

lfac = [1,1]
ifac = 1
for i in range(2,n+1):
    ifac = (ifac * i) % mod
    lfac.append(ifac)
    
def comb(n,m):
    res1 = pow(lfac[m],(mod-2),mod)
    res2 = pow(lfac[n-m],(mod-2),mod)
    return (((lfac[n] * res1) % mod) * res2) % mod

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

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r):
  if n - r < r: r = n - r
  if r == 0: return 1
  if r == 1: return n
  numerator = [n - r + k + 1 for k in range(r)]
  denominator = [k + 1 for k in range(r)]
  for p in range(2,r+1):
    pivot = denominator[p - 1]
    if pivot > 1:
      offset = (n - r) % p
      for k in range(p-1,r,p):
        numerator[k - offset] /= pivot
        denominator[k] /= pivot
  result = 1
  for k in range(r):
    if numerator[k] > 1:
      result *= int(numerator[k])
  return result

n,a,b=map(int,input().split())
c=0
for i in range(n):
  if (i+1)!=a and (i+1)!=b:
    j=i+1
    c=c+cmb(n,j)
print(int(c%((10**9)+7)))

Submission status: Time Limit Exceeded

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


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


def cmb(n, k, mod=10**9+7):
    a = framod(n, mod)
    b = framod(k, mod)
    c = framod(n - k, mod)
    return (a * power(b, mod - 2, mod) * power(c, mod - 2, mod)) % mod


def modpow(n, m, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (modpow(n, m, p//2)**2) % m
    return (modpow(n, m, p-1)*n) % m


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


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
mod=100000007
factorial = [1]

def power_func(a,n,p):
    bi=str(format(n,"b"))
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
            res=(res*a) %p
    return res
for i in range(1, n+1):
    factorial.append(factorial[i-1]*i%mod)
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
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) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)
print(power_func(2,n,mod)-1-cmb(n,a,mod)-cmb(n,b,mod))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

mod = 1000000007

def nCr(n, r):

    r = min(r, n-r)

    bunsi = 1
    for i in range(n, n-r, -1):
        bunsi *= i

    bunbo = 1
    for i in range(r, 1, -1):
        bunbo *= i

    return bunsi // bunbo


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

hana_kind_cnt = n

result = 0
for hanataba_koho_select_cnt in range(1, hana_kind_cnt + 1):
    if not(hanataba_koho_select_cnt == a or hanataba_koho_select_cnt == b):
        result += nCr(n, hanataba_koho_select_cnt) % mod

print(int(result))

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input().split(" ")
    n = int(s[0])
    a = int(s[1])
    b = int(s[2])
    nCa = combination(n, a)
    nCb = combination(n, b)
    alla = calcAll(n)
    result = alla - 1 - nCa - nCb
    print(result)


def calcAll(n):
    overflow = 10**9+7
    result = 1
    for i in range(n):
        result = (result * 2) % overflow
    return result

# 互いに素な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 combination(a, b):
    m = 10**9+7
    res = 1
    for i in range(1, a+1):
        res = res*i % m
    for i in range(1, b+1):
        res = res*mod_inv(i, m) % m
    for i in range(1, a-b+1):
        res = res * mod_inv(i, m) % m
    return res


main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, A, B = MAP()


def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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


def main():
    ans = 0
    for i in range(N):
        if i+1 == A or i+1 == B: continue
        ans += cmb(N, i+1, mod)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

total=(2**N[0])-1
A=cmb(N[0],N[1])
B=cmb(N[0],N[2])
ans=(total-A-B)%1000000007
print(ans)

Submission status: Time Limit Exceeded

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

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
n,a,b = [int(i) for i in input().split()]
k = min(n,2*(10**5))
def pow_k(x, n):
    if n == 0:
        return 1

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

    return (K * x - 1) % mod
def modinv(a, mod):
    return pow(a, mod-2, mod)
def combination_list(n, mod):
    lst = [1]
    for i in range(1, k+1):
        lst.append(lst[-1] * (n+1-i) % mod * modinv(i, mod) % mod)
    return lst
ans = pow_k(2,n)
cmb = combination_list(n,mod)
ans %= mod
ans -= cmb[a]
if ans < 0:
    ans += mod
ans -= cmb[b]
if ans <0:
    ans += mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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

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

# ans = power(2, n, MOD) - 1 - (power(2, a, MOD) - power(2, a - 1, MOD)) - (power(2, b, MOD) - power(2, b - 1, MOD))
ans = power(2, n, MOD) - 1 - comb(n, a, MOD) - comb(n, b, MOD)
# - comb(2, a, MOD) - comb(2, b, MOD)

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

M = 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
  
  
n, a, b = map(int, input().split())
print((2**n - cmb(n, a) - cmb(n, b) - 1) % M)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
n,a,b = [int(e) for e in input().split()]
def cmb(n, r):
    u = 1
    d = factorial(r)
    for i in range(n-r+1,n+1):
        u*=i
    return (int(u//d) % int(10e9+7))  
res = 2**n - 1
res -= (cmb(n,a) + cmb(n,b))
res %= int(10e9+7)
print(res)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import math

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

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

ans = 0
mod = 10**9+7

tmp = 0
for i in range(n):
    tmp += combinations_count(n, i+1)
an = combinations_count(n, a)
bn = combinations_count(n, b)
ans = (tmp - an - bn) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int, input().split())
mod,ans=1000000007,2**n-1
#階乗（をmodで割ったあまり）のテーブルを作る
fac=1
finv=[0]*(b+1)
inv=[0]*(b+1)
finv[0]=finv[1]=1
inv[1]=1
for i in range(2,n+1):
    fac*=i%mod
for i in range(2,b+1):
    inv[i]=mod-inv[mod%i]*(mod//i)%mod
    finv[i]=finv[i-1]*inv[i]%mod

def comb_count(n,r): #組み合わせを数える関数
    return fac*(finv[r]*finv[n-r]%mod)%mod

for i in range(1,n+1):
    if i==a:
        ans-=comb_count(n,a)
    elif i==b:
        ans-=comb_count(n,b)
print(ans)

Submission status: Time Limit Exceeded

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

import numpy as np


def prepare(n, MOD):
    nrt = int(n ** 0.5) + 1
    nsq = nrt * nrt
    facts = np.arange(nsq, dtype=np.int64).reshape(nrt, nrt)
    facts[0, 0] = 1
    for i in range(1, nrt):
        facts[:, i] = facts[:, i] * facts[:, i - 1] % MOD
    for i in range(1, nrt):
        facts[i] = facts[i] * facts[i - 1, -1] % MOD
    facts = facts.ravel().tolist()

    invs = np.arange(1, nsq + 1, dtype=np.int64).reshape(nrt, nrt)
    invs[-1, -1] = pow(facts[-1], MOD - 2, MOD)
    for i in range(nrt - 2, -1, -1):
        invs[:, i] = invs[:, i] * invs[:, i + 1] % MOD
    for i in range(nrt - 2, -1, -1):
        invs[i] = invs[i] * invs[i + 1, 0] % MOD
    invs = invs.ravel().tolist()

    return facts,invs

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

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

print(s)

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+=(invs[i]*invs[n-i])%mod
    print((fn*ans)%mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# Code for D - Bouquet
# Use input() to fetch data from STDIN
import sys

[N, 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
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 = 0
for x in range( 1, N + 1 ):
    if x == A or x == B:
        continue

    total += cmb(N, x, mod) % mod

print(total)

Submission status: Time Limit Exceeded

Solution code:

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

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

    return result


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

p = 10 ** 9 + 7

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

Submission status: Time Limit Exceeded

Solution code:
input = raw_input

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

from math import factorial

#def comb(n,k):
#  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):
#  return (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 framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

power_dict = {}
power_dict[(n, 0)] = 1

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

#if True:
if False:
    comb_dict = {}
    comb_dict[(1, 0)] = 1
    comb_dict[(1, 1)] = 1

    zenbu2 = 1
    for i in range(2, n+1):
        new_comb_dict = {}
        new_comb_dict[(i, 0)] = 1
        new_comb_dict[(i, i)] = 1
        for j in range(1, i):
            tmp = comb_dict[(i-1, j-1)] + comb_dict[(i-1, j)]
            tmp = tmp % M
            new_comb_dict[(i, j)] = tmp
            if i == n:
                zenbu2 += tmp

        comb_dict = new_comb_dict


#zenbu = 1
#for i in range(n):
#    zenbu = zenbu * 2
#    zenbu = zenbu % M
#
#    assert zenbu not in values, (i, zenbu)
#    values.append(zenbu)
zenbu = (2 ** n) % M - 1
#zenbu = zenbu2

out = zenbu - comb(n, a, M) - comb(n, b, M)
#out = zenbu - comb_dict[(n, a)] - comb_dict[(n, b)]
out = out % M
print(out)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

data = input()
flower_num = int(data.split()[0])
a = int(data.split()[1])
b = int(data.split()[2])


val = 2**flower_num - combinations_count(flower_num, a) - combinations_count(flower_num, b) - 1

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

Submission status: Time Limit Exceeded

Solution code:
#from scipy.special import comb
import math
(n, a, b) = list(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]

result = 0
result = 2**n - 1

minus_v = 0
for i in (a, b):
#    minus_v += comb(n, i)
    minus_v += math.factorial(n) //(math.factorial(n - i) * math.factorial(i))

result -= minus_v
print(int(result % (10**9 + 7)))

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8

MOD = 1000000007

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

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

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

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

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

def mypow(x, n, m):
    if n == 0:
        return 1
    if n % 2 == 0:
        return mypow(mul(x, x) % m, n / 2, m)
    else:
        return mul(x, mypow(x, n - 1, m) % m)

def main():
    n, a, b = map(int, input().split())
    sumv = 1
    sumv = mypow(2, n, MOD)
    sumv = sub(sumv, nCr(n, a, MOD))
    sumv = sub(sumv, nCr(n, b, MOD))
    sumv = sub(sumv, 1)
    print(sumv)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
import queue
import copy

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


#X = str(input()).split()
#a = [int(x) for x in input().split()]


NAB = str(input()).split()
N = int(NAB[0])
A = int(NAB[1])
B = int(NAB[2])

ans = 2**N-1
 

ans -= combinations_count(N, A)
ans -= combinations_count(N, B)

ans = ans%1000000007

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

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

    return K * x

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


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

mod=1000000007

num=(power(2,n,mod)-1)
anum=cmb(n,a,mod)
bnum=cmb(n,b,mod)

print((num-anum-bnum)%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
a, b, c=map(int,input().split())
if a==b and a==c-1:
  print(0)
elif a==c and a==b-1:
  print(0)
else:
  d=0
  for k in range(1,a+1):
    j=1
    for l in range(1,k):
      j*=(a+1-l)
      j/=l
    d+=j
  b_1=1
  for l in range(1,b+1):
      b_1*=(a+1-l)
      b_1/=l
  c_1=1
  for l in range(1,c+1):
      c_1*=(a+1-l)
      c_1/=l
  d=d-b_1-c_1
  d=d%(10**9+7)
  d=int(d)
  print(d)

Submission status: Time Limit Exceeded

Solution code:
import math

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

# ans = 2 ** n - 1

def binary(n):
    return bin(n)[2:]

# バイナリ法
def pow_by_binary_exponentiation(a, x, n): # a^x mod n
    x = [int(b) for b in binary(x)]
    y = a
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * a) % n
    return y
	
ans = pow_by_binary_exponentiation(2, n, MOD)

ans -= 1

fac = [1]
inv = [1]

for i in range(1, n + 1) :
	fac.append(fac[-1] * i % MOD)
	inv.append(pow(fac[-1], MOD - 2, MOD))

ans -=  fac[n] * inv[a] * inv[n - a] % MOD
ans -=  fac[n] * inv[b] * inv[n - b] % MOD

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7

n,a,b=map(int,input().split())
com=[]
ans=pow(2,n,MOD)-1


def cmb(k):
    ret=1
    x,y=1,1
    for i in range(1,k+1):
        x*=(n-i+1)%MOD
        x%=MOD
        y*=i
    ret=x*pow(y%MOD,MOD-2,MOD)%MOD

    return ret%MOD



ans-=(cmb(a)+cmb(b))%MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

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

    return result


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

MOD = 10**9 + 7

s = 2**n

a1 = cmb(n,a)
a2 = cmb(n,b)

print((s-a1-a2)%MOD-1)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n, a, b=map(int, input().split())
M=10**9 +7
SUM=0
now=n
for i in range(1,n+1):
  if i==1:
    now=n
  else:
    now=now*(n-i+1)/i%M
  if not (i==a or i==b):
    SUM+=now%M
    



print(int(SUM%M))

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

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

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

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
n, a, b = map(int, input().split())
a = factorial(n) / factorial(a) / factorial(n - a)
b = factorial(n) / factorial(b) / factorial(n - b)
print(int(2**n-a-b-1))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math

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

hanataba = 2**n

aconb = math.factorial(n) // (math.factorial(n - a) * math.factorial(a))
bconb = math.factorial(n) // (math.factorial(n - b) * math.factorial(b))

hanataba -= aconb
hanataba -= bconb
print(hanataba-1)

Submission status: Time Limit Exceeded

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

a,b,c=map(int,input().split(' '))
count=0

for i in range(1,a+1):
    count+=com(a,i)
count-=com(a,b)
count-=com(a,c)
print(int(count)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
# from datetime import datetime

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

# time1 = datetime.now()

noab = 2**n -1

def exc(n,a):
    a = min(a,(n-a))
    nseki = 1
    for i in range(a):
        nseki *= n-i
    aseki = 1
    for j in range(1,a+1):
        aseki *= j
    return(nseki // aseki)
        

nCa = exc(n,a)
nCb = exc(n,b)

patall = int(noab - nCa - nCb)

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

# time2 = datetime.now()
# print(time2 - time1)

Submission status: Time Limit Exceeded

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

ntmp = n
nottmp = 1
tmpin = [1, 1]

result = 0

for i in range(n):
    tmpin[0] *= ntmp
    tmpin[1] *= nottmp
    if nottmp != a and nottmp != b:
        result += ((tmpin[0] // tmpin[1]) % (10 ** 9 + 7))
    ntmp -= 1
    nottmp += 1
    

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
n, a, b = map(int, input().split())

def pow(x, n):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = ans*x
    x = x*x
    n = n >> 1 #ビットシフト
  return ans

sum1 = pow(2, n)
sumwhole = sum1 -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

p = comb(n,a,10**9+7)
q = comb(n,b,10**9+7)

sumf1 = sumwhole - p - q
sumf = sumf1 % (10**9+7)
print(sumf)