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
if __name__ == '__main__':
    n ,a, b = map(int, input().split())
    sum = 2 ** n -1


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


    sum = sum % (10 ** 9 + 7)

    print(int(sum))

Submission status: Time Limit Exceeded

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

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

if(n==2):
  print('0')
else:
  sigma = 0
  for i in range(n):
    if ((i+1) != a and (i+1) != b):
      sigma += combinations_count(n, (i+1))

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

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
mod = 1000000007
y = pow(2, n, mod)-1
p = 1
q = 1
for i in range(a):
    p *= i+1
    q *= n-i
ca = q//p % mod
p = 1
q = 1
for i in range(b):
    p *= i+1
    q *= n-i
cb = q//p % mod
print((y-ca-cb)%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

all = 2**n - 1
tmp1 = 1
tmp2 = 1
tmp3 = 1
tmp4 = 1
for i in range(1, a+1):
    tmp1 *= n - i + 1
for i in range(1, a+1):
    tmp2 *= i
for i in range(1, b+1):
    tmp3 *= n - i + 1
for i in range(1, b+1):
    tmp4 *= i
result = all - ((tmp1//tmp2) + (tmp3//tmp4)) 
print(result%(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 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

all = 2**n -1

ans = all - comb(n,a) - comb(n,b)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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(" "))
print((2**n - cmb(n,a) - cmb(n,b))%(10**9+7)-1)

Submission status: Time Limit Exceeded

Solution code:
p = 10 ** 9 + 7
n,a,b = map(int,input().split())
sum = 0
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

fact = [1, 1] 
factinv = [1, 1] 
inv = [0, 1] 
 
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)

for i in range(1,n + 1):
    if i != a and i != b:
        sum+=cmb(n, i, p)
print(sum%p)

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

Submission status: Time Limit Exceeded

Solution code:
N,a,b=map(int,input().split())
from math import factorial
def conbi(n, r):
    return factorial(n) // (factorial(n - r)*factorial(r))
total=(2**N)-1
A=conbi(N,a)
B=conbi(N,b)
ans=(total-A-B)%1000000007
print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

    return result

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

for i in range(n):
  now = i + 1
  before = c
  # print(now)
  if now != a and now != b:
    # print(now)
    # print(cmb(n,now))
    c += cmb(n, now)

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

Submission status: Time Limit Exceeded

Solution code:
#D

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())
whole_sum = (2 ** n) - 1
mod = 10 ** 9 + 7

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

print(whole_sum % mod)

Submission status: Time Limit Exceeded

Solution code:
# ABC156d


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    # 再帰関数を使わない限りPypyで出すこと
    import math
    MOD = 10**9+7

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

    n, a, b = map(int, input().split())
    # print(2**n)
    #print(2**n % MOD-1-combinations_count(n, a)-combinations_count(n, b))

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

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

        return K % MOD * x % MOD

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

    #print(cmb(n, a))
    ans = pow_k(2, n) - 1 - cmb(n, a) - cmb(n, b)
    while ans < 0:
        ans += MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,a,b = map(int,input().split())
    tmp = 1
    ans = 0
    for n,r in zip(range(n,-1,-1),range(1,n+1)):
        tmp = tmp*n//r
        if r != a and r != b:
            ans += tmp
    print(ans%(10**9+7))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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



xx = 2**n % mod


print((xx - comb(n,a,mod) - comb(n,b,mod) -1) % mod)

Submission status: Time Limit Exceeded

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

t=1000000007

def mod(k):
    return k%t

def comb(n,k,p):
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  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

base=1
for i in range(n):
    base=mod(base*2)
    
print(mod(2*t+base-1-comb(n,a,t)-comb(n,b,t)))

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

def combinations_count(n, r):
  if n < r:
    return 0
  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

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

Submission status: Time Limit Exceeded

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

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

all = 2**n -1


ans = all - comb(n,a) - comb(n,b)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod + x % mod)% mod
def comb(n,k,mod):
    c = 1
    for i in range(k):
        c = c*(n-i)%mod
        c = c*mod_inv(i+1,mod)%mod
    return c
n,a,b = map(int,input().split())
mod = 10**9+7
p = comb(n,a,mod)
q = comb(n,b,mod)
c = 1
k = 2
ans = 1
while n > 0:
    if n % (c*2) == c:
        n -= c
        ans *= k
        ans %= mod
    c *= 2
    k = k*k
    k %= mod
print((ans-p-q-1)%mod)

Submission status: Time Limit Exceeded

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

def nCmMOD(A,B,Mod):
    #a conb b を　Mod で割った余り
    num,den=1,1
    for i in range(B):
        num*=(A-i)
        den*=(i+1)
        num%=Mod
        den%=Mod
    return (num*pow(den,Mod-2,Mod))%Mod

A=nCmMOD(n,a,mod)
B=nCmMOD(n,b,mod)
#print(A,B)

def pow_r(x, n):
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2, n // 2)%mod
    else:  # standard case ② n is odd
        return x * pow_r(x ** 2, (n - 1) // 2)%mod

An=pow_r(2,n)
print((An-1+mod*2-A-B)%mod)

Submission status: Time Limit Exceeded

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

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 )

n,a,b = map(int, input().split())
ans = 0
for i in range(1,(n+1)):
    r = i
    ans += cmb(n,r,mod)
    ans  = ans%mod
    print(ans)

for x in [a,b]:
    if (ans - cmb(n,x,mod))<0:
        ans = ans+mod - cmb(n,x,mod)
    else:
        ans -= cmb(n,x,mod)
print(ans)

Submission status: Time Limit Exceeded

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

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

res = 0
for i in range(n):
  if i+1 != a and i+1 != b:
    res += combinations_count(n, i+1)
    res = res % mod
print(res)

Submission status: Time Limit Exceeded

Solution code:
def combination(a, b) :
    ans1 = 1
    ans2 = 1
    if a//2 < b :
        b = a-b
    for l in range(a, a-b, -1) :
        ans1 = (ans1*l)%(10**9+7)
    for m in range(1, b+1) :
        ans2 = (ans2*m)%(10**9+7)
    return ans1/ans2

ans = 0
n, a, b = map(int, input().split())
for i in range(1, n+1) :
    if i == a or i == b :
        continue
    plus = combination(n, i) % (10**9+7)
    ans = (ans+plus) % (10**9+7)
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
n,a,b = map(int,input().split())
sum = 0
l = [1]
for i in range(2,n + 1):
    l.append(l[-1] * i % mod)
for i in range(1,n + 1):
    if i != a and i != b:
        if i != n:
            sum+=l[n - 1] / l[i - 1] / l[n - i - 1]
        else:
            sum+=1
print(int(sum))

Submission status: Time Limit Exceeded

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

print(c%(d))

Submission status: Time Limit Exceeded

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

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

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(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


nca = comb(n, a, mod)#factorial(n) // factorial(a) // factorial(n-a)
ncb = comb(n, b, mod)#factorial(n) // factorial(b) // factorial(n-b)

ans = pow_k(2, n)

ans -= 1 + nca + ncb
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

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])
            result %= MOD

    return result

