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 math
n, a, b = map(int, input().split())
def conbination(n, r):
    return math.factorial(n) / (math.factorial(r)*math.factorial(n-r))
Conb = 2 ** n - 1
Conb_a = conbination(n, a)
Conb_b = conbination(n, b)
Conb -= Conb_a + Conb_b
print(int(Conb%(10**9+7)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()


def inv_mod(a, N):
    """
    Fermatの小定理より(Nが素数のときしか使えない)
    aの逆元 ax = 1 (mod N)を満たすx = a^(N-2) mod Nを返す。
    O(log N)
    """

    def bpm(x, y, N):
        """
         Bisection power method : 二分累乗法
         O(log y)でx^(y) mod N を求める。
        """
        ans = 1
        x %= MOD
        digit = int((math.log(y, 2) // 1 + 1))  # yの２進数表示の桁数
        for i in range(digit):
            if (y >> i) & 1 == 1:
                ans *= x
                ans %= MOD
            x **= 2
            x %= MOD
        return ans

    return bpm(a, N - 2, N)


def bpm(x, y, N):
    """
     Bisection power method : 二分累乗法
     O(log y)でx^(y) mod N を求める。
    """
    ans = 1
    x %= MOD
    digit = int((math.log(y, 2) // 1 + 1))  # yの２進数表示の桁数
    for i in range(digit):
        if (y >> i) & 1 == 1:
            ans *= x
            ans %= MOD
        x **= 2
        x %= MOD
    return ans


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

nCa = 1
nCb = 1

inv_list = []

for i in range(max(a, b)):
    inv_list.append(inv_mod(i + 1, MOD))

for i in range(a):
    nCa *= inv_list[i]
    nCa %= MOD
    nCa *= n - i
    nCa %= MOD

for i in range(b):
    nCb *= inv_list[i]
    nCb %= MOD
    nCb *= n - i
    nCb %= MOD

print((bpm(2, n, MOD) - 1 - nCa - nCb) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()


def inv_mod(a, N):
    """
    ユークリッドの互除法より
    aの逆元 ax = 1 (mod N)を満たすxを返す。
    O(log a)
    """

    def extgcd(a, b):
        """
        Extended Great Common Divisor
        ax + by = gcd(a, b) = dを満たすx, y, dを返す。
        """
        d = fractions.gcd(a, b)
        if b == 0:
            return 1, 0, a
        else:
            q, r = divmod(a, b)
            x, y, d = extgcd(b, r)
            s, t = y, x - q * y
            return s, t, d

    return extgcd(a, N)[0]


def bpm(x, y, N):
    """
     Bisection power method : 二分累乗法
     O(log y)でx^(y) mod N を求める。
    """
    ans = 1
    x %= MOD
    digit = int((math.log2(y) // 1 + 1))  # yの２進数表示の桁数
    for i in range(digit):
        if (y >> i) & 1 == 1:
            ans *= x
            ans %= MOD
        x **= 2
        x %= MOD
    return ans


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

nCa = 1
nCb = 1

inv_list = []

for i in range(max(a, b)):
    inv_list.append(inv_mod(i + 1, MOD))

for i in range(a):
    nCa *= inv_list[i]
    nCa %= MOD
    nCa *= n - i
    nCa %= MOD

for i in range(b):
    nCb *= inv_list[i]
    nCb %= MOD
    nCb *= n - i
    nCb %= MOD

print((bpm(2, n, MOD) - 1 - nCa - nCb) % MOD)

Submission status: Time Limit Exceeded

Solution code:
# D - Bouquet
n, a, b = map(int, input().split())
from operator import mul
from functools import reduce
MOD = 10**9 + 7

def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac

fac, ifac = make_tables(MOD, n)
tmp2 = 1
for l in range(n):
    tmp2 *= 2
    tmp2 = tmp2 % (MOD)

ans = ((tmp2 -1) - cmb(n, a, MOD, fac, ifac)- cmb(n, b, MOD, fac, ifac))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D - Bouquet
n, a, b = map(int, input().split())
from operator import mul
from functools import reduce
MOD = 10**9 + 7

def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac

fac, ifac = make_tables(MOD, n)

ans = ((2 ** n -1)%(10**9+7) - cmb(n, a, MOD, fac, ifac)- cmb(n, b, MOD, fac, ifac))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D - Bouquet
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


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

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

    return K * x

# nCkの導出
def comb(n,k):
    nCk = 1
    # X
    for i in range(n-k+1, n+1):
        nCk *= i
        # nCk %= mod

    # Y
    for i in range(1,k+1):
        nCk *= pow(i,mod-2,mod)
        nCk %= mod
    return nCk

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

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

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

print(ans%mod)
# print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

    return K * x

# nCkの導出
def comb(n,k):
    nCk = 1
    # X
    for i in range(n-k+1, n+1):
        nCk *= i
        # nCk %= mod

    # Y
    for i in range(1,k+1):
        nCk *= pow(i,mod-2,mod)
        nCk %= mod
    return nCk

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

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

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

print(ans)
# print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
n, a, b = [int(i) for i in input().split()]
mod = 10**9 + 7
ans = 2**n - (factorial(n)//factorial(a)//factorial(n-a)) - (factorial(n)//factorial(b)//factorial(n-b)) -1
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def choose(n, r, M):
    x = 1
    y = 1

    for i in range(r):
        x *= (n - i) % M
        y *= (i + 1) % M
    res = x * pow(y, M-2, M) % M
    return res

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

print((pow(2, n, M) - 1 - choose(n, a, M) - choose(n, b, M)) % M)

Submission status: Time Limit Exceeded

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

sum=0
for i in range(1,n+1):
    if i==a:
        pass
    elif i==b:
        pass
    else:
        sum+=cmb(n,i)

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
def modpow(x, n, mod):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return modpow((x**2) % mod, n // 2, mod)
    else:
        return x * modpow(x, n - 1, mod) % mod
def modcomb(n, r, mod):
    "nCr = X/Yとおく"
    r = min(r, n - r)
    ue, sita = 1, 1
    for i in range(1, r + 1):
        ue *= (n + 1 - i) % mod
        sita *= i % mod
    # return ue * modpow(sita, mod-2, mod)
    return ue * pow(sita, mod-2, mod)

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

ans = pow(2, N, mod) - 1
ans -= modcomb(N, A, mod)
# ans -= cmb(N, A, mod) % mod
ans %= mod
ans -= modcomb(N, B, mod)
# ans -= cmb(N, B, mod) % mod
ans %= mod
print(ans % mod)

Submission status: Time Limit Exceeded

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

def ore_comb(n,r,mod):
    '''
    return nCr
    O(min{n-r, r})
    '''
    bunsi=1 
    bunbo=1 
    for i in range(n,n-r,-1):#分子
      bunsi = bunsi*i%mod
    for i in range(r):#分母
      bunbo = bunbo*(i+1)%mod

    ans = (bunsi*pow(bunbo,mod-2,mod))%mod
    return ans

ans = ( (pow(2,n)-1)  - ore_comb(n,a,mod) -ore_comb(n,b,mod) )%mod
if ans != 0:
  print(ans)
else:
  print(0)

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7
m = 2*10**5
mm = 2** m

def cmb(n,r,mod):        
    ret=1
    div = min(r,n-r)
    for i in range(div):        
        ret=ret*(n-i)*pow(div-i,mod-2,mod)%mod
        
    return ret % mod

ans = 1
for _ in range(n // m):
  ans = (ans * mm) % MOD

ans = (ans * 2**(n % m)) % MOD  
    
ans = (ans - 1) % MOD

ans = (ans - cmb(n,a,MOD))%MOD
ans = (ans - cmb(n,b,MOD))%MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def modpow(a,n,mod=10**9+7):
    res=1
    while n>0:
        if n&1:
            res=res*a%mod
        a=a*a%mod
        n>>=1
    return res%mod

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

n,a,b=[int(i) for i in input().split()]
ans=modpow(2,n)-1
ans-=modcmb(n,a)
ans%=10**9+7
ans-=modcmb(n,b)
ans%=10**9+7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from math import factorial
def modpow(x, n, mod):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return modpow((x**2) % mod, n // 2, mod)
    else:
        return x * modpow(x, n - 1, mod) % mod
def modcomb(n, r, mod):
    "nCr = X/Yとおく"
    X = factorial(n) % mod
    Y = factorial(n-r) % mod * factorial(r) % mod 
    Y_over = modpow(Y, mod - 2, mod)
    return (X * Y) % mod

N, A, B = map(int, input().split())
mod = 10 ** 9 + 7
def cmb(n, r, mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod
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)
ans = modpow(2, N, mod) - 1
# ans -= modcomb(N, A, mod)
# ans -= modcomb(N, B, mod)
ans %= mod
ans -= cmb(N, A, mod) % mod
ans %= mod
ans -= cmb(N, B, mod) % mod
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

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
#
#     return result

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

# from scipy.special import comb
# # a = comb(n, r)
# a = comb(n, r, exact=True)

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

ans = z - cmb(n, a) - cmb(n, b)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def cmb(r):
    x = 1
    y = 1
    for i in range(1,r+1):
        x *= (n-i+1) % mod
        y *= i % mod
    return x * pow(y, mod-2, mod) % mod    

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

print(int(all - aa - bb))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
p = 10 ** 9 + 7
N = 10 ** 7  # 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=((pow(2,N)-1)%(10**9+7)-cmb(n,a,p)-cmb(n,b,p))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
s = 1
for i in range(n):
  s *= 2
  s = s % (10 ** 9 + 7)

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
A = cmb(n, a) % (10 ** 9 + 7)
B = cmb(n, b) % (10 ** 9 + 7)
ans = (s - 1 - (A + B)) % (10 ** 9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

MOD = 10**9+7
def modcmb(n, r, mod):
    x = 1
    y = n
    for i in range(2,r+1):
        x *= i
        x %= mod
        y *= n-i+1
        y %= mod
    return y * pow(x, mod-2, mod) % mod

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

DIV = 10**9+7

all_n = '1'* n
nishin = int(all_n, 2)

_a = modcmb(n, a, MOD)
_b = modcmb(n, b, MOD)

print((nishin - (_a + _b))%DIV)

Submission status: Time Limit Exceeded

Solution code:
n,a,b = [int(i) for i in input().split()]
mod = 10**9+7

def mpow(a,n):
  if n == 1:
    return a
  x = mpow(a,n//2)
  ans = x*x%mod
  if n%2==1:
    ans *= a
  return ans

def comb(n,a,b):
  if a < b:
    s, l = a, b
  else:
    s, l = b, a
  rs = 1
  for i in range(s):
    rs = rs*(n-i)%mod
  rl = rs
  for i in range(s,l):
    rl = rl*(n-i)%mod
  L = 1
  for i in range(1,s+1):
    L = L*mpow(i,mod-2)%mod
  rs = rs*L%mod
  rl = rl*L%mod
  for i in range(s+1,l+1):
    rl = rl*mpow(i,mod-2)%mod
  if a < b:
    nCa, nCb = rs, rl
  else:
    nCa, nCb = rl, rs
  return nCa, nCb
nCa,nCb = comb(n,a,b)
print((mpow(2,n)-1-nCa-nCb)%mod)
# print(nCa,nCb)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

def nCrMOD(n,r,m):
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    for i in range( 2, n + 1 ):
        g1.append( ( g1[-1] * i ) % m )
        inverse.append( ( -inverse[m % i] * (m//i) ) % m )
        g2.append( (g2[-1] * inverse[-1]) % m )
    return cmb(n,r,m,g1,g2)


m=10**9+7

ans = 2**(n%(m-1))%m -1 - nCrMOD(n,a,m) -nCrMOD(n,b,m)
print(ans%m)

Submission status: Time Limit Exceeded

Solution code:
n,a,b = [int(i) for i in input().split()]
mod = 10**9+7

def mpow(a,n):
  if n == 0:
    return 1
  x = mpow(a,n//2)
  ans = x*x%mod
  if n%2==1:
    ans *= a
  return ans

def comb(n,a,b):
  if a < b:
    s, l = a, b
  else:
    s, l = b, a
  r1s = 1
  for i in range(s):
    r1s = r1s*(n-i)%mod
  r1l = r1s
  for i in range(s,l):
    r1l = r1l*(n-i)%mod
  r2s = 1
  for i in range(1,s+1):
    r2s = r2s*mpow(i,mod-2)%mod
  r2l = r2s
  for i in range(s+1,l+1):
    r2l = r2l*mpow(i,mod-2)%mod
  nCs = r1s*r2s
  nCl = r1l*r2l
  if a < b:
    nCa, nCb = nCs, nCl
  else:
    nCa, nCb = nCl, nCs
  return nCa, nCb
nCa,nCb = comb(n,a,b)
print((mpow(2,n)-1-nCa-nCb)%mod)
# print(nCa)

Submission status: Time Limit Exceeded

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

n, a, b = [int(n) for n in input().split()]
m = 0
d = 10**9+7
c = 2**n
m += combi(n, a)
m += combi(n, b)
m += 1
print((c-m)%d)

Submission status: Time Limit Exceeded

Solution code:
n,a,b = [int(i) for i in input().split()]
mod = 10**9+7

def mpow(a,n):
  if n == 0:
    return 1
  x = mpow(a,n//2)
  ans = x*x%mod
  if n%2==1:
    ans *= a
  return ans
  
def comb(n,k):
  ans = 1
  for i in range(k):
    ans = ans*(n-i)%mod
  for i in range(1,k+1):
    ans = ans*mpow(i,mod-2)%mod
  return ans

print((mpow(2,n)-1-comb(n,a)-comb(n,b))%mod)
# print(comb(n,a))

Submission status: Time Limit Exceeded

Solution code:
n,a,b = [int(i) for i in input().split()]
mod = 10**9+7

def mpow(a,n):
  if n == 0:
    return 1
  ans = mpow(a,n//2)**2%mod
  if n%2==1:
    ans *= a
  return ans
  
def comb(n,k):
  ans = 1
  for i in range(k):
    ans = ans*(n-i)%mod
  for i in range(1,k+1):
    ans = ans*mpow(i,mod-2)%mod
  return ans

print((mpow(2,n)-1-comb(n,a)-comb(n,b))%mod)
# print(comb(4,3))

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
n,a,b=map(int,input().split())
start = (2 ** n - 1) % (10 ** 9 + 7)
ac = (cmb(n,a)) % (10 ** 9 + 7)
bc = (cmb(n,b)) % (10 ** 9 + 7)
ans = (start - ac -bc) % (10 ** 9 + 7)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def choose(n,r):
    res = 1
    fac = 1
    for i in range(r):
        res *= n-i
        res %= MOD
        fac *= i+1
        fac %= MOD
    return res*pow(fac,MOD-2,MOD)%MOD        

n,a,b = list(map(int,input().split()))
t=0
ans = pow(2,n)-1
MOD = 10**9+7

ans -= choose(n,a)
ans -= choose(n,b)

ans = ans % MOD
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
n, a, b = list(map(int, input().split()))
MAX = 510000
MOD = 1000000007

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]
com = [0 for i in range(MAX)]

def cominit() :
  fac[0] = fac[1] = 1
  finv[0] = finv[1] = 1
  inv[1] = 1
  com[1] = n
  for i in range(2, MAX) :
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * int(MOD / i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD
    com[i] = com[i-1] * (n-(i-1)) * inv[i] % MOD
    
  return fac, finv, inv, com
 
"""
def combination(n, r, inv) :
  ans = 1
  if(n < r) : 
    return 0
  if((n < 0) or (r < 0)) :
    return 0
  for i in range(0, r) :
    return (fac[n] * (finv[r] * finv[n-r] % MOD) % MOD) 
 """

def two_n_mod(n) :
  ans = 1
  while(n > 32) :
    ans = ans * 2**32 % MOD
    n -= 32
  return ans * 2**n % MOD

temp = cominit()
##print(two_n_mod(1000000000))
print((two_n_mod(n) - 1 - com[a] - com[b]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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())
mo=10**9+7

fn=2*10**5
fac=[0]*fn
fac[1]=n
for i in range(2,fn):
    fac[i]=fac[i-1]*(n-i+1)*power(i, mo-2, mo) % mo

print((power(2, n, mo)-1-fac[a]-fac[b])%mo)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
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
        
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
import math
n,a,b = map(int, input().split())
total = pow(2,n,mod)-1
a2,b2 = 1,1
for i in range(n-a+1, n+1):
    a2 *=i
a2 = a2*pow(math.factorial(a), mod-2, mod)
for i in range(n-b+1, n+1):
    b2 *=i
b2 = b2*pow(math.factorial(b), mod-2, mod)
print((total-a2-b2)%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
import math
n,a,b = map(int, input().split())
total = (pow(2,n)-1)%mod
a2,b2 = 1,1
for i in range(n-a+1, n+1):
    a2 *=i
a2 = a2*pow(math.factorial(a), mod-2, mod)
for i in range(n-b+1, n+1):
    b2 *=i
b2 = b2*pow(math.factorial(b), mod-2, mod)
print((total-a2-b2)%mod)

Submission status: Time Limit Exceeded

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

print((total - c(n, a) - c(n, b))%mod)

Submission status: Time Limit Exceeded

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

def modComb(n,r,mod):
    tmp = 1
    for i in range(1,r+1):
        tmp *= (n-i+1) % mod
        tmp *= pow(i,mod-2,mod)
    
    return tmp % mod


mod = 10**9+7
ans = pow(2,n,mod) - 1
ans %= mod

print(ans-modComb(n,a,mod)-modComb(n,b,mod) % mod)

Submission status: Time Limit Exceeded

Solution code:
M = 1000000007

def nCr(n, k): 
    C = [[0 for x in range(k+1)] for x in range(n+1)] 
  
    for i in range(n+1): 
        for j in range(min(i, k)+1): 
            if j == 0 or j == i: 
                C[i][j] = 1
  
            else: 
                C[i][j] = C[i-1][j-1] + C[i-1][j] 
  
    return C[n][k] 

x, y , z = map(int,input().split()) 
ans = pow(2,x)-1
ans = ans - nCr(x,y)
ans = ans - nCr(x,z)
ans = ans%M

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
# refer to https://qiita.com/k_karen/items/653ba7025a92f5ac1363
 
# ONE = '1'.freeze
MOD = (10**9) + 7
 
# def inv(x)
#   res = 1 # 最終的に x^(MOD-2) になる変数です
#   beki = x # x^2^n を格納する変数です
#   # MOD-2の２進数展開を下位のbitから見ていきます。
#   (MOD - 2).to_s(2).reverse.chars do |digest|
#     # bitが立っている <=> digest == ONE 
#     # なら resにbekiを掛けます。
#     # ここで、掛け算は計算の都度MODを取れます
#     res = (beki * res) % MOD if digest == ONE
#     # 次のループに備えて、自乗を計算します。
#     # 計算の都度MODを取れます(とても大事なので二回言います)
#     beki = (beki * beki) % MOD
#   end
#   res
# end
 
# def fact(s, e)
#   (s..e).reduce(1) { |r, i| (r * i) % MOD }
# end
 
# def nCk(n, k)
#   k = n - k if k > n - k
#   (fact(k + 1, n) * inv(fact(1, n - k) % MOD)) % MOD
# end
 
def cmb(n, r, p):
    if r > n - r:
        r = n - r
    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)
 
def f(t,k,mod):
    res = 1
    for i in range(k):
        res = res * t % mod
        t -= 1
    return res

def nCk(n,r):
    if r > n - r:
        r = n - r
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    res = 1
    for i in range(r):
      res *= n - i
      res /= i + 1
    return int(res)
    
def fact(n,k,mod):
    res = 1
    for i in range(k):
        res = res * (n-i) % mod
    return res

# A_inv = pow(A,P-2,P)
 
mod = 10 ** 9 + 7
# n = gets.to_i
# s = gets.chomp
# n,a,b = gets.split.map(&:to_i)
n, a, b = map(int, input().split())
cnt_a = cnt_b = 0
 
ans = 1
for i in range(n):
    ans = ans * 2 % mod
ans -= 1
# p [n,ans]
# print(ans)
# print(f(n,a,mod))
# print(f(n,b,mod))
# print(f(4,1,mod))
# p nCk(a,n)
# p fact(b,n)
ans = (ans - fact(n,a,mod)*pow(fact(a,a,mod),mod-2,mod)) % mod
ans = (ans - fact(n,b,mod)*pow(fact(b,b,mod),mod-2,mod)) % mod
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int,input().split())
t = pow(2, n, 10**9 + 7) - 1
x = 1
y = 1
for i in range(a):
    x *= (n - i)
    y *= (a - i)
f = (x // y) % (10**9 + 7)
x = 1
y = 1
for i in range(b):
    x *= (n - i)
    y *= (b - i)
s = (x // y) % (10**9 + 7)

print((t - f - s + (10**9 + 7)) % (10**9 + 7))

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

def comb(n, r):
    ret = 1
    for i in range(r):
        ret *= n - i
    for i in range(r):
        ret *= pow(i+1, MOD-2, MOD)

    return ret % MOD
    

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

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

def comb(n, r):
    fn = 1
    finv_r = 1
    for i in range(r):
        fn *= n - i
        finv_r *= pow(i+1, MOD-2, MOD)

    return fn * finv_r % MOD
    

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

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

def comb(n, r):
    fn = 1
    fr = 1
    for i in range(1, r+1):
        fn *= n - (i-1)
        fr *= i % MOD
    finv_r = pow(fr, MOD-2, MOD)

    return fn * finv_r % MOD
    

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

Submission status: Time Limit Exceeded

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

count=0
mod=1000000007

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

count+=pow(2,n,mod)
#print(count)
count-=1
count-=C(n,a)
#print(count)
count-=C(n,b)

print(max(0,(count)%mod))

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

def comb(n, r):
    fn = 1
    fr = 1
    for i in range(1, r+1):
        fn *= n - (i-1)
        fr *= i
    finv_r = pow(fr, MOD-2, MOD)

    return fn * finv_r % MOD
    

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

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7
com = [1]
table = [1]
inv_table = [1]
sums = 0

for i in range(1, n+1):
    table.append((table[i-1]*i) % mod)
    inv_table.append(pow(table[i], mod-2, mod))

for i in range(1,n+1):
    com.append((table[n] * inv_table[i] * inv_table[n-i]) % mod)

for i in range(1,n+1):
    if i == a or i == b:continue
    sums +=com[i]

print(sums % mod)

Submission status: Time Limit Exceeded

Solution code:


n, a, b = map(int, input().split())
u = 0
def g(r, o):
    c = 1
    for y in range(r-o+1, r + 1):
        c *= y
    return int(c)
    
for x in range(1, n+1):
    if x == a or x == b:
        continue
    u += g(n, x) // g(x, x)
print(int(u))

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
mod=10**9+7
def comb(n,k):
    temp=1
    k=min(k,n-k)
    for i in range(k):
        temp*=(n-i)
        temp//=(i+1)

    return temp%mod
#二分累乗法を勉強する
ans=pow(2,n,mod)-1-(comb(n,a)+comb(n,b))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a,b = map(int, input().split())        
X,Y = 1,1
for i in range(b):
    X *= n-i
    X %= 10**9+7
    Y *= i+1
    Y %= 10**9+7

    if a-1 == i:
        Xa,Ya = X,Y

comb_a = (Xa*pow(Ya,10**9+5,10**9+7))%(10**9+7)
comb_b = (X*pow(Y,10**9+5,10**9+7))%(10**9+7)

result = pow(2,n)-1-comb_a-comb_b
print(result if result>=0 else result+10**9+7)

Submission status: Time Limit Exceeded

Solution code:
n,a,b = map(int, input().split())        
X,Y = 1,1
for i in range(b):
    X *= n-i
    X %= 10**9+7
    Y *= i+1
    Y %= 10**9+7

    if a-1 == i:
        Xa,Ya = X,Y

comb_a = (Xa*pow(Ya,10**9+5))%(10**9+7)
comb_b = (X*pow(Y,10**9+5))%(10**9+7)

result = pow(2,n)-1-comb_a-comb_b
print(result if result>=0 else result+10**9+7)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def calc(y, n, m):
    if n == 0:
        return 1
    elif n%2 == 0:
        l = calc(y, n/2, m)
        return (l**2)%m
    else:
        return (calc(y, n-1, m)*y)%m
    
def calc2(a, m):
    x = 1
    y = 1
    for i in range(a):
        x = (x*(n-i))%m
        y = (y*(i+1))%m
    return (x*calc(y, m-2, m))%m

print(2**n-1-calc2(a,10**2+7)-calc2(b,10**2+7))

Submission status: Time Limit Exceeded

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

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

combi_sum = 0

for i in range(1,n+1):
	if i == a or i == b:
		combi_sum += 0
	else:
		combi_sum += cmb(n,i)
	#print(combi_sum)

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

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
total = pow(2, n, mod) - 1
product = 1
div = 1
for i in range(1, max(a, b) + 1):
    product *= (n - i + 1)
    div *= i
    if i == a or i == b:
        total -= product // div
print(total % mod)