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:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
#import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  n, a, b = map(int, readline().split())
  fact = [1, 1]  # fact[n] = (n! mod p)
  factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
  inv = [0, 1]  # factinv 計算用
  
  for i in range(2, n + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)
  
  def cmb(n, r, mod):
    if (r < 0) or (n < r):
      return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod
  
  if n==2:
    print(0)
  else:
    total = pow(2, n, MOD) %MOD
    nca = cmb(n,a,MOD)
    ncb = cmb(n,b,MOD)
    ans = (total-nca-ncb-1)%MOD
    print(int(ans))
  
  
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

#制限なしで全ての花束の作り方
wa = pow(2, n, 10 ** 9 + 7) - 1

#a本の花束の作り方
#val1 = comb(n, a, exact=True)
#val2 = comb(n, b, exact = True)

x = 1
y = 1
for i in range(a):
    x *= n-i % (10 ** 9 + 7)
    y *= i+1 % (10 ** 9 + 7)
val1 = x * pow(y, 10 ** 9 + 7 - 2, 10 ** 9 + 7) % (10 ** 9 + 7)

x = 1
y = 1
for i in range(b):
    x *= n-i % (10 ** 9 + 7)
    y *= i+1 % (10 ** 9 + 7)

val2 = x * pow(y, 10 ** 9 + 7 - 2, 10 ** 9 + 7) % (10 ** 9 + 7)
print(wa - val1 - val2)

Submission status: Time Limit Exceeded

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

#制限なしで全ての花束の作り方
wa = pow(2, n, 10 ** 9 + 7) - 1

#a本の花束の作り方
#val1 = comb(n, a, exact=True)
#val2 = comb(n, b, exact = True)

x = 1
y = 1
for i in range(a):
    x *= n-i % (10 ** 9 + 7)
    y *= i+1 % (10 ** 9 + 7)
val1 = x * pow(y, 10 ** 9 + 7 - 2, 10 ** 9 + 7)

x = 1
y = 1
for i in range(b):
    x *= n-i % (10 ** 9 + 7)
    y *= i+1 % (10 ** 9 + 7)

val2 = x * pow(y, 10 ** 9 + 7 - 2, 10 ** 9 + 7)  
ans = wa - val1 -val2
for i in range(10000):
    if ans < 0:
        ans += 10 ** 9 + 7
    else:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#TLE

#half_expo(a, n, mod) = (a**n) % mod
#繰り返し二乗法
def pow(a, n, mod):
    ans = 1
    while n > 0:
        if bin(n & 1) == bin(1):
            ans = ans * a
            ans %= mod
        a = a * a
        n = n >> 1
    return ans