def solve():
    n, a, b = [int(_) for _ in input().split()]
    return (2 ** n)%MOD - 1 - cmb(n, a) - cmb(n, b)

if __name__ == '__main__':
    print(solve()%MOD)

Submission status: Time Limit Exceeded

Solution code:
M,A,B = map(int, input().split())
Ans = 0

for a in range(1,M+1):
  if a == A or a == B:
    continue  

  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 )


 
  Ans = Ans + cmb(M,a,mod)
  Ans = Ans % 1000000007


print(Ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

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

ans = 0

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

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

for i in range(1, n+1):
    if i != a and i != b:
        ans += cmb(n, i, mod)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

ans = 0
for i in range(1,n+1):
  if i==a or i ==b:
    continue
  ans += combinations_count(n, i)
  
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, a, b = [int(_) for _ in input().split()]

total = 0
for num in range(1, n + 1):
  if num == a or num == b:
    continue
  m = 1
  for i in range(1, num + 1):
    m *= (n + 1 - i) / i
  total += m

print(int(total))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def cmb_fnct(MOD):
    #MOD:素数
    fact_mod = [1,1]
    inv_mod = [0,1]
    inv_fact_mod = [1,1]
    i = len(fact_mod)
    i_ = len(inv_fact_mod)

    def cmb(n,r):
        nonlocal i, i_
        r = min(r, n-r)
        if r<0: 
            return 0
        if r==0:
            return 1
        if r==1: 
            return n%MOD

        while n >= i:
            fact_mod[i:i] = [(fact_mod[i-1]*i)%MOD]
            i += 1

        while n-r >= i_:
            inv_mod[i_:i_] = [(-inv_mod[MOD%i_]*(MOD//i_))%MOD]
            inv_fact_mod[i_:i_] = [(inv_fact_mod[i_-1]*inv_mod[i_])%MOD]
            i_ += 1

        return fact_mod[n] * inv_fact_mod[r] * inv_fact_mod[n-r] % MOD
    return cmb

def solve():
    n,a,b = map(int, input().split())
    cmb = cmb_fnct(10**9+7)
    res = pow(2,n,10**9+7) - cmb(n,a) - cmb(n,b) - 1    
    return str(res%(10**9+7))

if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

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

MOD = 10 ** 9 + 7


ans = 2 ** N - 1
ans %= MOD


def cumprod(arr, MOD):
    L = len(arr)
    Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]
        arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]
        arr[n] %= MOD
    return arr.ravel()[:L]


def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64)
    x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64)
    x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv


