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

mod = 1000000007

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

mod = 10**9+7 #出力の制限
N = n
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 )

print(pow(2,n,mod)-1-(cmb(n,a,mod)+cmb(n,b,mod)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,a,b= map(int,input().split())
if a>n/2:
    a=n-a
if b>n/2:
    b=n-b    
from functools import reduce
from fractions import Fraction
nca = (reduce(lambda x,y:x*y, (Fraction((n-i),(i+1)) for i in range(a)), 1) )
ncb = (reduce(lambda x,y:x*y, (Fraction((n-i),(i+1)) for i in range(b)), 1) )
print(int(2**n - 1 - nca - ncb)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math

def kumi (n, r):
  return math.factorial(n)/math.factorial(r)/math.factorial(n-r)
  
N,A,B = map(int, input().split())
ans = 0
X = 0
for i in range(1,N+1):
  if i == A or i == B:
    continue
  ans += kumi(N,i)
print(int(ans))

Submission status: Time Limit Exceeded

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

delta=1
for i in range(n):
    delta=delta*(n-i)/(i+1)
    if i!=a-1 and i!=b-1:
        comb=comb+delta

if comb<10**9+7:
    print(int(comb))
else:
    print(int(comb)%10**9+7)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, a, b = MAP()

# def c(n,k): 
#   return 1 if(k<=0 or n<=k) else ( c(n-1, k-1) + c(n-1, k) ) %4

# def make_comb_dp(n):
#     dp = [[0] * (n + 1) for i in range(n + 1)]
#     for i in range(n + 1):
#         dp[i][0] = 1
#         dp[i][i] = 1
#     for i in range(2, n + 1):
#         for j in range(1, i):
#             dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
#     return dp





# def c(n,k): 
#   return 1 if(k<=0 or n<=k) else c(n-1, k-1) + c(n-1, k)

# for i in range(10):
#   print([c(i,j) for j in range(i+1)])


MAX = 510000
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

# // テーブルを作る前処理
MOD = mod
# def COMinit():
#     fac[0] = 1
#     fac[1] = 1
#     finv[0] = 1
#     finv[1] = 1
#     inv[1] = 1
#     # for (i = 2; i < MAX; i++){
#     for i in range(2, MAX):
#         fac[i] = fac[i - 1] * i % MOD
#         inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD
#         finv[i] = finv[i - 1] * inv[i] % MOD
# print(fac)

# // 二項係数計算
def C(n, k):
    if (n < k):
        return 0
    if (n < 0 or k < 0):
        return 0
    else:
        # print(1)
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

# COMinit()

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
# def modinv(a, m):
#     g, x, y = egcd(a, m)
#     if g != 1:
#         raise Exception('modular inverse does not exist')
#     else:
#         return x % m

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

c = combination(n, a)
d = combination(n, b)
ans = (2 ** n - c - d -1) % mod
print(ans)






# exit()

# P = [0] * (n + 1)
# P[0]=1
# P[1]=1
#     # // 1を-1にすれば、差分のパスカル三角形になります。
# SIZE = n
# # for y=2;y<SIZE;y++
# for y in range(2, SIZE):
#     b=0
#     # for (r=y;r>0;r--:
#     for r in range(y, 0, -1):
#         P[r]=P[r-1]+b
#         b=P[r-1]
# print(P)


# exit()
# c = [[0] * (n+1) for i in range(n+1)]
# c[0][0] = 1
# for i in range(n):
#     for j in range(n):
#         tmp = c[i][j] % mod
#         c[i+1][j] += tmp
#         c[i+1][j+1] += tmp
# # print()
# # dp = make_comb_dp(n)
# # print(dp)
# print(c)
# soko = (sum(c[n]))
# # print(soko)
# ans = soko - 1 - c[n][a] - c[n][b]
# print(ans % mod)









# # def c(n,k): 
# #   return 1 if(k<=0 or n<=k) else c(n-1, k-1) + c(n-1, k)

# # for i in range(10):
# #   print([c(i,j) for j in range(i+1)])


# # MAX = 510000
# # fac = [0] * MAX
# # finv = [0] * MAX
# # inv = [0] * MAX

# # # // テーブルを作る前処理
# # MOD = mod
# # def COMinit():
# #     fac[0] = fac[1] = 1
# #     finv[0] = finv[1] = 1
# #     inv[1] = 1
# #     # for (i = 2; i < MAX; i++){
# #     for i in range(2, MAX):
# #         fac[i] = fac[i - 1] * i % MOD;
# #         inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
# #         finv[i] = finv[i - 1] * inv[i] % MOD

# # # // 二項係数計算
# # def C(n, k):
# #     if (n < k):
# #         return 0
# #     if (n < 0 or k < 0):
# #         return 0
# #     else:
# #         print(1)
# #         return fac[n] * (finv[k] * finv[n - k] % mod) % mod
# # print(C(173205, 141421))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

S = []
for i in range(1, n+1):
  S.append(i)

S.remove(a)
S.remove(b)

CS = 0

for r in S:
  c = factorial(n) / factorial(r) / factorial(n - r)
  CS += c

ans = int(CS % (19**9 + 7))

print(ans)

Submission status: Time Limit Exceeded

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

f = 1
for i in range(1, n+1):
  f *= i
  f %= mod
     
# n!^-1 の計算
inv = pow(f, mod - 2, mod)
# n!^-1 - 1!^-1 の計算
invs = {}
invs[n] = inv
for m in range(n, 1, -1):
    inv *= m
    inv %= mod
    invs[m - 1] = inv

memo = {}

def comb(n,k):
  if k==0 or k==n: return 1
  if n-k in memo:
    return memo[n-k]
  else:
    memo[k] = (f*invs[k]*invs[n-k])%mod
    return memo[k]

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

Submission status: Time Limit Exceeded

Solution code:
import math

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

ans = 0

p = 2


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


for i in range(int(math.sqrt(n))):
    p *= p % mod

if n % 2 == 1:
    p *= 2

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


print(int(ans % mod))

Submission status: Time Limit Exceeded

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

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

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

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

    return result

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

mod = 10 ** 9 + 7
ans = 2 ** n - 1

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

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
MAX_NUM = 10**9+1
MOD = 10**9+7

fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]

fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def combinations(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD


def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

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

X = combinations(n,a)
Y = combinations(n,b)
Z = power_func(2,n,MOD) - 1
print(Z - X - Y)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
#n種類,aとbが苦手
n,a,b = map(int,input().split())
array = [1]
tmp = array[0]
cnt = 0
for i in range(1,n+1,1):
    tmp *= i
    array.append(tmp)
for i in range(1,n+1,1):
    if i == a or i == b:
        continue
    cnt += (array[n]/array[n-i])/array[i]
print(int(cnt%(1000000000+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


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

tot = 2 ** n - 1
ans = tot - cmb(n, a) - cmb(n, b)
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,a,b= map(int,input().split())
from functools import reduce
from fractions import Fraction
nca = (reduce(lambda x,y:x*y, (Fraction((n-i),(i+1)) for i in range(a)), 1) )
ncb = (reduce(lambda x,y:x*y, (Fraction((n-i),(i+1)) for i in range(b)), 1) )
print(int(2**n - 1 - nca - ncb)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
MOD = 10 ** 9 + 7

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a):
    x = extgcd(a,MOD)[0]
    return (MOD+x%MOD)%MOD

input = sys.stdin.readline
n,a,b = map(int,input().split())
x1 = 1

a = min(a,n-a)
b = min(b,n-b)
if a > b:
    a,b = b,a

for i in range(n-a+1,n+1):
    x1 = x1 * i % MOD
for i in range(1,a+1):
    x1 = x1 * mod_inv(i)

x2 = x1
for i in range(n-b+1,n-a+1):
    x2 = x2 * i % MOD
for i in range(a+1,b+1):
    x2 = x2 * mod_inv(i)
    x2 = x2 % MOD

t = []
nn = n
while nn > 0:
    t.append(nn % 2)
    nn //= 2
x0 = 1
for i in range(len(t)):
    x0 = x0 ** 2
    x0 = x0 % MOD
    if t[len(t)-i-1] == 1:
        x0 *= 2
        x0 = x0 % MOD
print ((x0 - x1 - x2 - 1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
# 2020/02/22
# AtCoder Beginner Contest 156 - D

import math

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

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

# Calc
ans = (2 ** n - 1) % (10 ** 9 + 7) - combi(n, a) - combi(n, b)

# Output
print(ans)

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, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 8  # 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)

#print(cmb(n, r, p))


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

Submission status: Time Limit Exceeded

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

class remainder():
    def __init__(self, mod=(10**9 + 7)):
        self.mod = mod
    
    def sub(self, a, b):

        return (a + self.mod - b) % self.mod
    
    def mul(self, a, b):

        return ((a % self.mod) * (b % self.mod)) % self.mod

    def pow(self, a, b):
        bp = []
        #bp.append(1)
        bp.append(a)

        n = len(bin(b)) - 2
        for x in range(n):
            bp.append(bp[x]**2 % self.mod)

        res = 1
        for x in range(n):
            if b >> x & 1:
                res = (res * bp[x]) % self.mod
        
        return res

    def div(self, a, b):
        
        return self.mul(a, self.pow(b, self.mod - 2))

com = [0] * (B + 1)
com[0] = 1

re = remainder()

ans = re.pow(2, N) - 1
for x in range(1, B + 1):
    s = re.sub(N, x) + 1
    d = re.div(s, x)
    com[x] = re.mul(com[x - 1], d)

subA = com[A]
subB = com[B]

ans = re.sub(ans, subA)
ans = re.sub(ans, subB)

print(ans)

Submission status: Time Limit Exceeded

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

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

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
mod=10**9+7
      
def cmb(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

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

Submission status: Time Limit Exceeded

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

### baseを求める
def power_func(a,n,p):
    bi=str(format(n,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
            res=(res*a) %p
    return res

base = power_func(2, n, mod) - 1

### baseから引く
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

for t in [a, b]:
	base -= comb(n, t, mod)
print(base)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2000000)
input=sys.stdin.readline


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

mod = 10**9+7

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y/2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod


def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
def div(a, b):
    return mul(a, power(b, mod-2)) % mod


# def cmb(n,r):
#     res=1
#     for i in range(1,r+1):
#         res=res*div(n-i+1,i)%mod
#     return res%mod


cnt=(power(2,n)-1)%mod


res=1
c=min(a,b)
d=max(a,b)
for i in range(1,d+1):
    res=res*div(n-i+1,i)%mod
    if i==c:
        cnt=(cnt-res)%mod
cnt=(cnt-res)%mod


# cnt-=cmb(n,a)+cmb(n,b)
print(cnt)

Submission status: Time Limit Exceeded

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

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


for i in range(n):
  if i+1 == a or i+1 == b:
    pass
  else:
    ans += cmb(n,i+1)

print(ans)

Submission status: Time Limit Exceeded

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

def cmb(n, r):
    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 )

def pow_r(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return pow_r(x ** 2 % mod, n // 2)
    else: 
        return x * pow_r(x ** 2 % mod, (n - 1) // 2)

plus = pow_r(2, (n - 1))
sum = 2 * plus - 1 % mod

print(sum - cmb(n,a) % mod - cmb(n,b) % mod)

Submission status: Time Limit Exceeded

Solution code:
n,a,b = [int(x) for x in input().rstrip().split()]
l=[]
n1=1
st=1
ans=0
for i in range(1,n+1):
    n1=n1*(n-i+1)
    st=st*i
    ans1 = (n1//st)
    if i==a or i==b:
        l.append(n1//st)
        continue
    else:
        if n<(i/2):
            ans+=l[n-i]
        else:
            ans+=ans1
            l.append(ans1)

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

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
sys.setrecursionlimit(int(10**9))

mod = 10**9 + 7

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y/2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def fact(n):
    if n == 1: 
        return 1
    else:
        return (fact(n-1)*n)%mod

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

n, a, b = map(int, input().split())
now = 1
for i in range(a):
    now = (now*(n-i)*power(i+1,mod-2))%mod
cnka = now
for i in range(a,b):
    now = (now*(n-i)*power(i+1,mod-2))%mod
cnkb = now

ans = power(2, n)%mod - cnka - cnkb - 1
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
def modpow(a:int, p:int, mod:int)->int:
    if p==0: return 1
    if p%2==0:
        half = modpow(a, p//2, mod)
        return half*half % mod
    else:
        return a * modpow(a, p-1, mod) % 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

A = list(map(int, input().split()))
n = A[0]
a = A[1]
b = A[2]

tot = modpow(2, n, MOD)

tot = tot-1
tot -= cmb(n, a)
tot -= cmb(n, b)
tot = tot % MOD

print(tot)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce
n, a, b = map(int, input().split())

MAX_NUM = 10**9 + 1
MOD = 10**9+7

fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]

fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def combinations(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD

def pow_by_iter(a, x, n):
  acc = a
  for i in range(a, x):
    acc = (acc*a)%n
    return acc

ans = pow_by_iter(2, n, MOD)

ans = ans - (combinations(n, a) + combinations(n, b)) - 1
print(ans)

Submission status: Time Limit Exceeded

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

allComb = 2 ** N - 1

factA = 1
for indxA in range(2, a+1):
  factA = factA * indxA

factB = 1
for indxB in range(2, b+1):
  factB = factB * indxB

factNA = 1
for indxNA in range(0, a):
  factNA = factNA * (N - indxNA)

factNB = 1
for indxNB in range(0, b):
  factNB = factNB * (N - indxNB)

Ans = allComb - int(factNA / factA) - int(factNB / factB)
Ans = Ans % ((10**9) + 7)

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

def main():
  n,a,b=map(int,input().split())
  mod=10**9+7
  cmb_l=[1 for _ in range(b+1)]
  for i in range(b):
    cmb_l[i+1]=(cmb_l[i]*(n-i)%mod*mod_inv(i+1,mod))%mod

  x=cmb_l[a]
  y=cmb_l[b]
  return((2**n-x-y-1) % mod)
print(main())

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as fac


def binomial(x, y):
    try:
        binom = fac(x) // fac(y) // fac(x - y)
    except ValueError:
        binom = 0
    return binom

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

ans=2**n-1
    
ans_b=binomial(n, a)+binomial(n, b)

print(ans-ans_b)

Submission status: Time Limit Exceeded

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


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


total = pow_k(2, n) - 1

now = 1
div = 1
ans = 0
for i in range(max(a, b) + 1):
    now *= (n - i)
    div *= i + 1
    if i == a-1 or i == b-1:
        total -= now // div
print(total % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

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

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
x = []
for i in range(a):
  x.append(combinations_count(a,i))
g = sum(x)-combinations_count(a,b)-combinations_count(a,c)
g = g % (10**9 +7)
print(g)

Submission status: Time Limit Exceeded

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


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


total = pow_k(2, n) - 1

now = 1
div = 1
ans = 0
for i in range(max(a, b) + 1):
    now *= (n - i)
    div *= i + 1
    if i == a-1 or i == b-1:
        total -= now // div
print(total % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

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

    all = 2 ** n

    mod = 10**9+7 #出力の制限
    N = n
    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 combinations_count(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

    all -= combinations_count(n, a, mod)
    all -= combinations_count(n, b, mod)

    if n==2 and a != b:
        print(0)
        return 

    print(all - 1)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

f = 1
for i in range(1, n+1):
  f *= i
  f %= mod
     
# n!^-1 の計算
inv = pow(f, mod - 2, mod)
# n!^-1 - 1!^-1 の計算
invs = [1] * (n + 1)
invs[n] = inv
for m in range(n, 1, -1):
    inv *= m
    inv %= mod
    invs[m - 1] = inv

def comb(n,k):
  if k==0 or k==n: return 1
  return (f*invs[k]*invs[n-k])%mod

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

Submission status: Time Limit Exceeded

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

def comb(n,r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
print(
    (pow(2,n)-1
    - comb(n, a)
    - comb(n, b))%(10**9+7)   
    )

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce
mod = 10**9+7
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
n,a,b = map(int, input().split())
x = ((1<<n)-1)
x -= combinations_count(n,a)
x-= combinations_count(n,b)
print(x%mod)

Submission status: Time Limit Exceeded

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

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

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

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

    
#res = cmb(n,3,mod)
for i in range(1, n+1):
    res += cmb(n,i,mod)
res -= cmb(n,a,mod)
res -= cmb(n,b,mod)

print(res)

Submission status: Time Limit Exceeded

Solution code:
# n種類の花
# 苦手な数字a,b
n, a, b = map(int, input().split())

mod = 10**9+7

A = range(n)

pattern = []

for i in range(1 << len(A)):
    output = []
    for j in range(len(A)):
        if ((i >> j) & 1) == 1:
            output.append(A[j])
    if output != []:
        pattern.append(output)
    
def nCr(n,r):
    if n < 0 or r < 0 or n < r: return 0
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
  
    # 分子のn*(n-1)*...がr個分続くやつ
    numerator = [n-r+k+1 for k in range(r)]
    # 分母：r!=r*(r-1)*...*3*2の要素
    denominator = [k+1 for k in range(r)]
  
    # 分母の要素で割れる部分を割っていく部分
    for p in range(2, r+1):
        # 分母は1,2,3,...rのようになっており、1は意味がないのでスキップした形か
        pivot = denominator[p-1]
        if pivot > 1:
          # 分子のX番目と分母のX-offset番目が共通の約数を持つということだと思う。piv分ずれているのだから、pivの倍数というところか
            offset = (n-r) % p
            for k in range(p-1, r, p):
                # 約分できる要素について割る
                numerator[k - offset]  /= pivot
                denominator[k] /= pivot
        
    ret = 1
    for k in range(r):
        if numerator[k] > 1: ret *= int(numerator[k])
      
    return ret
print(len(pattern)-nCr(n,a)-nCr(n,b))

Submission status: Time Limit Exceeded

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

from operator import mul
from functools import reduce

p = 10**9+7

def prepare(n, MOD):

    # n! の計算
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs

ans = 0
fn, invs = prepare(n, p)
for i in range(1, n+1):
    if i == a or i == b:
        continue
    ans += fn * invs[i] * invs[n-i] % p

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
c = 1
d = 1
for i in range(1, n+1):
    c = c * i
ans = []
e = c
for i in range(1, n+1):
    d = d * i
    e = int(e / (n-i+1))
    #print(i, c, d, e)
    if i != a and i != b:
        ans.append(int(c/(d*e)))
#print(ans)
print(sum(ans)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
p = 10 ** 9 + 7
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

def pow_r(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return pow_r(x ** 2 % p, n // 2)
    else: 
        return x * pow_r(x ** 2 % p, (n - 1) // 2)

plus = pow_r(2, (n - 1))
sum = 2 * plus - 1 % p

print(sum - cmb(n,a) % p - cmb(n,b) % p)

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
I=10**9+7
l=[1,1]
p=2
for i in range(1,n):
  p=p*2%I
  m=[1]
  for j in range(i):
    m.append((l[j]+l[j+1])%I)
  l=m+[1]
print((p-l[a]-l[b]-1)%I)

Submission status: Time Limit Exceeded

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

sum = pow(2, N)

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

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

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

ax = cmb(N, a, mod)
bx = cmb(N, b, mod)

print((sum - ax - bx - 1)%(10**9+7))

Submission status: Time Limit Exceeded

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

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

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

print(2**n -cmb(n,a,p)-cmb(n,b,p)-1)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

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

n,a,b=list(map(int,input().split()))
p = 10 ** 9 + 7
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)

# 2**n-1
total = power_func(2,n,MOD)-1

print(total-cmb(n,a,MOD)-cmb(n,b,MOD))