#comb_mod(n, r, mod) = nCr % mod
def comb_mod(n, r, mod):
    ans = 1
    if r <= n/2:
        for i in range(n-r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    else:
        for i in range(r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, n-r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    return ans

n, a, b = map(int, input().split())
ans = pow(2, n, 10**9+7) - comb_mod(n, a, 10**9+7) - comb_mod(n, b, 10**9+7) - 1
if ans < 0:
    ans += 10**9 + 7
if ans < 0:
    ans += 10**9 + 7

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
import math
s=0
def comb(x,y):
  return (math.factorial(x)//(math.factorial(y)*math.factorial(x-y)))
for i in range(1,n+1):
  if i==a or i==b:
    s=s
  else:
    s=s+comb(n,i)
print(s%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
#TLE

#half_expo(a, n, mod) = (a**n) % mod
#二分累乗法
def half_expo_mod(a, n, mod):
    nbin = tuple(bin(n))
    nbin = nbin[3:]
    ans = a
    for j in nbin:
        if j == '0':
            ans **= 2
        else:
            ans = (ans ** 2) * a
        ans %= mod
    return ans

#comb_mod(n, r, mod) = nCr % mod
def comb_mod(n, r, mod):
    ans = 1
    if r <= n/2:
        for i in range(n-r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, r+1):
            ans *= half_expo_mod(i, mod-2, mod)
            ans %= mod
    else:
        for i in range(r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, n-r+1):
            ans *= half_expo_mod(i, mod-2, mod)
            ans %= mod
    return ans

n, a, b = map(int, input().split())
ans = half_expo_mod(2, n, 10**9+7) - comb_mod(n, a, 10**9+7) - comb_mod(n, b, 10**9+7) - 1
if ans < 0:
    ans += 10**9 + 7
if ans < 0:
    ans += 10**9 + 7

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
#TLE

#half_expo(a, n, mod) = (a**n) % mod
#二分累乗法
def half_expo_mod(a, n, mod):
    nbin = list(bin(n))
    nbin = nbin[3:]
    ans = a
    for j in nbin:
        if j == '0':
            ans **= 2
        else:
            ans = (ans ** 2) * a
        ans %= mod
    return ans

#comb_mod(n, r, mod) = nCr % mod
def comb_mod(n, r, mod):
    ans = 1
    if r <= n/2:
        for i in range(n-r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, r+1):
            ans *= half_expo_mod(i, mod-2, mod)
            ans %= mod
    else:
        for i in range(r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, n-r+1):
            ans *= half_expo_mod(i, mod-2, mod)
            ans %= mod
    return ans

n, a, b = map(int, input().split())
ans = half_expo_mod(2, n, 10**9+7) - comb_mod(n, a, 10**9+7) - comb_mod(n, b, 10**9+7) - 1
if ans < 0:
    ans += 10**9 + 7
if ans < 0:
    ans += 10**9 + 7

print(int(ans))

Submission status: Time Limit Exceeded

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

#half_expo(a, n, mod) = (a**n) % mod
#二分累乗法
def half_expo_mod(a, n, mod):
    nbin = list(bin(n))
    nbin = nbin[3:]
    ans = a
    for j in nbin:
        if j == '0':
            ans **= 2
        else:
            ans = (ans ** 2) * a
        ans %= mod
    if n == 0: #n=0の時の処理
        ans = 1
    return ans

#comb_mod(n, r, mod) = nCr % mod
def comb_mod(n, r, mod):
    ans = 1
    if r <= n/2:
        for i in range(n-r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, r+1):
            ans *= half_expo_mod(i, mod-2, mod)
            ans %= mod
    else:
        for i in range(r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, n-r+1):
            ans *= half_expo_mod(i, mod-2, mod)
            ans %= mod
    return ans

ans = half_expo_mod(2, n, 10**9+7) - comb_mod(n, a, 10**9+7) - comb_mod(n, b, 10**9+7) - 1
if ans < 0:
    ans += 10**9 + 7
if ans < 0:
    ans += 10**9 + 7

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, p):
    r = min(r, n - r)
    res = 1
    for i in range(r):
        res *= pow(i+1, p-2, p)  # 分母の逆元
        res *= (n-i) % p  # 分子
    return res % p

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

Submission status: Time Limit Exceeded

Solution code:
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 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


n, a, b = map(int, input().split())
print(((2**n-1)%p - cmb(n, a, p) - cmb(n, b, p))%p)

Submission status: Time Limit Exceeded

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

M = pow(2, N,m)

m = 10**9+7
#互いに素な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]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
  

res = 1
for i in range(N-a+1,N+1):
    res = res*i%m
for i in range(1,a+1):
    res = res*mod_inv(i,m)%m

rs = 1
for i in range(N-b+1,N+1):
    rs = rs*i%m
for i in range(1,b+1):
    rs = rs*mod_inv(i,m)%m

print((M-1-res-rs)%m)

Submission status: Time Limit Exceeded

Solution code:
N,a,b=map(int,input().split())
m = 10**9+7
def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
            ans %= m
        x *= x
        n >>= 1
    return ans

M = pow(2, N)%m

m = 10**9+7
#互いに素な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]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
  

res = 1
for i in range(N-a+1,N+1):
    res = res*i%m
for i in range(1,a+1):
    res = res*mod_inv(i,m)%m

rs = 1
for i in range(N-b+1,N+1):
    rs = rs*i%m
for i in range(1,b+1):
    rs = rs*mod_inv(i,m)%m

print(M-1-res-rs)

Submission status: Time Limit Exceeded

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

M = pow(2, N)%m

m = 10**9+7
#互いに素な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]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
 
def nCr(n,r):
    if r*2>n:
        return nCr(n,n-r)
    else:
        a = b = 1
        for i in range(r):
            a = a * (n - i) % m
            b = b * (r - i) % m
        return (a * pow(b,m-2,m)) % m
 
ans = M - 1 - nCr(N,a) - nCr(N,b)
print(ans%m)

Submission status: Time Limit Exceeded

Solution code:
N,a,b=map(int,input().split())
m = 10**9+7
def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

M = pow(2, N)%m

m = 10**9+7
#互いに素な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]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
  

res = 1
for i in range(N-a+1,N+1):
    res = res*i%m
for i in range(1,a+1):
    res = res*mod_inv(i,m)%m

rs = 1
for i in range(N-b+1,N+1):
    rs = rs*i%m
for i in range(1,b+1):
    rs = rs*mod_inv(i,m)%m

print(M-1-res-rs)

Submission status: Time Limit Exceeded

Solution code:
N,a,b=map(int,input().split())
m = 10**9+7
def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

M = pow(2, N)%m

#互いに素な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]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
  
res = 1
for i in range(1,N+1):
    res = res*i%m
for i in range(1,N-a+1):
    res = res*mod_inv(i,m)%m
for i in range(1,a+1):
    res = res*mod_inv(i,m)%m

rs = 1
for i in range(1,N+1):
    rs = rs*i%m
for i in range(1,N-b+1):
    rs = rs*mod_inv(i,m)%m
for i in range(1,b+1):
    rs = rs*mod_inv(i,m)%m

print(M-1-res-rs)

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

M = pow(2, N)

c=1
d=1
for i in range(a):
  c*=(N-i)
  d*=i+1

e=1
f=1
for i in range(b):
  e*=(N-i)
  f*=i+1

print((M-1-c//d-e//f)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

p = combinations_count(n, a)
q = combinations_count(n, b)

print((2**n-1-p-q)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

p = combinations_count(n, a)
q = combinations_count(n, b)

print(2**n-1-p-q)

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
ncpre=1
MOD=1000000007
ans=0
for i in range(1,n+1):
    nci=ncpre*(n-(i-1))//i
    ncpre=nci
    if(i!=a and i!=b):
        ans = (ans + nci)%MOD
print(ans)

Submission status: Time Limit Exceeded

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

#　ans = 2**n
na = list(bin(n))
nb = na[3:]

ans = 2

for c in nb:
    if c == '0':
        ans **= 2
    else:
        ans = (ans ** 2) * 2

if n == 0:
    ans = 1

#　数え過ぎたものを引く
def comb(n, r):
    m = 1
    for i in range(n-r+1, n+1):
        m *= i
    for i in range(1, r+1):
        m //= i
    return m
ans -= comb(n, a) + comb(n, b) + 1

print(int(ans % (1000000007)))

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
    
n,a,b = map(int,input().split())

res = pow(2,n,10**9+7)
res -= 1


res -= combinations_count(n,a)
res %= 10**9+7

res -= combinations_count(n ,b)
res %= 10**9+7

print(res)

Submission status: Time Limit Exceeded

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

#　ans = 2**n
n2 = n
ans = 1
rou = 0
while n2 >= 1:
    n2, rem = divmod(n2, 2)
    if rem == 1:
        ans *= 2**(2**rou)
    rou += 1

#　数え過ぎたものを引く
def comb(n, r):
    m = 1
    for i in range(n-r+1, n+1):
        m *= i
    for i in range(1, r+1):
        m //= i
    return m
ans -= comb(n, a) + comb(n, b) + 1


print(int(ans % (1000000007)))

Submission status: Time Limit Exceeded

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

ans = 2**n
#n2 = n
#ans = 1
#rou = 0
#while n2 >= 1:
    #n2, rem = divmod(n2, 2)
    #if rem == 1:
        #ans *= 2**(2**rou)
    #rou += 1

#　数え過ぎたものを引く
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

ans -= comb(n, a) + comb(n, b) + 1


print(int(ans % (1000000007)))

Submission status: Time Limit Exceeded

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

#　ans = 2**n
n2 = n
ans = 1
rou = 0
while n2 >= 1:
    n2, rem = divmod(n2, 2)
    if rem == 1:
        ans *= 2**(2**rou)
    rou += 1

#　数え過ぎたものを引く
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

ans -= comb(n, a) + comb(n, b) + 1


print(int(ans % (1000000007)))

Submission status: Time Limit Exceeded

Solution code:
n,a,b = map(int, input().split())
M = 10**9 + 7
from math import factorial
from functools import reduce
A = pow(2,n,M) - 1
B = reduce(lambda x, y: x*y, [n-i for i in range(a)]) * pow(factorial(a), M - 2, M) % M
C = reduce(lambda x, y: x*y, [n-i for i in range(b)]) * pow(factorial(b), M - 2, M) % M
print((A-B-C)%M)

Submission status: Time Limit Exceeded

Solution code:
def ncr(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 = map(int, input().split())
p = 10 ** 9 + 7
"N = 10 ** 6  # N は必要分だけ用意する"
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)

 
al = 2**N -1
acr = ncr(N, a, p)
bcr = ncr(N, b, p)
print(al-acr-bcr)

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb
n, a, b = map(int, input().split())

combination = 0
for i in range(1, n + 1):
    if i == a or i == b:
        continue
    combination += comb(n, i, exact=True)


ans = combination % (10**9 + 7)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

n, a, b = map(int, input().split())
count = 0
mod = (10 ^ 9 + 7)
for i in range(n):  # i+1本の花束の組み合わせ
    # print("aaa")
    if i + 1 == a or i + 1 == b:
        # print("no")
        continue
    count += (math.factorial(n) % mod) / (math.factorial(i + 1) % mod) / (math.factorial(n - (i + 1)) % mod)
    # print(count_j)
print(int(count % (10 ^ 9 + 7)))

Submission status: Time Limit Exceeded

Solution code:
import math
n,a,b=map(int, input().split())
count=0
for i in range(n):#i+1本の花束の組み合わせ
    # print(i)
    if i+1==a or i+1==b:
        continue
    # print(i)
    count += math.factorial(n)/math.factorial(i+1)/math.factorial(n-(i+1))
print(int(count))

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):
  y = 1
  p = mod - 2
  base = x
  while p != 0:
    if p % 2 == 1:
      y *= base
      y %= mod
    base *= base
    base %= mod
    p //= 2
  return y
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
S = [inved(i+1) for i in range(b)]
A = doubling(2, n)
A = (A - 1) % mod
proda, prodb = 1, 1
for i in range(b):
  proda *= ((n - i) * S[i]) % mod
  proda %= mod
  if i == a - 1:
    A -= proda
    A %= mod
print((A - proda) % 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):
  y = 1
  p = mod - 2
  base = x
  while p != 0:
    if p % 2 == 1:
      y *= base
      y %= mod
    base *= base
    base %= mod
    p //= 2
  return y
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
S = [inved(i+1) for i in range(b)]
A = doubling(2, n)
A = (A - 1) % mod
proda, prodb = 1, 1
for i in range(a):
  proda *= ((n - i) * S[i]) % mod
  proda %= mod
for i in range(b):
  prodb *= ((n - i) * S[i]) % mod
  prodb %= mod
print((A - proda - prodb) % mod)

Submission status: Time Limit Exceeded

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

def choose(n, m, mod):
    x, y = 1, 1
    for i in range(m):
        x *= (n - i) % mod
        y *= (i + 1) % mod
    return x * mod_pow(y, mod - 2, mod) % mod

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

ans = (mod_pow(2, n, mod) - 1 - choose(n, a, mod) - choose(n, b, mod)) % mod
print(ans)

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7
#a本、b本の制限を無視すると、2^n - 1の選び方が存在する。
ans = pow(2, n, mod) - 1 % mod

def choose(n, a):
    x = y = 1
    for i in range(a):
        y *= (i + 1) % mod
        x *= (n - i) % mod
    return x * pow(y, mod - 2, mod) % mod 
#上記で求めた値から、a本を選んだ時とb本を選んだ時の組み合わせ数を引く
ans -= choose(n, a)
ans -= choose(n, b)

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
# problem D

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 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans = 2**n - (cmb(n,a,p)+cmb(n,b,p)) -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a,b = map(int,input().split())
mod = 10**9+7
def combination(N,K):
    bunsi = 1
    bunbo = 1
    for i in range(K):
        bunsi = bunsi*(N-i)%mod
        bunbo = bunbo*(i+1)%mod
    return bunsi*pow(bunbo,mod-2,mod)%mod
all_num = (2**n-1)%mod
ans = all_num-combination(n,a)-combination(n,b)
print(ans%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

N,a,b = map(int,input().split())
Sum = pow(2, N, 10**9+7)-1
MOD = 10**9 + 7
def comb(n,k, mod):
    m = 1#分子
    l = 1#bunnbo
    for i in range(k):
        m *= (n-i)
        l *= (i + 1)
        m %= mod
    return m * pow(l, mod-2, mod) % mod

Sum = pow(2, N, 10**9+7) -1 - comb(N, a, MOD) - comb(N, b, MOD)
Sum = Sum % (10**9+7)
print(Sum)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,a,b = map(int,input().split())
print((2**n-len(list(itertools.combinations(range(n),a)))-len(list(itertools.combinations(range(n),b)))-1)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)

def C(n,r):
    return P(n, r)//math.factorial(r)

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

Submission status: Time Limit Exceeded

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

comb_all = (2**n-1)
comb_a = math.factorial(n) // (math.factorial(n - a) * math.factorial(a))
comb_b = math.factorial(n) // (math.factorial(n - b) * math.factorial(b))
temp = comb_all - (comb_a + comb_b)
print(temp%1000000007)

Submission status: Time Limit Exceeded

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

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

def cmbmod(n, r,mod):
  a=mod-2
  b=1
  for i in range(r):
   b*=(i+1)
   b%=mod
  ans1 = 1
  while a:
      if a % 2:
          ans1 *= b
          ans1 %= mod
      b *= b
      n >>= 1
  ans2 = 1
  for i in range(n-r):
   ans2 *= (i+r+1)
   ans2%=mod
  return (ans1*ans2)%mod

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
all_patern = 2 ** n - 1
minus_a = combination(n, a)
minus_b = combination(n, b)
print((all_patern % mod - minus_a - minus_b) % mod)

Submission status: Time Limit Exceeded

Solution code:
import math

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

factional_n   = math.factorial(n)
factional_nma = math.factorial(n-a)
factional_nmb = math.factorial(n-b)
factional_a   = math.factorial(a)
factional_b   = math.factorial(b)

tmp = (pow(2,n)-1) - ( factional_n//(factional_a*factional_nma) + factional_n//(factional_b*factional_nmb))
print(tmp%(pow(10,9)+7))

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
def fac(N):
  s=1
  while N>=1:
    s=s*N
    N=N-1
  return (s)
def com(m,n):
  k=int(fac(m)/(fac(m-n)*fac(n)))
  return (k)
k=2**n-com(n,a)-com(n,b)-1
print (k)

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
def fac(N):
  s=1
  while N>=1:
    s=s*N
    N=N-1
  return (s)
def com(m,n):
  k=int(fac(m)/(fac(m-n)*fac(n)))
  return (k)
S=0
for i in range(1,n+1):
  if i!=a and i!=b:
    S=S+com(n,i)
print(S)

Submission status: Time Limit Exceeded

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

def abp(a, b, p):
    if b == 0:
        return 1
    if b % 2 == 0:
        tmp = abp(a, b // 2, p)
        return (tmp * tmp) % p
    if b % 2 == 1:
        return (a * abp(a, b - 1, p)) % p
 
def nCr(n, r, p):
    total = 1
    for i in range(r):
        total *= (n - i) * abp(r - i, p - 2, p)
        total %= p
    return total

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

Submission status: Time Limit Exceeded

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


def kaijyou(k):
  N=1
  for i in range(k,0,-1):
    N*=i
  return N

def combinations(n,r):
  return int(kaijyou(n)/(kaijyou(r)*kaijyou(n-r)))


s = 2**n - 1
P = 10**9 + 7

A=combinations(n,a)
B=combinations(n,b)

H = (s-A-B) % P
print(H)

Submission status: Time Limit Exceeded

Solution code:
import math

n, a, b = (int(x) for x in input().split(' '))

#二項係数の総和を求め、そこからaの時、bの時、をそれぞれ差分する
ans = 0
ans = 2 ** n -1 #最後の-1は「一つも選ばないパターン」
ans -= math.factorial(n) / (math.factorial(a) * math.factorial(n-a))
ans -= math.factorial(n) / (math.factorial(b) * math.factorial(n-b))

#出力
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
inp = [int(i) for i in input().split()]
n = inp[0]
a = inp[1]
b = inp[2]

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 )

A = cmb(n,a,mod)
B = cmb(n,b,mod)
ans = 2**n-1-A-B
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n,a,b = [int(i) for i in input().split()]
mod = 10**9+7
 
def mpow(a,n):
  if n == 0:
    return 1
  x = mpow(a,n//2)
  ans = x*x%mod
  if n%2==1:
    ans *= a
  return ans
  
def comb(n,k):
  ans = 1
  for i in range(k):
    ans = ans*(n-i)%mod
  for i in range(1,k+1):
    ans = ans*mpow(i,mod-2)%mod
  return ans
 
print((mpow(2,n)-1-comb(n,a)-comb(n,b))%mod)
# print(comb(n,a))

Submission status: Time Limit Exceeded

Solution code:
import math


def comb(n, r, mod):
    # calculates C(n,r) mod p (assuming mod is prime).
    nc = n
    for rc in range(1, r):
        nc -= 1
        n *= nc % mod
        r *= rc % mod

    nCr = n*pow(r, mod - 2, mod) % mod
    return nCr


def solve():
    n, a, b = list(map(int, input().split()))
    mod = int(math.pow(10, 9) + 7)

    total = pow(2, n, mod) - 1
    ac = comb(n, a, mod)
    bc = comb(n, b, mod)
    ans = int(total - ac - bc) % mod

    print(ans)


# Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

def permutation(n,r):
    perm = 1
    for integer in range(n-r+1, n+1):
        perm *= integer
    return perm

def RepeatSquaring(x, n, m):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = (ans*x)%m
    x = (x*x)%m
    n = n >> 1
  return ans

def cmb(n, r, mod):
    nume = permutation(n,r)
    deno = permutation(r,r)
    return (nume * RepeatSquaring(deno, mod-2, mod)) % mod

ans = RepeatSquaring(2, n, mod) - 1 - cmb(n, a, mod) - cmb(n, b, mod)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

ans=2**N-1

A=combinations_count(N, a)
B=combinations_count(N, b)

ans=(ans-A-B)%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

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

M = 10**9 + 7


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

    
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

all_pattern = my_pow(2, n)
dislike = cmb(n, a) + cmb(n, b)
dislike = dislike % M


print( (all_pattern - dislike - 1) )