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:
def modpow(x, n, m):
    res = 1
    while n > 0:
        if n % 2 == 1:
            res = (res * x) % m
        x = (x * x) % m
        n >>= 1
    return res

def combination(n, r, m):
    res = 1
    r = min(r, n - r)

    for i in range(1, r + 1):
        res = res * (n - r + i) % m
        res = res * modpow(i, m - 2, m) % m
    return res

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

total = (total - combination(n, a, mod) - combination(n, b, mod)) % mod

print(total)

Submission status: Time Limit Exceeded

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

nb = str(bin(n))[2:]
nblis = []
for k in range(len(nb)):
  if nb[-k-1] == '1':
    nblis.append(k)

two = [2]
for k in range(len(nb)-1):
  two.append(two[-1]*two[-1]%mod)


ans = 1
for item in nblis:
  ans = ans * two[item] %mod



bi = str(bin(mod-2))[2:]
blis = []
for k in range(len(bi)):
  if bi[-k-1] == '1':
    blis.append(k)


def modinv(N):
  if N == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(len(bi)):
      li.append(N%mod)
      N = N*N%mod
    for item in blis:
      res = res * li[item] %mod
    return res

ans_a = 1
for k in range(n-a+1, n+1):
  ans_a = ans_a*k%mod
for k in range(2, a+1):
  ans_a = ans_a*modinv(k)%mod


ans_b = 1
for k in range(n-b+1, n+1):
  ans_b = ans_b*k%mod
for k in range(2, b+1):
  ans_b = ans_b*modinv(k)%mod

print((ans-ans_a-ans_b-1)%mod)

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, p):
    r = min(n, n - r)
    upper = 1
    for i in range(n, n - r, -1):
        upper = (upper * i) % p

    lower = 1
    for i in range(1, r + 1):
        lower = (lower * i) % p

    return (upper * pow(lower, p - 2, p)) % p

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

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

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#組み合わせnCr　１
from functools import reduce
def nCr(n,r,DIV):
  if r<n-r:
    r=n-r
  if r==0:
    return 1
  f=lambda x,y:x*y%DIV
  X=reduce(f,range(n-r+1,n+1))
  Y=reduce(f,range(1,r+1))
  return X*pow(Y,DIV-2,DIV)%DIV

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

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ΣnCiが高速に計算できればいいがNがでかい -> なんかΣncrでググったら高速化できるらしい?
# なんかi=0 -> i=nで2^nになるらしい。これは繰り返し二乗法でいけそう

# 最終的にΣnCi(i=1, i<=n) - nCa - nCaができればいい

# なぜか手持ちのライブラリがことごとくダメ

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


