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

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x)
            if isinstance(other, ModInt)
            else ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x)
            if isinstance(other, ModInt)
            else ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x)
            if isinstance(other, ModInt)
            else ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(self.x * pow(other.x, MOD - 2, MOD))
            if isinstance(other, ModInt)
            else ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD))
            if isinstance(other, ModInt)
            else ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x)
            if isinstance(other, ModInt)
            else ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(other.x * pow(self.x, MOD - 2, MOD))
            if isinstance(other, ModInt)
            else ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD))
            if isinstance(other, ModInt)
            else ModInt(pow(other, self.x, MOD))
        )


def main():
    N, A, B = map(int, input().split())
    total = ModInt(2) ** N - 1

    num_a = ModInt(1)
    for i in range(A):
        num_a *= N - i
        num_a /= A - i

    num_b = ModInt(1)
    for i in range(B):
        num_b *= N - i
        num_b /= B - i

    total -= num_a
    total -= num_b
    print(total)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000



d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

n, a, b = LI()


n_ = n# まで対応
fun = [1 for i in range(n_+1)]
for i in range(1, n_ + 1):
    fun[i] = fun[i-1] * i % mod

rev = [1 for i in range(n_+1)]
rev[n_] = pow(fun[n_], mod-2, mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1) % mod

def nCr(n,r):
    if n <= 0 or r < 0 or r> n:return 0
    
    return fun[n]*rev[r]%mod*rev[n-r]%mod

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

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce
def comb(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(int(pow(2, n) - 1 - comb(n, a) - comb(n, b)) % (10 ** 9 + 7))

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

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

for i in range(n):
  ans+=cmb(n,i)%(10**9+7)
  ans%=(10**9+7)
ans-=cmb(n,a)
ans-=cmb(n,b)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a,b = map(int,input().split())
# nCr(r:1~n)-nCa-nCb
mod = 10**9+7
def comb(n,r):
    res = 1
    for i in range(1,n+1):
        res = res*i%mod
    for i in range(1,r+1):
        res = res*pow(i,mod-2,mod)%mod
    for i in range(1,n-r+1):
        res = res*pow(i,mod-2,mod)%mod
    return res
ans = 0
for i in range(1,n+1):
    ans = (ans+comb(n,i))%mod
print((ans-comb(n,a)-comb(n,b))%mod)

Submission status: Time Limit Exceeded

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

di = 10**9+7

def pow_k(x,nt):
    if nt==0:
        return 1
    K=1
    while nt>=2:
        if nt%2!=0:
            K=(K*x)%di
        x=(x*x)%di
        nt//=2
    return (K*x)%di

ans = pow_k(2,n)-1

mi = max(a,b)

lis = [n-i for i in range(mi)]
lisr = [i+1 for i in range(mi)]


for i in range(1,mi):
    lis[i] = (lis[i-1]*lis[i])%di
    lisr[i] = pow_k(lisr[i],di-2)

for i in range(1,mi):
    lisr[i] = (lisr[i-1]*lisr[i])%di


hik =(lis[a-1]*lisr[a-1])%di
hik2 = (lis[b-1]*lisr[b-1])%di


ans = (ans - hik - hik2)%di

#print((lis[3-1]*lisr[3-1])%di)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque
from collections import defaultdict

def comb(n, r, mod):
    X, Y = 1, 1
    for i in range(r):
        X = X * (n - i)
        Y = Y * (r - i)
    return X * pow(Y, mod-2, mod)

def main():
    n,a,b = list(map(int,sys.stdin.readline().split()))
    mod = 10**9 + 7
    ans = pow(2, n, mod) - 1
    ans = (ans - comb(n, a, mod) - comb(n, b, mod)) % mod
    print(ans)

    return 0

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7

n,a,b=map(int,input().split())
res=pow(2,n,mod)
res=(res-1)%mod

up=1
down=1
for i in range(1,b+1):
	up*=(n-i+1)
	up%mod
	down*=i
	if i==a:
		upa=up
		downa=down

nca=upa%mod
nca*=pow(downa,mod-2,mod)
nca%=mod
ncb=(up%mod)
ncb*=pow(down,mod-2,mod)
ncb%=mod
print((res-nca-ncb)%mod)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7

n,a,b=map(int,input().split())
res=pow(2,n,mod)
res=(res-1)%mod

up=1
down=1
for i in range(1,b+1):
	up*=(n-i+1)
	down*=i
	if i==a:
		upa=up
		downa=down

nca=(upa%mod)*pow(downa,mod-2,mod)%mod
ncb=(up%mod)*pow(down,mod-2,mod)%mod
print((res-nca-ncb)%mod)

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

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

if answer == 0:
    print(0)
else:
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
N,A,B=map(int,input().split())
MOD=10**9+7

def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
  
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
	
print((pow(2,N,MOD)-1-comb(N,A)-comb(N,B))%MOD)

Submission status: Time Limit Exceeded

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


def comb(n, x):
    numerator = 1
    for i in range(n, n - x, -1):
        numerator = numerator * i % mod

    denominator = 1
    for j in range(x, 1, -1):
        denominator = denominator * j % mod

    d = denominator ** mod - 2 % mod

    return numerator * d

# #pow
# # def pow(x, n, mod=10e9+7):
# #     ans = 1
# #     while (n > 0):
# #         if bin(n & 1) == bin(1):
# #             ans *= x
# #         x *= x
# #         n = n >> 1
# #     return ans

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

print((2**n %mod - 1 - a - b) % mod)

Submission status: Time Limit Exceeded

Solution code:
import math

def comb(n, r):
    x = math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    return x % (pow(10,9)+7)

n,a,b = map(int, input().split())
ans = 0
for i in range(n):
    i = i+1
    if i==a or i==b:
        pass
    else:
        ans += comb(n,i)
        if ans > (pow(10,9)+7):
            ans = ans % (pow(10,9)+7)

print(ans)

Submission status: Time Limit Exceeded

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

import math

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

MOD = 10 ** 9 + 7

total = 2 ** n - 1
ans = total - combinations_count(n, a) - combinations_count(n, b)
print(ans % MOD)

Submission status: Time Limit Exceeded

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

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

for i in [a, b]:
  # nCa mod(10^9+7) = n*(n-1)*...*(n-a+1)/a*(a-1)*...*1 mod(10^9+7)
  # X := n*(n-1)*...*(n-a+1)
  # Y := a*(a-1)*...*1
  # nCa mod(10^9+7) = X/Y mod(10^9+7)
  # フェルマー小定理より
  # Y * Y^{(10^9+7)-2} mod(10^9+7) = 1
  # Y^{(10^9+7)-2} mod(10^9+7) = Y^(-1)
  # nCa mod(10^9+7) = X * Y^{(10^9+7)-2} mod(10^9+7) を求める。

  x = y = 1
  for j in range(i):
    x = x * (n - j) % mod
    y = y * (j + 1) % mod
  x *= pow(y, mod - 2, mod)
  x %= mod
  counter -= x

print(counter % mod)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
N, A, B = map(int, input().split())
MOD = 10 ** 9 + 7

def calc(n):
    ret = 1
    for i in range(n):
        ret *= (N - i) % MOD
    return ret * pow(factorial(n), MOD - 2, MOD) % MOD

print(max(0, (pow(2, N, MOD) - ((calc(A) + calc(B)) % MOD) - 1) % MOD))

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

def calculate_combination(n,k):
    x, y = 1, 1
    for i in range(k):
        x *= (n - i) % mod
        y *= (k - i) % mod
    return x * pow(y, mod-2, mod) % mod

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

ans = pow(2, n, mod) - 1 - calculate_combination(n,a) - calculate_combination(n,b)
while ans < 0:
    ans += mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a,b = map(int,input().split())
lim = 10**9+7
class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def C(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod
c = Combination(n)
print((pow(2,n,lim)-c.C(n,a)-c.C(n,b)-1) % lim)

Submission status: Time Limit Exceeded

Solution code:
class Combinatorics:
    def __init__(self, N, mod):
        '''
        Preprocess for calculating binomial coefficients nCr (0 <= r <= n, 0 <= n <= N)
        over the finite field Z/(mod)Z.
        Input:
            N (int): maximum n
            mod (int): a prime number. The order of the field Z/(mod)Z over which nCr is calculated.
        '''
        self.mod = mod
        self.fact = {i: None for i in range(N+1)}         # n!
        self.inverse = {i: None for i in range(1, N+1)}   # inverse of n in the field Z/(MOD)Z
        self.fact_inverse = {i: None for i in range(N+1)} # inverse of n! in the field Z/(MOD)Z
        
        # preprocess
        self.fact[0] = self.fact[1] = 1
        self.fact_inverse[0] = self.fact_inverse[1] = 1
        self.inverse[1] = 1
        for i in range(2, N+1):
            self.fact[i] = i * self.fact[i-1] % self.mod
            q, r = divmod(self.mod, i)
            self.inverse[i] = (- (q % self.mod) * self.inverse[r]) % self.mod
            self.fact_inverse[i] = self.inverse[i] * self.fact_inverse[i-1] % self.mod
    
    def perm(self, n, r):
        '''
        Calculate nPr = n! / (n-r)! % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return (self.fact[n] * self.fact_inverse[n-r]) % self.mod
    
    def binom(self, n, r):
        '''
        Calculate nCr = n! /(r! (n-r)!) % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return self.fact[n] * (self.fact_inverse[r] * self.fact_inverse[n-r] % self.mod) % self.mod
        
    def hom(self, n, r):
        '''
        Calculate nHr = {n+r-1}Cr % mod.
        Assign r objects to one of n classes.
        Arrangement of r circles and n-1 partitions:
            o o o | o o | | | o | | | o o | | o
        '''
        if n == 0 and r > 0:
            return 0
        if n >= 0 and r == 0:
            return 1
        return self.binom(n + r - 1, r)
n,a,b=map(int,input().split())
lim=10**9+7
c = Combinatorics(n,lim)
ans = (2**n-1-c.binom(n,a)-c.binom(n,b))
print(ans%lim)

Submission status: Time Limit Exceeded

Solution code:
n,a,b=list(map(int,input().split()))
from math import factorial as f
ans=1
ans2=1
for i in range(n-a):
    ans*=(n-i)
for i in range(n-b):
    ans2*=(n-i)
print(int(2**n-ans/f(n-a)-ans2/f(n-b)-1))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,a,b=list(map(int,input().split()))
from math import factorial as f
A=[i for i in range(1,n+1) if i!=a and i!=b]
ans=0
for i in A:
    ans+=f(n)/(f(n-i)*f(i))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import math

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


def choose(n, a):
    x = 1
    y = 1
    for i in range(a):
        x *= n - i
        y *= i + 1
    return x // y


def pow2(num):
    c = 2
    d = 1
    dic = {d: c}

    for _ in range(20):
        c **= 2
        d *= 2
        dic[d] = c

    ret = 0
    while d != 0:
        if num >= d:
            num -= d
            if ret == 0:
                ret = dic[d]
            else:
                ret *= dic[d]
        else:
            d //= 2
    return ret


print((pow2(n) - 1 - choose(n, a) - choose(n, b)) % 1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

p=10**9+7
ans=0
for i in range(1,n+1):
    if i==1:
        now=n%p
    else:
        now=now*(n+1-i)*pow(i,p-2,p)%p
    if i==a or i==b:
        continue
    else:
        ans+=now
        ans%=p



print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

t = (10 ** 9) + 7
n = n % t
A = (math.factorial(n) / (math.factorial(a) * math.factorial(n - a))) % t
B = (math.factorial(n) / (math.factorial(b) * math.factorial(n - b))) % t
ans = ((2 ** n) - 1 - A - B) % t
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,a,b=map(int,input().split())
DP=n
if a==1:
  ans_a=n
ans=DP
for i in range(1,n):
  DP=DP*(n-i)/(1+i)
  ans+=DP
  if i==(a-1):
    ans_a=DP
  if i==(b-1):
    ans_b=DP
ans=ans-ans_a-ans_b
print(int(ans%(10**9+7)))

Submission status: Time Limit Exceeded

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

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

so=10**9+7

large=(pow(2,n,so)-1) % so 

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

ajogai = kumiawase(n,a) % so
bjogai = kumiawase(n,b) % so
print((large  - ajogai - bjogai + 2*so) % so)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

class ModInt:
    def __init__(self, n=0, mod=mod):
        self.mod = mod
        self.n = n % self.mod
    
    def value(self):
        return self.n
    
    def __add__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n + rhs.n, self.mod)
        return self.__class__(self.n + rhs, self.mod)
    
    __radd__ = __add__
    
    def __sub__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n - rhs.n, self.mod)
        return self.__class__(self.n - rhs, self.mod)
    
    def __rsub__(self, lhs):
        if isinstance(lhs, ModInt):
            return self.__class__(lhs.n - self.n, self.mod)
        return self.__class__(lhs - self.n, self.mod)

    def __mul__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n * rhs.n, self.mod)
        return self.__class__(self.n * rhs, self.mod)
    
    __rmul__ = __mul__

    def __floordiv__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n // rhs.n, self.mod)
        return self.__class__(self.n // rhs, self.mod)
    
    def __rfloordiv__(self, lhs):
        if isinstance(lhs, ModInt):
            return self.__class__(lhs.n // self.n, self.mod)
        return self.__class__(lhs // self.n, self.mod)

    def __iadd__(self, rhs):
        if isinstance(rhs, ModInt):
            self.n += rhs.n
        else:
            self.n += rhs
        if self.n >= self.mod:
            self.n -= self.mod
        
        return self
    
    def __isub__(self, rhs):
        rhs_n = rhs.n if isinstance(rhs, ModInt) else rhs
        if self.n < rhs_n:
            self.n += self.mod
        self.n -= rhs_n
        return self
    
    def __imul__(self, rhs):
        rhs_n = rhs.n if isinstance(rhs, ModInt) else rhs
        self.n = self.n * rhs_n % self.mod
        return self
    
    def __ifloordiv__(self, rhs):
        rhs_n = rhs.n if isinstance(rhs, ModInt) else rhs
        exp = self.mod - 2
        while exp:
            if exp % 2:
                self *= rhs_n
            
            rhs_n *= rhs_n
            rhs_n %= self.mod
            exp //= 2
        
        return self
    
    def __pow__(self, exp):
        exp_n = exp.n if isinstance(exp, ModInt) else exp
        if exp_n == 0:
            return self.__class__(1, self.mod)
        if exp_n % 2 == 0:
            t = self.__pow__(exp_n // 2)
            return t * t
        return self * self.__pow__(exp_n - 1)
    
    def __str__(self):
        return str(self.n)

def comb(n, k):
    if n == k or k == 0:
        return 1
    if n < k:
        return 0
    
    res = ModInt(1)
    for i in range(k):
        res *= (n - i)
        res *= ModInt(i + 1) ** (mod - 2)
    
    return res

n, a, b = na()

ans = ModInt(2) ** n - 1
ans -= comb(n, a)
ans -= comb(n, b)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

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

tmp1 = pow(2, N, MOD) - 1 #1本以上の選び方

#計算量 log(m)くらい
def modinv(a, m): #mod. m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u


def combination(n, r): #nCrを求める
    if n - r > r:
        r = n - r
    tmp1 = 1
    for i in range(n - r + 1, n + 1):
        tmp1 *= i
        tmp1 %= MOD
    
    tmp2 = 1
    for i in range(1, r + 1):
        tmp2 *= i
        tmp2 %= MOD
    return tmp1 * modinv(tmp2, MOD)

tmp2 = combination(N, A)
tmp3 = combination(N, B)

print ((tmp1 - tmp2 - tmp3) % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

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

tmp1 = pow(2, N, MOD) - 1 #1本以上の選び方

def combination(n, r): #nCrを求める
    if n - r > r:
        r = n - r
    tmp1 = 1
    for i in range(n - r + 1, n + 1):
        tmp1 *= i
        tmp1 %= MOD
    
    tmp2 = 1
    for i in range(1, r + 1):
        tmp2 *= i
        tmp2 %= MOD
    return tmp1 * pow(tmp2, MOD - 2, MOD)

tmp2 = combination(N, A)
tmp3 = combination(N, B)

print ((tmp1 - tmp2 - tmp3) % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

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

tmp1 = pow(2, N, MOD) - 1 #1本以上の選び方


def combination(n, r): #nCrを求める
    if n - r > r:
        r = n - r
    tmp = 1
    for i in range(n - r + 1, n + 1):
        tmp *= i
        tmp %= MOD
    for i in range(1, r + 1):
        tmp *= pow(i, MOD - 2, MOD)
        tmp %= MOD
    return tmp

tmp2 = combination(N, A)
tmp3 = combination(N, B)

print ((tmp1 - tmp2 - tmp3) % MOD)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, a, b = map(int, input().split())
    mod = 10**9+7
    p = []
    pa = p.append
    for i in range(200001):
        pa(pow(i, mod-2, mod))
    nn, aa, bb = n, a, b
    ans1 = 1
    for a in range(aa, 0, -1):
        ans1 = ans1*n*p[a] % mod
        n -= 1
    ans2 = 1
    n = nn
    for b in range(bb, 0, -1):
        ans2 = ans2*n*p[b] % mod
        n -= 1
    print((pow(2, nn)-ans1-ans2-1) % mod)


main()

Submission status: Time Limit Exceeded

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

    nn = n
    ans1 = 1
    while a > 0:
        ans1 = (ans1 * n * pow(a, mod-2, mod)) % mod
        n -= 1
        a -= 1

    ans2 = 1
    n = nn
    while b > 0:
        ans2 = (ans2 * n * pow(b, mod-2, mod)) % mod
        n -= 1
        b -= 1

    print((pow(2, nn)-ans1-ans2-1) % mod)


main()

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

total = 2**n -1

total-=comb(n,a,mod)
total-=comb(n,b,mod)


print(total%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())
mod = 10**9 +7

total = 2**n -1

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


print(total%mod)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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


def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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

print(total)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

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

    ans += factorial(n) // (factorial(n - i) * factorial(i))

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
MOD = 10**9 + 7
def comb(n, k, p):
    if n<0 or k<0 or n<k:
        return 0
    if n==0 or k==0:
        return 1
    a, b, c = 1, 1, 1
    for i in range(1, n+1):
        a = (a*i)%p
    for i in range(1, k+1):
        b = (b*i)%p
    for i in range(1, n-k+1):
        c = (c*i)%p
    return a*pow(b, p-2, p)*pow(c, p-2, p)%p
n,a,b = map(int,input().split())
A = comb(n,a,MOD)
B = comb(n,b,MOD)
C = pow(2,n,MOD)
ans = C -A-B-1
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
# ans = 全通り - nCa - nCb
#     = 2^n - 1 - nCa - nCb

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

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def comb_num_mod(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 = map(int, input().split())

mod = (10**9) + 7

num_all = pow(2, n) - 1

nca = comb_num_mod(n, a, mod=mod)
ncb = comb_num_mod(n, b, mod=mod)

print(num_all - nca - ncb)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def rev(x):
    re = 10**9+5
    num = 1
    ix = x
    while re > 0:
        if re%2 == 1:
            num = (num*ix)%mod
        re //= 2
        ix = (ix**2)%mod
    return(num)

kaijo = [0 for i in range(n+1)]
kaijo[0] = 1
for i in range(1,n+1):
    kaijo[i] = (kaijo[i-1]*i)%mod

re = n
ans = 1
i2 = 2
while re > 0:
    if re%2 == 1:
        ans = (ans*i2)%mod
    re //= 2
    i2 = (i2**2)%mod

ans -= 1
ans = (ans - (((kaijo[n]*rev(kaijo[a]))%mod)*rev(kaijo[n-a]))%mod)%mod
ans = (ans - (((kaijo[n]*rev(kaijo[b]))%mod)*rev(kaijo[n-b]))%mod)%mod
print(ans)

Submission status: Time Limit Exceeded

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

# a
x = 1
for i in range(n - a + 1, n + 1):
    x *= i
y = 1
for i in range(1, a + 1):
    y *= i

a_ans = x*pow(y, mod-2, mod)

x = 1
for i in range(n - b + 1, n + 1):
    x *= i
y = 1
for i in range(1, b + 1):
    y *= i
b_ans = x*pow(y, mod-2, mod)
print((ans - a_ans - b_ans) % mod)

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

Submission status: Time Limit Exceeded

Solution code:
n,a,b = map(int,input().split())
def kai(g):
    p = 1 
    for i in range(1,g+1):
        p = p*i
    return p
def comb(n,k):
    return kai(n)/(kai(k)*kai(n-k))
print(int(2**n-1-comb(n,a)-comb(n,b)))

Submission status: Time Limit Exceeded

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

ans = pow(2, n, mod)

def C(n, k):
    x, y = 1, 1
    for i in range(k):
        x *= n - i
        y *= i+1

    return (x * pow(y, mod-2, mod)) % mod

print((ans - C(n, a) - C(n, b) - 1) % mod)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

def cmb(n,r):
  return factorial(n) /factorial(r) / factorial(n-r)
  

# Sigma_r nCr = nC1 + nC2 + nC3 + ... + nCn = 2**n
su = 2**n - 1
su -= cmb(n,a)+cmb(n,b)
su = su % (10**9 + 7)
print(int(su))

Submission status: Time Limit Exceeded

Solution code:
# k本の花束の作り方は正直わからない
# 2**n-1通りのはなの選び方があるのは間違いない
# その中からごうけいがa,bになるものは除く
# nCa+nCb何じゃない？
# 組み合わせ数を計算するだけならめんどくさいライブラリを使わなくてもmathのfactorialで階乗を計算すれば良い
from functools import lru_cache
import math
n,a,b = map(int,input().split())


# これはfactorialの計算がやばいことになるので(10**9+7)で割りながらやっていこう
# ホントはここの10^9のループが重いみたいだなぁ
# なんか２分累乗法を使わないといけないらしい．．．実はpythonではmathのpowに標準でついています！
Big = 10**9 + 7
@lru_cache()
def cal_pow(num,w):
    if num==1:
        return w
    elif num==0:
        return 1
    else:
        half = num // 2
        rest = num % 2
        res = cal_pow(half,w) **2 * cal_pow(rest,w)
        res %= Big
        return res
all = cal_pow(n,2)-1

a_comb = 1
for i in range(a):
    # 逆元
    inv_a = cal_pow(Big-2,a-i)
    a_comb *= (n-i)*inv_a
    a_comb %= Big
b_comb = 1
for i in range(b):
    # 逆元
    inv_b = cal_pow(Big-2,b-i)
    b_comb *= (n-i)*inv_b
    b_comb %= Big
res = (all - a_comb - b_comb)
while res<0:
    res += Big
print(res)

# また出たぞ！！逆元だぁ...
# 1/x の mod p(素数) は x^(p-2)になるらしい．(フェルマーの小定理より...)
# mod(1/x) = mod(x^(p-2))