fact, fact_inv = make_fact(B + 10, MOD)

arr = cumprod(list(range(N, N-B, -1)), MOD)

a = arr[A - 1] * fact_inv[A]
a %= MOD
b = arr[B-1] * fact_inv[B]
b %= MOD

# print(mb)
# print(fact_inv)

'''
a = ma * fact_inv[A]
a %= MOD

b = mb * fact_inv[B]
b %= MOD
'''

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a,b = list(map(int,input().split()))
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 = 1
  b = 1
  c = 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*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
mod = 10**9 + 7
ans = (power_func(2,n,mod)-1)%mod
ac = comb(n,a,mod)
bc = comb(n,b,mod)
ans = (ans-ac-bc)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
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())
mod = 10**9 + 7
print((2**n - 1 - cmb(n,a) - cmb(n,b))%mod)

Submission status: Time Limit Exceeded

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

c -= factorial(n) // factorial(a) // factorial(n - a)%d
c -= factorial(n) // factorial(b) // factorial(n - b)%d

print(c%(d))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

@lru_cache(maxsize=None)
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())
s = 0
for i in range(1, N + 1):
    if i in (A, B):
        continue
    s += cmb(N, i)

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

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


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


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


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

mod = 10**9 + 7
A = pow_by_binary_exponentiation(2, n, mod) - 1

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

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
ans=0
def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = (numer*(n1-i)) % mod
        denom = (denom*i) % mod
    return numer * pow(denom, mod-2, mod) % mod
for i in range(1,n+1):
    if i==a or i==b:
        continue
    ans+=combination(n,i)
print(ans)

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

ans=0

