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:
import sys

class modNumber:
    prime = 10**9 + 7
    def __init__(self, num):
        self.num = num % modNumber.prime

    def __add__(self, other):
        if type(other) is int:
            return modNumber(self.num + other)
        return modNumber(self.num + other.num)

    def __sub__(self, other):
        if type(other) is int:
            return modNumber(self.num - other)
        return modNumber(self.num - other.num)

    def __mul__(self, other):
        if type(other) is int:
            return modNumber(self.num * other)
        return modNumber(self.num*other.num)

    def __truediv__(self, other):
        if type(other) is int:
            return modNumber(self.num + modNumber(other).reciprocal())
        return (self*other.reciprocal())

    def __pow__(self, power, modulo=None):
        if type(power) is int:
            answer = 1
            base = self.num
            while True:
                if power == 0:
                    return modNumber(answer)
                elif power%2 == 0:
                    power = power//2
                    base = base*base % modNumber.prime
                else:
                    power = power // 2
                    answer = answer * base % modNumber.prime
                    base = base*base % modNumber.prime
        return self.num.__pow__(power)

    def __str__(self):
        return str(self.num)

    def __int__(self):
        return self.num

    def reciprocal(self):
        ans = modNumber(1)
        buffer = modNumber(self.num)
        exp = modNumber.prime - 2
        while exp:
            if exp & 1:
                ans = ans * buffer
            buffer = buffer * buffer
            exp = exp >> 1
        return ans

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

    total = modNumber(2)**n - 1
    C = modNumber(1)
    for i in range(1, b + 1):
        C = C*modNumber(n-(i-1))/modNumber(i)
        if i == a:
            total -= C
    total -= C

    print(total)

Submission status: Time Limit Exceeded

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

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


Aa = combinations_count(N,a) %(10**9 + 7)
Ab = combinations_count(N,b) %(10**9 + 7)

allN = 2**N % (10**9 + 7)

ans = allN -1 - Aa - Ab

print(ans)

Submission status: Time Limit Exceeded

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

nCa = 1
for i in range(a):
  nCa *= n-i
  nCa %= mod
  nCa *= pow(a-i, mod-2, mod)
  nCa %= mod

nCb = 1
for i in range(b):
  nCb *= n-i
  nCb %= mod
  nCb *= pow(b-i, mod-2, mod)
  nCb %= mod  
  
print((ans-nCa-nCb)%mod)

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
mod = pow(10, 9) + 7
total = pow(2, n) - 1

def comb(N, x):
    numerator = 1
    for i in range(N-x+1, N+1):
        numerator = numerator * i % mod
    denominator = 1
    for j in range(1, x+1):
        denominator = denominator * j % mod
    d = pow(denominator, mod-2, mod)
    return numerator * d

a = comb(n, a)
b = comb(n, b)