def rep(i, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        tmp = rep(i, n // 2) % mod
        return tmp * tmp % mod
    else:
        return i * rep(i, n - 1) % mod


# なぜかうまくいかない
# def ncr(n, r):
#     res = 1
#     for i in range(1, r + 1):
#         res = res * (n - i + 1) // i
#         res %= mod
#     for i in range(2, r + 1):
#         res *= rep(i, mod - 2)
#         res %= mod
#     return res

# なぜかうまくいかない
# def cmb(n, r, mod):
#     if (r < 0 or r > n):
#         return 0
#     g1 = [1, 1]  # 元テーブル
#     g2 = [1, 1]  #逆元テーブル
#     inverse = [0, 1]  #逆元テーブル計算用テーブル
#     N = 10**6  # なんでだろうね
#     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)
#     return g1[n] * g2[r] * g2[n - r] % mod


# なぜかうまくいく
def nCrMod(n, r, p):
    ret = 1
    # 分子
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret %= p
    # 分母
    for i in range(2, r + 1):
        # ret //= i なんかこれがおかしい（なんでだろうね）
        ret *= rep(i, p - 2)  # なぜかここでやらないと駄目だった
        ret %= p
    # ret = repMod(ret, p - 2, p) # なぜかここでやると駄目だった
    return ret % p


ans = (rep(2, n) - 1 - nCrMod(n, a, mod) - nCrMod(n, b, mod)) % mod  # なぜかうまくいく
# ans = (rep(2, n) - 1 - ncr(n, a) - ncr(n, b)) % mod なぜかうまくいかない
# ans = (rep(2, n) - 1 - cmb(n, a, mod) - cmb(n, b, mod)) % mod なぜかうまくいかない
while ans < 0:
    ans += mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#ΣnCk-nCa-nCb
#Σnck=(1+1)^n
from math import factorial
n,a,b=map(int,input().split())
X=factorial(n)//factorial(a)//factorial(n-a)
Y=factorial(n)//factorial(b)//factorial(n-b)
print((2**n-X-Y-1)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys,collections,math
input = sys.stdin.readline

n,a,b = list(map(int,input().split()))
m = 10**9+7
ans = pow(2,n,m)


la  = 1
laa = 1
for i in range(n,n-a,-1):
    la = la*i
for i in range(1,a+1):
    laa = laa*i

lb  = 1
lbb = 1
for i in range(n,n-b,-1):
    lb = lb*i
for i in range(1,b+1):
    lbb = lbb*i

la = (la*pow(laa,10**9+5,m))%m
lb = (lb*pow(lbb,10**9+5,m))%m

print((ans-la-lb-1)%m)

Submission status: Time Limit Exceeded

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

aa = math.factorial(n)/math.factorial(n-a)/math.factorial(a)
bb = math.factorial(n)/math.factorial(n-b)/math.factorial(b)

ans = int(((1 << n) - 1 - aa - bb) % (10**9+7))
print(ans)

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


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

Submission status: Time Limit Exceeded

Solution code:

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

def combo(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

print((allpair - combo(n, a) - combo(n, b) - 1) % MOD)

Submission status: Time Limit Exceeded

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

modp = mod                     # 素数であることが前提
max_r = 10 ** 7               # 必要分だけ用意する 10**7が限度
factinv = [1, 1] + [0]*max_r  # factinv[n] = ((n!)^(-1) mod modp)
inv = [0, 1] + [0]*max_r      # factinv 計算用

fact = {}

def cmb(n, r, p):
    assert n < p, 'n is less than modp'
    assert r < max_r, 'n in less than max_n'
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    if (n, r) in fact:
        return fact[(n, r)] * factinv[r] % p
    else:
        f = 1
        for i in range(n, n-r, -1):
            f = f * i % p
        fact[(n, r)] = f
        return f * factinv[r] % p

for i in range(2, max_r + 1):
    inv[i] = (-inv[modp % i] * (modp // i)) % modp
    factinv[i] = (factinv[i-1] * inv[i]) % modp

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.special import comb

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

MOD = 10**9 + 7

base = 2**n - 1
a = comb(n, a, exact=True)
b = comb(n, b, exact=True)

print((base - a - b)%MOD)

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
mod=10**9+7
def comb(n,k,mod):
  if k>n-k:
    k=n-k
  c=1
  for i in range(n-k+1,n+1):
    c*=i
    c%=mod
  d=1  
  for i in range(1,k+1):
    d*=i
    d%=mod
  return (c*pow(d,mod-2,mod))%mod

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

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
mod=10**9+7
from scipy.special import comb
ans=(2**n-1)%mod-comb(n,a,exact=True)%mod-comb(n,b,exact=True)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
mod=10**9+7
def comb(n,k,mod):
  if k>n-k:
    k=n-k
  c=1
  for i in range(n-k+1,n+1):
    c*=i
  d=1  
  for i in range(1,k+1):
    d*=i
  return (c*pow(d,mod-2,mod))%mod

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

Submission status: Time Limit Exceeded

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

def comb(m):
    x = 1
    y = 1
    for i in range(m):
        x = x*(n-i)%mod #コンビネーションの分子
        y = y*(i+1)%mod #コンビネーションの分母
    return (x * pow(y, mod-2, mod) % mod)

print((sum-comb(a)-comb(b))%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

P = 10 ** 9 + 7


def conb(n, r):
    resp = n
    for i in range(1, r):
        resp = (resp * (n - i) * pow(i + 1, P - 2))%P
    return resp


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



print((pow(2, n) - conb(n, a) - conb(n, b)-1)%P)

Submission status: Time Limit Exceeded

Solution code:
import math
from operator import mul
from functools import reduce
n, a, b = map(int, input().split())
s=0
def combinations_count(n, r):
    #return math.factorial(n) // (math.factorial(n - r) * math.factorial(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
if n==2:
    print('0')
else:
    if n%2==1:
        for i in range(1,int(n/2)+1):
            s+=combinations_count(n, i)
        s=s*2
        s+=1
        s-=combinations_count(n, a)
        s-=combinations_count(n, b)
    else:
        for i in range(1,int(n/2)):
            s+=combinations_count(n, i)
        s=s*2
        s+=combinations_count(n, int(n/2))
        s+=1
        s-=combinations_count(n, a)
        s-=combinations_count(n, b)
    print(s)

Submission status: Time Limit Exceeded

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

def comb(n,r):
    return math.factorial(n) // (math.factorial(n-r ) *math.factorial(r))
def pow1(x, n):
    if n == 0: return 1
    value = pow1(x, int(n / 2))
    value *= value
    if n % 2 == 1: value *= x
    return value

print((pow1(2,n) - comb(n,a) -comb (n,b) - 1)%(pow1(10,9) + 7))

Submission status: Time Limit Exceeded

Solution code:
def pre_cmb(N, MOD):  # cmbの前準備
    FACT = [1, 1]  # 階乗
    INV = [0, 1]  # 各iの逆元
    FACTINV = [1, 1]  # 階乗の逆元

    for i in range(2, N + 1):
        FACT.append((FACT[-1] * i) % MOD)
        INV.append(pow(i, MOD-2, MOD))
        FACTINV.append((FACTINV[-1] * INV[-1]) % MOD)
    PRELIST = FACT, FACTINV
    return PRELIST


def cmb(N, R, MOD, PRELIST):  # nCr(mod p)
    FACT, FACTINV = PRELIST
    if (R < 0) or (N < R):
        return 0
    R = min(R, N - R)
    return FACT[N] * FACTINV[R] * FACTINV[N-R] % MOD


n, a, b = map(int, input().split())
mod = 10**9+7
prelist = pre_cmb(n, mod)
exc = cmb(n, a, mod, prelist) + cmb(n, b, mod, prelist)
print((pow(2, n, mod) - exc - 1) % mod)

Submission status: Time Limit Exceeded

Solution code:
def pre_cmb(N, MOD):  # cmbの前準備
    FACT = [1, 1]  # 階乗
    INV = [0, 1]  # 各iの逆元
    FACTINV = [1, 1]  # 階乗の逆元

    for i in range(2, N + 1):
        FACT.append((FACT[-1] * i) % MOD)
        INV.append(pow(i, MOD-2, MOD))
        FACTINV.append((FACTINV[-1] * INV[-1]) % MOD)
    PRELIST = FACT, FACTINV
    return PRELIST


def cmb(N, R, MOD, PRELIST):  # nCr(mod p)
    FACT, FACTINV = PRELIST
    if (R < 0) or (N < R):
        return 0
    R = min(R, N - R)
    return FACT[N] * FACTINV[R] * FACTINV[N-R] % MOD



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

Submission status: Time Limit Exceeded

Solution code:
# N = int(input())
def cmb(n, r, mod):
    x = 1
    for i in range(r):
        x = x * (n-i) % mod
    return (x * g2[r]) % mod


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


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

def pow_(x, n):
    if n == 0:
        return 1

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

    return (k * x) % MOD

n, a, b = [int(i) for i in input().split()]
MOD = 10 ** 9 + 7
n_num = pow_(2, n) - 1
a_num = cmb(n, a, MOD)
b_num = cmb(n, b, MOD)
print((n_num - a_num - b_num) % MOD)

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

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

if n%2 == 1:
    for i in range(n//2):
        ans += cmb(n,i+1)*2

else:
    for i in range(n//2-1):
        ans += cmb(n,i+1)*2
    ans += cmb(n,n//2)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
MOD = 10**9 + 7


def calc_2(n):
    ans = 1
    for i in range(n):
        ans *= 2
        ans %= MOD
    return ans - 1


def cmb(N, A):
    num = reduce(lambda x, y: x * y % MOD, range(N, N - A, -1))
    den = reduce(lambda x, y: x * y % MOD, range(1, A + 1))
    return num * pow(den, MOD - 2, MOD) % MOD


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


print((calc_2(n) - cmb(n, a) - cmb(n, b)) % MOD)

Submission status: Time Limit Exceeded

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

def factorial(n):
    v = 1
    for i in range(1, n + 1):
        v *= i
    return v

def comb(a, b):
    return factorial(a) // (factorial(b) * factorial(a - b))

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

Submission status: Time Limit Exceeded

Solution code:
N,a,b = map(int,input().split())
MOD = 10**9+7
def combination(n,r):
    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]
factinv = [1,1]
inv = [0,1]
for i in range(2,N+1):
    fact.append((fact[-1]*i)%MOD)
    inv.append((-inv[MOD%i]*(MOD//i)%MOD))
    factinv.append((factinv[-1]*inv[-1]%MOD))
result = pow(2,N,MOD) - 1
nashi = combination(N,a) + combination(N,b)
if result - nashi < 0:
    print(result - nashi + MOD)
else:
    print(result - nashi)

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

x=cmb(n,a)+cmb(n,b)
y=pow(2,n)-1
ans=(y-x%(10**9+7))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def cmb_mod(n, r, m):
    r = min(r, n-r)
    res = 1
    for i in range(0, r):
        res *= divide_mod(n-i, r-i, m)
        res %= m
    return res


def divide_mod(x, y, m):
    return (x%m) * pow_mod(y, m-2, m) % m


def pow_mod(base, exp, m):
    if exp == 1:
        return base % m
    elif exp % 2:
        return pow_mod(base, exp-1, m) * base % m
    else:
        return pow_mod(base, exp//2, m) ** 2 % m


def main():
    n, a, b = NMI()
    all = pow_mod(2, n, MOD) - 1
    ans = all - cmb_mod(n, a, MOD) - cmb_mod(n, b, MOD)
    ans %= MOD
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# from scipy.special import comb
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
all = (2**n - 1)%mod

def comb(n, r):
  c = 1
  m = 1
  r = min(n-r, r)
  for i in range(r):
    c = c * (n - i) % mod
    m = m * (i + 1) % mod
  return c * pow(m, mod-2, mod) % mod

nca = comb(n, a)
ncb = comb(n, b)
all -= nca + ncb
print(all%mod)

Submission status: Time Limit Exceeded

Solution code:
# from scipy.special import comb
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
all = (2**n - 1)%mod

c = 1
m = 1
a = min(n-a, a)
for i in range(a):
    c = c*(n-i)%mod
    m = m*(i+1)%mod

nca = c*pow(m, mod-2, mod)%mod

c = 1
m = 1
a = min(n-b, b)
for i in range(b):
    c = c*(n-i)%mod
    m = m*(i+1)%mod

ncb = c*pow(m, mod-2, mod)%mod    

# nca = comb(n, a, exact=True)
# ncb = comb(n, b, exact=True)
all -= nca + ncb
print(all%mod)

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
c=d=1
e=0
m=10**9+7
for i in range(1,n+1):
  c=(c*(n+1-i))%m
  d=(d*i)%m
  if i==a or i==b:
    e+=c*pow(d,m-2,m)%m
f=1
for i in range(n):
  f*=2
  if f>m:
    f%=m
print(f-e-1)

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
c=d=1
e=0
m=10**9+7
for i in range(1,n+1):
  c=(c*(n+1-i))%m
  d=(d*i)%m
  if i!=a and i!=b:
    e+=c*pow(d,m-2,m)%m
print(e%m)

Submission status: Time Limit Exceeded

Solution code:

n, a, b = map(int, input().split())
all = (2**n - 1)%1000000007
# all = 2**n - 1
# print(all)
nca = 1
n_tmp = n
for i in range(1,a+1):
    nca *= n_tmp
    nca //= i
    # nca %= 1000000007
    n_tmp -= 1
    # a -= 1
# print(nca)
ncb = 1
n_tmp = n
for i in range(1,b+1):
    ncb *= n_tmp
    ncb //= i
    # ncb %= 1000000007
    n_tmp -= 1

all -= int(nca) + int(ncb)
print(int(all%1000000007))

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest
import math
# 検索用タグ、繰り返し2乗法、膨大な組み合わせ、フェルマーの小定理
# https://math.nakaken88.com/textbook/cp-binary-exponentiation-and-recursive-function/
# ちなみに、pythonでは(pow())にて実装済みなので、自作不要。
# https://note.com/keyem/n/n526ee14fe3de
# 「繰り返し2乗法」はプログラム数学とでも呼ぶべき分野(高校、大学数学とは多分違う。「プログラムに対してのみ」効果があるので・・)
# --------------------------------------------------
# この問題のポイントは・・「組み合わせをXの(y)-2乗」という形に変換する事。
# https://img.atcoder.jp/abc156/editorial.pdf
# https://qiita.com/ofutonfuton/items/92b1a6f4a7775f00b6ae
# 10億種類の花から10万個を選ぶ・・というのは処理速度的に無理だが、
# 「Xの?乗」という形に変換できれば、繰り返し2乗法で高速に計算できる!(pythonならpow()を使うだけでOK)
# --------------------------------------------------

# 膨大な組み合わせ(10億C10万とか)の数を求める関数。
def cmb(n, r):
    mod = 10**9+7
    ans = 1
    for i in range(r):
        ans *= n-i
        ans %= mod
    for i in range(1, r+1):
        ans *= pow(i, mod-2, mod)
        ans %= mod
    return ans

def resolve():

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

    # 10の9乗+7を算出しておく。
    div = pow(10, 9) + 7

    # まず、a,bを無視した総パターン数を求める。
    sum_pattern = pow(2, n) - 1 % div

    # ここから、a,bのパターン数を減算する。
    # a,bのパターン数は、フェルマーの小定理を基にして、組み合わせでなく、pow()で求めるようにする。(ここがポイント)
    print(sum_pattern - cmb(n, a) - cmb(n, b))


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4 1 3"""
        output = """7"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """1000000000 141421 173205"""
        output = """34076506"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Time Limit Exceeded

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

def nCr(n_, r_, m_):
  c = min(r_ , n_ - r_)
  bunshi = 1
  bunbo = 1
  for i in range(1,c+1):
    bunshi *= (n_+1-i) % m_
    bunbo *= i % m_
  return bunshi * pow(bunbo, m_-2, m_) % m_

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

Submission status: Time Limit Exceeded

Solution code:
m = 10**9+7

def nCr(n,r,m):
  c = min(r,n-r)
  bunshi = 1
  bunbo = 1
  for i in range(1,c+1):
    bunshi *= (n+1-i)%m
    bunbo *= i%m
  return bunshi*pow(bunbo,m-2,m)%m

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

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

Submission status: Time Limit Exceeded

Solution code:
def nCr(n,r):
  c = min(r,n-r)
  bunshi = 1
  bunbo = 1
  for i in range(1,c+1):
    bunshi *= (n+1-i)%(10**9+7)
    bunbo *= i%(10**9+7)
  return bunshi*pow(bunbo,10**9+5,10**9+7)%(10**9+7)
  

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

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

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

def nCr(n,r):
  c = min(r,n-r)
  bunshi = 1
  bunbo = 1
  for i in range(1,c+1):
    bunshi *= (n+1-i)%(10**9+7)
    bunbo *= i%(10**9+7)
  return bunshi*pow(bunbo,10**9+5,10**9+7)%(10**9+7)
  

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

#答え用の関数
ans = 0
#Σ(k 1~n) nCk = 2^n
ans += pow(2,n,10**9+7)
ans -= (nCr(n,a)+nCr(n,b)+1)
ans = ans%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

#答え用の関数
ans = 0
#Σ(k 1~n) nCk = 2^n
ans += pow(2,n,10**9+7)
nCa = (factorial(n)//(factorial(a)*factorial(n-a)))%(10**9+7)
nCb = (factorial(n)//(factorial(b)*factorial(n-b)))%(10**9+7)
ans -= (nCa+nCb+1)
ans = ans%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

#答え用の関数
ans = 0
#Σ(k 1~n) nCk = 2^n
ans += (2**n)%(10**9+7)
nCa = (factorial(n)//(factorial(a)*factorial(n-a)))%(10**9+7)
nCb = (factorial(n)//(factorial(b)*factorial(n-b)))%(10**9+7)
ans -= (nCa+nCb+1)
ans = ans%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

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

def combinations(n, r):
    X = math.factorial(n)
    Y = math.factorial(n - r) * math.factorial(r)
    return X * pow(Y, mod-2)%mod

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

print(int(pow(2, n) - 1  - combinations(n, a)-combinations(n, b)))

Submission status: Time Limit Exceeded

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

def combinations(n, r):
    X = math.factorial(n)
    Y = math.factorial(n - r) * math.factorial(r)
    return X * pow(Y, -1)

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

lis = list()

lis.append(combinations(n, a))
lis.append(combinations(n, b))

print(int(pow(2, n) - 1  - (sum(lis)%mod)))

Submission status: Time Limit Exceeded

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

def combinations(n, r):
    X = math.factorial(n)
    Y = math.factorial(n - r) * math.factorial(r)
    return X * (Y**(-1))

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

lis = list()

lis.append(combinations(n, a))
lis.append(combinations(n, b))

print(int(2**n-1 - sum(lis)%mod))

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

lis = list()

for i in range(1,n+1):
    if i == a or i ==b:
        pass
    else:
        lis.append(combinations(n, i))

print(sum(lis)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

lis = list()

for i in range(1,n+1):
    if i == a or i ==b:
        pass
    else:
        lis.append(combinations(n, i))

print(sum(lis)%(10*9+7))

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

print((pow(2, n) - cmb(n, a) - cmb(n, b) - 1) % (pow(10, 9)+7))

Submission status: Time Limit Exceeded

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


n, a, b = map(int, input().split())
a_comb = comb(n,a,mod)
b_comb = comb(n,b,mod)
print(2 ** n -1 - a_comb - b_comb)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

class ModOperator:
    def __init__(self, MOD: int = 10 ** 9 + 7):
        self.MOD = MOD
        self.factorials = [1, 1]    # 階乗のメモ

    # x^n % MOD
    def mod_pow(self, x: int, n: int):
        bi = str(format(n, "b"))
        res = 1
        a = x
        for i in range(len(bi)):
            if n >> i & 1:
                res = (res * a) % self.MOD
            a = (a * a) % self.MOD
        return res
    
    # x! % MOD
    def mod_fact(self, x: int):
        if x < len(self.factorials):
            return self.factorials[x]
        else:
            res = self.factorials[-1]
            for i in range(len(self.factorials), x + 1):
                res = res * i % self.MOD
                self.factorials.append(res)
        return res % self.MOD

    # inverse of a number
    def mod_inv(self, x: int):
        return self.mod_pow(x, self.MOD - 2)
    
    # conmination nCk
    def mod_comb(self, n: int, k: int):
        numerator = self.mod_fact(n)
        denomintator1 = self.mod_fact(k)
        denomintator2 = self.mod_fact(n - k)
        denomintator = denomintator1 * denomintator2 % self.MOD
        return numerator * self.mod_inv(denomintator) % self.MOD


def main():
    n, a, b = map(int, input().split())
    op = ModOperator()
    print((op.mod_pow(2, n) - op.mod_comb(n, a) - op.mod_comb(n, b) - 1) % MOD)

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        x%=MOD
    return K * x

# nCk
K_MAX = 10**7
MOD = 10**9 + 7
fac, finv, inv = [0]*(K_MAX+1), [0]*(K_MAX+1), [0]*(K_MAX+1)
# nCk (k<=10^7, n<=10^9)
def com_init():
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2,K_MAX+1):
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

def com(n, k):
    ans = 1
    for i in range(n-k+1,n+1):
        ans *= i
        ans %= MOD
    return (ans * finv[k]) % MOD


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

all_comb = pow_k(2,n)
a_comb = com(n,a)
b_comb = com(n,b)

ans = all_comb - a_comb - b_comb -1
print(ans%MOD)