for i in range(1,n+1):
    if(i==a or i==b):
        continue
    ans+=comb(n,i,10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N, a, b = map(int, input().split())
    
    MOD = 10 ** 9 + 7
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    
    # 必要なだけforを回す。N+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)
    
    # nCr n個から重複を許さずr個の組み合わせを選ぶ
    def cmb(n, r):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return fact[n] * factinv[r] * factinv[n-r] % MOD
    
    ans = 0
    for i in range(1, N+1):
        if i == a or i == b:
            continue
        ans += cmb(N, i) % MOD
    
    return ans % MOD

print(solve())

Submission status: Time Limit Exceeded

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

MOD = 1000000007

def pow_mod(x, y):
    if y == 0: return 1
    ans = 1
    while y > 1:
        if y % 2 != 0: 
            ans *= x
            ans %= MOD
        x *= x
        x %= MOD
        y //= 2
    return ans * x % MOD 

mod_inv = lambda x: pow_mod(x, MOD - 2)

nCk = {0: 1}

for i in range(1, max(a,b) + 1):
  nCk[i] = nCk[i-1] * ((n-i+1) % MOD)
  nCk[i] %= MOD
  nCk[i] *= mod_inv(i)
  nCk[i] %= MOD

print((pow_mod(2, n) - 1 - nCk[a] - nCk[b]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
mod = int(1e+9) + 7
def extgcd(a, b):
  if b == 0:
    return 1, 0
  else:
    x, y, u, v, k, l = 1, 0, 0, 1, a, b
    while l != 0:
      x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
      k, l = l, k % l
    return x
def inved(x):
  a = extgcd(x, mod)
  return a % mod
def doubling(N, M):
  y = 1
  base = N
  while M != 0:
    if M % 2 == 1:
      y *= base
      y %= mod
    base *= base
    base %= mod
    M //= 2
  return y

A = doubling(2, n)
A = (A - 1) % mod
proda, prodb = 1, 1
for i in range(a):
  proda *= ((n - i) * inved(i + 1)) % mod
  proda %= mod
for i in range(b):
  prodb *= ((n - i) * inved(i + 1)) % mod
  prodb %= mod
print((A - proda - prodb) % mod)

Submission status: Time Limit Exceeded

Solution code:
def sq(a, b, mod):  # aのb乗を剰余,kは初期値#20191116-D-Knight
    if b == 0:
        return 1
    elif b % 2 == 0:
        return sq(a, b // 2, mod)**2 % mod
    else:
        return sq(a, b - 1, mod) * a % mod


def nCk(n, k, mod=10 ** 9 + 7):
    x = max(k, n - k)
    y = min(k, n - k)
    kkai = 1
    for i in range(2, y + 1):
        kkai = (kkai * i) % mod
    nkkai = 1
    for i in range(x + 1, n + 1):
        nkkai = (nkkai * i) % mod
    answer = sq(kkai, mod - 2, mod) * nkkai % mod
    return answer
ans = 0
mod = 10**9+7

n, a, b = map(int, input().split())
for i in range(1, n+1):
    if i == a or i == b:
        continue
    ans += nCk(n, i)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
 
n, a, b = na()
mod = 1000000007
 
def comb(n, r, mod):
    if n < 0 or r < 0 or r > n: return 0
    nu = 1
    de = 1
    for i in range(r):
        nu = nu * (n-i) % mod
        de = de * (i+1) % mod
    return nu * inv(de, mod) % mod
 
def inv(a, mod):
    b = mod
    p, q = 1, 0
    while b > 0:
        c = a//b
        d = a; a = b; b = d % b
        d = p; p = q; q = d-c*q
    return p+mod if p < 0 else p
 
print((pow(2, n, mod) - comb(n, a, mod) - comb(n, b, mod) - 1)%mod)

Submission status: Accepted

Solution code:
def nCk(n, k, mod):
    nu = 1
    de = 1 
    for i in range(1, k+1):
        nu *= (n-i+1)
        de *= i
        nu = nu % mod
        de = de % mod
    ans = nu * pow(de, mod-2, mod) % mod
    return ans

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

Submission status: Accepted

Solution code:
# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np
# import heapq
# from collections import deque

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
n, a, b = map(int, input().split())
# A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr

mod = 10 ** 9 + 7

def comb(n, m, mod = 10 ** 9 + 7):
    numerator = 1
    denominator = 1
    for i in range(1, m + 1):
        numerator = numerator * (n - i + 1) % mod
        denominator = denominator * i % mod
    d_inv = pow(denominator, mod - 2, mod)
    return numerator * d_inv % mod

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

print((pow(2, n, mod) - 1 - cmb_n_a - cmb_n_b) % mod)

Submission status: Accepted

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

for i in range(b):
    x=x*(i+1)%m
    y=y*(n-i)%m
    if i+1==a:
        a=b
        ALL-=y*pow(x,m-2,m)

print(ALL%m)

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    n,a,b = i_map()
    s = pow(2,n,MOD) - 1

    def fur(n,r):
        p,q = 1, 1
        for i in range(r):
            p = p*(n-i)%MOD
            q = q*(i+1)%MOD
        return (p * pow(q,MOD-2,MOD)) % MOD

    print((s - fur(n,a) - fur(n,b)) % MOD)



if __name__=="__main__":
    main()

Submission status: Accepted

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