print((total -a -b) % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
import time
import collections
from collections import Counter, deque
import itertools
import math
import timeit
import random
from io import BytesIO, IOBase
from bisect import bisect_left

 
#########################
# imgur.com/Pkt7iIf.png #
#########################
 
def sieve(n):
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r
 
def divs(n, start=1):
    divisors = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if n % i == 0:
            if n / i == i:
                divisors.append(i)
            else:
                divisors.extend([i, n // i])
    return divisors
 
def divn(n, primes):
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t
 
def flin(d, x, default=-1):
    left = right = -1
    for i in range(len(d)):
        if d[i] == x:
            if left == -1: left = i
            right = i
    if left == -1:
        return (default, default)
    else:
        return (left, right)

def modpow(b,p,m):
    res=1
    b=b%m
    while(p):
        if p&1:
            res=(res*b)%m
        b=(b*b)%m
        p>>=1
    return res

def mod_inv(a,m):
    return modpow(a,m-2,m)

def ncr(n,r,m):
    res=1
    if r==0:
        return 1
    if n-r<r:
        r=n-r
    p,k=1,1
    while(r):
        res=((res%m)*(((n%m)*mod_inv(r,m))%m))%m
        n-=1
        r-=1
    return res
 
def ceil(n, k): return n // k + (n % k != 0)
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(map(int, input().split()))
def lcm(a, b): return abs(a * b) // math.gcd(a, b)
def prr(a, sep=' '): print(sep.join(map(str, a)))
def dd(): return collections.defaultdict(int)
def ddl(): return collections.defaultdict(list)
 
 
# region fastio
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
	newlines = 0
 
	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = "x" in file.mode or "r" not in file.mode
		self.write = self.buffer.write if self.writable else None
 
	def read(self):
			while True:
					b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
					if not b:
							break
					ptr = self.buffer.tell()
					self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
			self.newlines = 0
			return self.buffer.read()
 
	def readline(self):
			while self.newlines == 0:
					b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
					self.newlines = b.count(b"\n") + (not b)
					ptr = self.buffer.tell()
					self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
			self.newlines -= 1
			return self.buffer.readline()
 
	def flush(self):
			if self.writable:
					os.write(self._fd, self.buffer.getvalue())
					self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
	def __init__(self, file):
			self.buffer = FastIO(file)
			self.flush = self.buffer.flush
			self.writable = self.buffer.writable
			self.write = lambda s: self.buffer.write(s.encode("ascii"))
			self.read = lambda: self.buffer.read().decode("ascii")
			self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

mod=10**9+7
n,a,b=mi()
res=(modpow(2,n,mod)-1-ncr(n,a,mod)-ncr(n,b,mod))%mod
print(res)

#print(res)

Submission status: Time Limit Exceeded

Solution code:
# from .myutil import Combination


class Combination:
    mod = 0
    N = 0
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]

    def __init__(self, mod=10 ** 9 + 7, N=10 ** 9):
        self.mod = mod
        self.N = N
        for i in range(2, self.N + 1):
            self.g1.append((self.g1[-1] * i) % self.mod)
            self.inverse.append((-self.inverse[self.mod % i] * (self.mod // i)) % self.mod)
            self.g2.append((self.g2[-1] * self.inverse[-1]) % self.mod)

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


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

total = (2 ** n) - comb.cmb(n, a) - comb.cmb(n, b) - 1

print(total)

Submission status: Time Limit Exceeded

Solution code:
import math
def count(n, r):
    return math.factorial(n) // (math.factorial(n-r)*math.factorial(r))
n, a, b = map(int, input().split())
sum = 0
for i in range(n):
    sum = sum + count(n,i)
sum = sum - count(n,a) - count(n,b)
print(sum%(10**7))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math


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


n, a, b = map(int, input().split())
count = 0
f = [(i for i in range(n))]
count = 0

for i in range(1, n + 1):
    if (i != a) and (i != b):
        count += combinations_count(n, i)

ans = count % (10**9 + 7)

print(ans)

Submission status: Time Limit Exceeded

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

thenum=pow(10,9)+7


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=pow(2,n)%(thenum)-comb(n,a,thenum)-comb(n,b,thenum)-1
ans=ans%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
L=list(map(int,input().split()))
n=L[0]
a=L[1]
b=L[2]
def comb(n,m):
    return int(math.factorial(n)/(math.factorial(m)*math.factorial(n-m)))
c=2**n-1
c=c-comb(n,a)-comb(n,b)
print(c%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
total = 1
for i in range(n):
  total = (total*2)%(10**9+7)
total -= 1
def factorial(z):
  product = 1
  for i in range(1, z+1):
    product = (product*i)%(10**9+7)
  return product
def ncr(x, y):
  return factorial(x)/(factorial(y)*factorial(x-y))
subt = (ncr(n, a) + ncr(n, b))
print(int(total-subt)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
total = 2**n-1
def factorial(z):
  product = 1
  for i in range(1, z+1):
    product *= i
  return product
def ncr(x, y):
  return factorial(x)/(factorial(y)*factorial(x-y))
subt = ncr(n, a) + ncr(n, b)
print(int(total-subt))

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb

num = [int(n) for n in input().split()]

r = 2 ** num[0] - 1

for i in num[1:]:
  r -= comb(num[0], i, exact=True)
  
print(int(r % (1e9 + 7)))

Submission status: Time Limit Exceeded

Solution code:
ink= input().split()
ink=[int(i) for i in ink]
in1=ink[0]
in2=ink[1]
in3=ink[2]

def nibun(a,e,h):
    #a=int(input("何乗？"))
    b=2#何進法でもできるようにする予定だった
    c=[]
    d=0
    while d==0:
        for i in range(999):
            if b**i<=a and a<b**(i+1):
                c.append(1)
                d=i

    a=a-b**d
    for x in range(d-1,-1,-1):
        if b**(x)<=a:
            a=a-(b**x)
            c.append(1)
        else:
            c.append(0)
        d=d-1
    #print(c)

    #e=int(input("何を？"))
    f=1
    g=0
    #h=int(input("mod?"))#mod
    j=1
    for i in range(len(c)-1,-1,-1):
        j=e
        if c[i]==1:
            for x in range(g):
                j=j*j%h
            f=f*j%h
        g=g+1
    return f
f=nibun(in1,2,10**9+7)

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

######################################################
p=10**9+7

#pは素数とする

#fact[i] : i! modp (0<= i <p) O(p)
fact = [1]
k = 1
for i in range(1,p):
    k = k*i%p
    fact.append(k)


#n! = a p^eとしたときのeを求める (O(logp n)
def mod_e(n,p):
    res = 0
    while n >= p:
        res += n//p
        n = n//p
    return res

#n! = a p^eとしたときのa mod pを求める  (O(logp n)
def mod_fact(n,p):
    if n==0:
        return 1


    res = mod_fact(n//p,p)

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

######################################################

#nCk mod p
def mod_comb(n,k,p):
    if n < 0 or k < 0 or n<k:
        return 0
    e1 = mod_e(n,p)
    e2 = mod_e(k,p)
    e3 = mod_e(n-k,p)
    #pで割り切れる場合
    if e1 > e2 + e3:
        return 0

    #pで割り切れない場合
    a1 = mod_fact(n,p)
    a2 = mod_fact(k,p)
    a3 = mod_fact(n-k,p)
    return a1 * mod_inv(a2*a3%p,p) %p

p =10**9+7

#fact[i] : i! modp (0<= i <p) O(p)
#上だとO(p)なのでnまでにして O(n)にする
fact = [1]
k = 1
for i in range(1,10**5+1):
    k = k*i%p
    fact.append(k)

#10000C4000 mod 10**9+7

j=mod_comb(in1,in2,p)
k=mod_comb(in1,in3,p)
x=(f-1-j-k)
print(x)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial 

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


def rapid_comb(N,K):
    bunsi=bunbo=1
    for i in range(K):
        bunsi*=(N-i)%mod
        bunbo*=(i+1)%mod
    return bunsi*pow(bunbo,mod-2,mod)

ans=((pow(2,N,mod)-1)%mod-rapid_comb(N,a)-rapid_comb(N,b))%mod

#逆元の割り算のmodは、分子*逆元（分母)%modと等価　フェルマーの小定理から、 逆元はpow(b,mod-2,mod)となる

print(ans)

Submission status: Time Limit Exceeded

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


def rapid_comb(N,K):
    bunsi=bunbo=1
    for i in range(K):
        bunsi*=(N-i)%mod
        bunbo*=(i+1)%mod
    return bunsi//bunbo

ans=((pow(2,N,mod)-1)%mod-rapid_comb(N,a)%mod-rapid_comb(N,b)%mod)%mod

print(ans%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math as m

def main(**kwargs):
    mod = 10 ** 9 + 7
    r = repeatSquare(2, n, mod) - 1
    r -= m.factorial(n) * repeatSquare(m.factorial(n - a) * m.factorial(a), mod - 2, mod)
    r -= m.factorial(n) * repeatSquare(m.factorial(n - b) * m.factorial(b), mod - 2, mod)
    r = r % mod
    return r

def repeatSquare(n, p, m):
    if p == 0:
        return 1

    if p % 2 == 0:
        tmp = repeatSquare(n, p/2, m)
        return tmp * tmp % m

    return n * repeatSquare(n, p-1, m)

if __name__ == "__main__":
    cin = np.array(input().split(" ")).astype("int")
    n, a, b = cin

    cout = main(n=n, a=a, b=b)
    print(cout)

Submission status: Time Limit Exceeded

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

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

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

ret = 0

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

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 #出力の制限
N = n + 1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


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

Submission status: Time Limit Exceeded

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math as m

def main(**kwargs):
    mod = 10 ** 9 + 7
    r = int(repeatSquare(2, n, mod) - 1 - m.factorial(n) * repeatSquare(m.factorial(n-a) * m.factorial(a), mod - 2, mod) - m.factorial(n) * repeatSquare(m.factorial(n-b) * m.factorial(b), mod - 2, mod)) % mod
    return r

def repeatSquare(n, p, m):
    if p == 0:
        return 1

    if p % 2 == 0:
        tmp = repeatSquare(n, p/2, m)
        return tmp * tmp % m

    return n * repeatSquare(n, p-1, m)

if __name__ == "__main__":
    cin = np.array(input().split(" ")).astype("int")
    n, a, b = cin

    cout = main(n=n, a=a, b=b)
    print(cout)

Submission status: Time Limit Exceeded

Solution code:
import math

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

ret = 0
for i in range(n):
    if i+1 == a : continue
    if i+1 == b : continue
    ret = ret + (math.factorial(n) // (math.factorial(n-i-1) * math.factorial(i+1)))
    if ret > 1000000007 : ret - 1000000007
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math as m

def main(**kwargs):
    mod = 10 ** 9 + 7
    facts = [m.factorial(i) % mod for i in range(n+1)]
    r = 0

    for i in range(1, n+1):
        if i != a and i != b:
            r += int((facts[n] / facts[n-i] / facts[i]))

    r %= mod
    return r

if __name__ == "__main__":
    cin = np.array(input().split(" ")).astype("int")
    n, a, b = cin

    cout = main(n=n, a=a, b=b)
    print(cout)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math as m

def main(**kwargs):
    mod = 10 ** 9 + 7
    facts = [m.factorial(i) % mod for i in range(n+1)]
 
    r = int((2 ** n - 1 - facts[n] / facts[n-a] / facts[a] - facts[n] / facts[n-b] / facts[b]) % mod)
    return r

if __name__ == "__main__":
    cin = np.array(input().split(" ")).astype("int")
    n, a, b = cin

    cout = main(n=n, a=a, b=b)
    print(cout)

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
            ncr[i]

    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())
mod7 = 10 ** 9 + 7
def power(a,b,mod):
    p = 1
    q = a
    while b != 0:
        if b % 2 == 1:
            p = (p * q) % mod
        q = (q * q) % mod
        b = b // 2
    return p

def fact(n, mod):
    p = 1
    for i in range(1,n+1):
        p = (p * i) % mod
    return p

def divi(a,b,mod):
    p = (power(b, mod-2, mod) * a) % mod
    return p

def combi(n,a,mod):
    nf = fact(n,mod)
    af = fact(a,mod)
    bf = fact(n-a,mod)
    return divi(divi(nf,af,mod),bf,mod)

Answer = power(2, n, mod7) - combi(n, a, mod7) - combi(n, b , mod7) - 1
print(Answer)

Submission status: Time Limit Exceeded

Solution code:
import math
n,a,b = map(int, input().split())
#include a b
all_case = 2 ** n - 1
a_case = math.factorial(n)*pow((math.factorial(a)*math.factorial(n-a)),((10**9+7)-2),10**9+7)
b_case = math.factorial(n)*pow((math.factorial(b)*math.factorial(n-b)),((10**9+7)-2),10**9+7)
res = int((all_case-a_case-b_case)%(10**9+7))
print(res)

Submission status: Time Limit Exceeded

Solution code:

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

mod = 10**9+7

def comb(n,r):
	u = 1
	d = 1
	for i in range(n-r+1,n+1):
		u *= i%mod

	for i in range(1,r+1):
		d *= i%mod
	D = pow(d,mod-2,mod)

	return u*D%mod

ans = pow(2,n,mod)-1-comb(n,a)-comb(n,b)

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb
n, a, b = [int(_) for _ in input().split()]
print(pow(2,n)-1 - comb(n, a, True) - comb(n, b, True))

Submission status: Time Limit Exceeded

Solution code:
# nCk
def comb(n,k,p=10**9+7):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
n, a, b = [int(_) for _ in input().split()]
print(sum([comb(n, _+1) for _ in range(n) if _+1 != a and _+1 != b]))

Submission status: Time Limit Exceeded

Solution code:
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
n, a, b = [int(_) for _ in input().split()]
print(sum([combination(n, _+1) for _ in range(n) if _+1 != a and _+1 != b]))

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

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

# https://tex2e.github.io/blog/crypto/modular-mul-inverse
def xgcd(a, b):
	x0, y0, x1, y1 = 1, 0, 0, 1
	while b != 0:
		q, a, b = a // b, b, a % b
		x0, x1 = x1, x0 - q * x1
		y0, y1 = y1, y0 - q * y1
	return a, x0, y0

# https://tex2e.github.io/blog/crypto/modular-mul-inverse
def modinv(a, m):
	g, x, y = xgcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def combination(n, r):
	ans = 1
	for i in range(n - r + 1, n + 1):
		ans *= i
		ans %= MOD
	for i in range(1, r + 1):
		ans *= modinv(i, MOD)
		ans %= MOD
	return ans

ans = 0
ans += 2 ** n - 1
ans += MOD - combination(n, a)
ans += MOD - combination(n, b)
ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split());
ans = (2 ** n) - 1
p = 1
for i in range(1, a + 1):
	p = p * i
q = 1
for i in range(1, b + 1):
	q = q * i
t = n - a
w = n - b
h = 1
for i in range(t+1, n + 1):
	h = h * i
x = 1
for i in range(w+1, n + 1):
	x = x * i
h = h // p
x = x // q
print(ans - h - x)

Submission status: Time Limit Exceeded

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

for i in range(1, n+1):
  u *= n+1-i
  d *= i
  if i != a and i != b:
    ans += u//d
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

p = 10 ** 9 + 7
N = 10 ** 6       # N は必要分だけ用意する
fact = [1, 1]     # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]      # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

n,a,b = map(int, input().split())
ans = 2**n -1 -cmb(n,a,p) -cmb(n,b,p)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#156D

def comb(n,r,p=7+10**9):
  bunshi = 1
  for i in range(n-r+1, n+1):
    bunshi =bunshi * i % p
  bunbo = 1
  for i in range(1, r+1):
    bunbo = bunbo * i % p
  return bunshi * pow(bunbo, p-2, p)
n,a,b=map(int,input().split())
s=-1+2**n-comb(n,a)-comb(n,b)
print(s%(7+10**9))

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
mod=10**9+7
def choose(n,k):
  x,y=1,1
  for i in range(1,k+1):
    x*=n-k+i
    y*=i
  return x//y%mod
print(pow(2,n,mod)-1-choose(n,a)-choose(n,b))

Submission status: Time Limit Exceeded

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

m = 10 ** 9 + 7

def comb(n, r, m):
  ans = 1
  for i in range(r):
    ans *= (n-i) * pow(i+1, m-2, m) % m
  return ans
  
print((pow(2,n,m)-1-comb(n,a,m)-comb(n,b,m))%m)

Submission status: Time Limit Exceeded

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


a0 = 1
a1 = 1 
for i in range(1, a+1):
  a0 = a0 * (n - i + 1) % 1000000007
  a1 = a1 * i % 1000000007

b0 = 1
b1 = 1 
for i in range(1, b+1):
  b0 = b0 * (n - i + 1) % 1000000007
  b1 = b1 * i % 1000000007

A = (pow(2, n) - 1 - a0 * pow(a1, 1000000005) - b0 * pow(b1, 1000000005)) % 1000000007

def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans = ans * x % 1000000007
        x *= x % 1000000007
        n >>= 1
    return ans % 1000000007

print(A)

Submission status: Time Limit Exceeded

Solution code:
number, a, b = map(int, input().split())
total = 0

def cmb(x, y):
    if y == 0: return 1
    elif y == 1: return x
    denominator = 1
    numerator = 1
    for j in range(1, y+1):
        denominator *= j
        numerator *= x-j+1
    return (numerator//denominator)%(10**9+7)

for i in range(1, number+1):
    if i != a and i != b:
        total += cmb(number, i)
print(total)

Submission status: Time Limit Exceeded

Solution code:
number, a, b = map(int, input().split())
total = 0

def cmb(x, y):
    denominator = 1
    numerator = 1
    for j in range(1, y+1):
        denominator *= j
        numerator *= x-j+1
    return (numerator//denominator)%(10**9+7)

for i in range(1, number+1):
    if i != a and i != b:
        total += cmb(number, i)
print(total)

Submission status: Time Limit Exceeded

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


def pow(m, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return (pow(m, int(n / 2)) ** 2) % mod
    elif n % 2 == 1:
        return (pow(m, int((n - 1) * 0.5)) ** 2 * m) % mod


def conb(n, a):
    mod1 = 1
    mod2 = 1
    for i in range(a):
        mod1 *= n - i
        mod2 *= i + 1
    mod2 = pow(mod2, mod - 2)
    return (mod1 * mod2) % mod


n, a, b = (int(val) for val in input().split())


ans = 1
noa = 1
nob = 1
mod = 1000000007
ans = pow(2, n) - 1 - conb(n, a) - conb(n, b)
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
num_line=input().rstrip().split(" ")
num=int(num_line[0])
a=int(num_line[1])
b=int(num_line[2])

allcase=pow(2,num,1000000007)-1
#print(allcase)

if(a>num//2):
    a=num-a
if(b>num//2):
    b=num-b

abunshi=1
for i in range(num-a+1,num+1):
    abunshi*=i
#print(abunshi)

abumbo=1
for i in range(1,a+1):
    abumbo*=i
#print(abumbo)

abumbo=pow(abumbo,1000000005,1000000007)
#print(abumbo)

aminus=abunshi*abumbo%1000000007
#print(aminus)

bbunshi=1
for i in range(num-b+1,num+1):
    bbunshi*=i
#print(bbunshi)

bbumbo=1
for i in range(1,b+1):
    bbumbo*=i
#print(bbumbo)

bbumbo=pow(bbumbo,1000000005,1000000007)
#print(bbumbo)

bminus=bbunshi*bbumbo%1000000007
#print(bminus)

print((allcase-aminus-bminus)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

num_line=input().rstrip().split(" ")
num=int(num_line[0])
a=int(num_line[1])
b=int(num_line[2])

allcase=pow(2,num,1000000007)-1
#print(allcase)

abunshi=1
for i in range(num-a+1,num+1):
    abunshi*=i
#print(abunshi)

abumbo=1
for i in range(1,a+1):
    abumbo*=i
#print(abumbo)

abumbo=pow(abumbo,1000000005,1000000007)
#print(abumbo)

aminus=abunshi*abumbo%1000000007
#print(aminus)

bbunshi=1
for i in range(num-b+1,num+1):
    bbunshi*=i
#print(bbunshi)

bbumbo=1
for i in range(1,b+1):
    bbumbo*=i
#print(bbumbo)

bbumbo=pow(bbumbo,1000000005,1000000007)
#print(bbumbo)

bminus=bbunshi*bbumbo%1000000007
#print(bminus)

print((allcase-aminus-bminus)%1000000007)

Submission status: Time Limit Exceeded

Solution code:

num_line=input().rstrip().split(" ")
num=int(num_line[0])
a=int(num_line[1])
b=int(num_line[2])

allcase=pow(2,num,1000000007)-1
#print(allcase)

abunshi=1
for i in range(num-a+1,num+1):
    abunshi*=i
#print(abunshi)

abumbo=1
for i in range(1,a+1):
    abumbo*=i
#print(abumbo)

abumbo=pow(abumbo,1000000005,1000000007)
#print(abumbo)

aminus=abunshi*abumbo%1000000007
#print(aminus)

bbunshi=1
for i in range(num-b+1,num+1):
    bbunshi*=i
#print(bbunshi)

bbumbo=1
for i in range(1,b+1):
    bbumbo*=i
#print(bbumbo)

bbumbo=pow(bbumbo,1000000005,1000000007)
#print(bbumbo)

bminus=bbunshi*bbumbo%1000000007
#print(bminus)

print(allcase-aminus-bminus)

Submission status: Time Limit Exceeded

Solution code:
numbers =input().rstrip().split(" ")
N =int(numbers[0])
a =int(numbers[1])
b =int(numbers[2])
import math 

def comb(n,k):
    return math.factorial(n)/(math.factorial(k)*math.factorial(n-k))

c =int(2**N-comb(N,a)-comb(N,b)-1)
d =c%(1000000000+7)
print(d)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,a,b = np.array(input().split()).astype(int)
mod = 10**9+7
import math
def power(x, n):
    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = ans*x%mod
        x = x*x%mod
        n = n >> 1 #ビットシフト
    return ans
def fact(m, n):
    val = 1
    for i in range(m, n + 1):
        val = (val*i)%mod
    return val
def cmb1(N, r):
    A = fact(N-r+1, N)
    B = math.factorial(r)
    return A, B, (A*power(B, mod-2))%mod
  
def cmb2(a, b, A, B):
    A = fact(N-a+1, N-b)*A
    B = fact(b+1, a)*B
    return (A*power(B, mod-2))%mod
if(a>N//2):
    a = N-a
if(b>N//2):
    b = N-b
tmp = max(a,b)
b = min(a,b)
a = tmp
A, B, K1 = cmb1(N, b)
K2 = cmb2(a, b, A, B)
print((power(2, N)-1-K1-K2)%mod)