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

def f(x, y):
    return math.factorial(x) // (math.factorial(x - y) * math.factorial(y))

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,a,b = map(int,input().split())
    MOD = 10**9 +7
    s = pow(2,n,MOD)-1
    P_ni = 1
    F_i = 1

    for i in range(1,b + 1):
        P_ni*=(n-i+1)%MOD
        F_i*= i % MOD
        if i == a or i == b:
            s-=P_ni*pow(F_i,MOD-2,MOD)
    print(s%MOD)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,a,b = map(int,input().split())
    MOD = 10**9 +7
    s = pow(2,n,MOD)-1
    P_ni = 1
    F_i = 1


    for i in range(1,b + 1):
        P_ni*=(n-i+1)%MOD
        F_i*= i % MOD
        if i == a or i == b:
            s-=P_ni*pow(F_i,MOD-2,MOD)



    print(s%MOD)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

def power_a(n,m,a=2):
    ret=1
    while n>0:
        if n%2==1:
            ret=ret*a%m
        a=a*a%m
        n>>=1
    return ret  


def comb_m(a):
    X=1
    Y=1
    for i in range(a):
        X*=(n-i)%m
        Y*=(i+1)%m
    return X*power_a(m-2,m,Y)%m   


varie=mod_m(power_a(n,m)-comb_m(a)-comb_m(b)-1)
          
    
print(int(varie))

Submission status: Time Limit Exceeded

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

    num = []
    den = []
    res = 1

    for k in range(0, r):
        num.append(n - r + k + 1)
        den.append(k + 1)

    for p in range(2, r + 1):
        piv = den[p - 1]
        if piv > 1:
            off = (n - r) % p
            for k in range((p - 1), r, p):
                num[k - off] /= piv
                den[k] /= piv

    for k in range(0, r):
        if num[k] > 1: res *= num[k]

    return res

nab = input().split()
n = int(nab[0])
a = int(nab[1])
b = int(nab[2])

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

print(round(ans))

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 power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, int(y/2)) ** 2 % mod
    else:
        return power(x, int((y-1)/2)) ** 2 * x % mod
ans = pow(2, n) - 1
    
a_max = 2 * 10 ** 5
# a, bの最大値+2
fact = [1] * (a_max + 2)
# 逆元
for i in range(1, a_max + 1):
    fact[i] = (fact[i-1] * i) % mod
# combination
def C(n, a):
    tmp = 1
    for i in range(n, n-a, -1):
        tmp = (tmp * i) % mod
    return tmp * power(fact[a], mod - 2)

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

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 power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, int(y/2)) ** 2 % mod
    else:
        return power(x, int((y-1)/2)) ** 2 * x % mod
    
a_max = 2 * 10 ** 5
# a, bの最大値+2
fact = [1] * (a_max + 2)
# 逆元
for i in range(1, a_max + 1):
    fact[i] = (fact[i-1] * i) % mod
ans = pow(2, n) - 1
# combination
def C(n, a):
    tmp = 1
    for i in range(n, n-a, -1):
        tmp = (tmp * i) % mod
    return tmp * power(fact[a], mod - 2)

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

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 power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, int(y/2)) ** 2 % mod
    else:
        return power(x, int((y-1)/2)) ** 2 * x % mod
    
a_max = 2 * 10 ** 5
# a, bの最大値+2
fact = [1] * (a_max + 2)
# 逆元
for i in range(1, a_max + 1):
    fact[i] = (fact[i-1] * i) % mod

# combination
def C(n, a):
    tmp = 1
    for i in range(n, n-a, -1):
        tmp = (tmp * i) % mod
    return tmp * power(fact[a], mod - 2)

print((pow(2, n) - 1 - C(n, a) - C(n, b)) % mod)

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
a = [a, n-a][a>n//2]
b = [b, n-b][b>n//2]

w = 1*(b!=0)
com = n
for i in range(1, n//2+1):
  w += com*((i!=a) + (i!=b) -(n%2==0 and i==n//2))
  com = com*(n-i)/(i+1)

print(int(w%(1e9+7)))

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

res = pow(2, n, MOD) - 1

dpa = {}
dpb = {}
factriala = 1
factrialb = n
for i in range(1, max(a, b)+1):
  if i in [a, b]:
    dpb[i] = factrialb
  factriala *= i
  factrialb *= n-i
  if i in [a, b]:
    dpa[i] = factriala

def ncr_count(r):
  return dpb[r] * pow(dpa[r], MOD-2, MOD)

res = res - ncr_count(a) - ncr_count(b)

print(res%MOD)

Submission status: Time Limit Exceeded

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

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

def resolve():
    ans = (pow(2, n) - modcmb(n, a, mod) - modcmb(n, b, mod) - 1) % mod
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,a,b = map(int,input().split())
    MOD = (10**9)+7
    s = pow(2,n,MOD)-1
    u = 1
    bb = 1


    for i in range(1,(max(a,b) + 1)):
        u*=(n-i+1)%MOD
        bb*= i % MOD
        if i == a or i == b:
            s-=u*pow(bb,MOD-2,MOD)



    print(s%MOD)
#


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

def ppow(a, b):
    a %= MOD
    res = 1
    while b != 0:
        if b & 1:
            res = (res * a) % MOD
        a = (a * a) % MOD
        b >>= 1
    return res

def nCr(n, r):
    res = 1
    for i in range(r):
        res = (res * (n-i)) % MOD
        res = (res * ppow(r-i, MOD-2)) % MOD
    return int(res)

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

U = (ppow(2, n) - 1) % MOD
U = (U - ((nCr(n, a) + nCr(n, b)) % MOD + MOD)) % MOD
print(U)

Submission status: Time Limit Exceeded

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

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

ans = (pow(2, n) - modcmb(n, a, mod) - modcmb(n, b, mod) - 1) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,a,b=mii()

if n==2 and a==1 and b==2:
    print(0)
    exit()

def p_f(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 mod_combination(n, k, mod):
    # nCk (mod m)
    def mod_permutation(n, k, mod):
        if n<=k:
            return 1
        else:
            return (n * mod_permutation(n-1,k,mod))%mod

    def mod_inv_permutation(k, mod):
        k, mod = int(k), int(mod)
        if k<=1:
            return 1
        else:
            return (pow(k,mod-2,mod) * mod_inv_permutation(k-1, mod))%mod

    return (mod_permutation(n,n-k,mod) * mod_inv_permutation(k, mod))%mod

ans=(p_f(2,n,mod) -1)%mod -mod_combination(n,a,mod)%mod - mod_combination(n,b,mod)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
from operator import mul
from functools import reduce
mod = 10**9+7
n,a,b = map(int, input().split())
def pow(x, n):
    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = ans*x
        x = x*x
        n = n >> 1
    return ans
total = pow(2,n)-1
total -= math.factorial(n) * pow(math.factorial(a), mod-2)
total -= math.factorial(n) * pow(math.factorial(b), mod-2)
print(total)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

mod=10**9+7

J=pow(2,n)%mod
def find_power(n,mod):
    # 0!からn!までのびっくりを出してくれる関数(ただし、modで割った値に対してである）
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist

def find_inv_power(n):
    #0!からn!までの逆元を素数10**9+7で割ったあまりリストを作る関数
    powlist=find_power(n,10**9+7)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist

C=find_inv_power(2*10**5+100)
if  True:
    c=1
    for i in range(a):
        c*=(n-i)
        c=c%mod
    c=c*C[a]
    c=c%mod
    d=1
    for i in range(b):
        d*=(n-i)
        d=d%mod
    d=d%mod
    d=d*C[b]
    print((J-c-d-1)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,a,b=mii()

if n==2 and a==1 and b==2:
    print(0)
    exit()

#ncrの場合
# nCr % mod と同等
N=100
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
#テーブル作成
for j in range( 2, N + 1 ):
    g1.append( ( g1[-1] * j ) % mod )
    inverse.append( ( -inverse[mod % j] * (mod//j) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
#nCrとmodを入力
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
def p_f(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 mod_combination(n, k, mod):
    # nCk (mod m)
    def mod_permutation(n, k, mod):
        if n<=k:
            return 1
        else:
            return (n * mod_permutation(n-1,k,mod))%mod

    def mod_inv_permutation(k, mod):
        k, mod = int(k), int(mod)
        if k<=1:
            return 1
        else:
            return (pow(k,mod-2,mod) * mod_inv_permutation(k-1, mod))%mod

    return (mod_permutation(n,n-k,mod) * mod_inv_permutation(k, mod))%mod

ans=(p_f(2,n,mod) -1)%mod -mod_combination(n,a,mod)%mod - mod_combination(n,b,mod)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import math

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

 
def comb(n,k,mod):
  """power_funcを用いて(nCk) mod p を求める"""

  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=math.factorial(n) %mod
  b=math.factorial(k) %mod
  c=math.factorial(n-k) %mod
  return (a*pow(b,mod-2,mod)*pow(c,mod-2,mod))%mod

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
print((pow(2,n,mod)- 1 - comb(n,a,mod) - comb(n,b,mod))%mod)
#2**n - 1 -nCa -nCb

Submission status: Time Limit Exceeded

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

mod=10**9+7

J=pow(2,n)%mod
def find_power(n,mod):
    # 0!からn!までのびっくりを出してくれる関数(ただし、modで割った値に対してである）
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist

def find_inv_power(n):
    #0!からn!までの逆元を素数10**9+7で割ったあまりリストを作る関数
    powlist=find_power(n,10**9+7)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist

C=find_inv_power(2*10**5+100)
if  True:
    c=1
    for i in range(a):
        c*=(n-i)
        c=c%mod
    c=c*C[a]
    c=c%mod
    d=1
    for i in range(b):
        d*=(n-i)
        d=d%mod
    d=d%mod
    d=d*C[b]
    print((J-c-d-1)%mod)

Submission status: Time Limit Exceeded

Solution code:
import math


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

res = 2 ** n - 1

dpa = {}
dpb = {}
factriala = 1
factrialb = n
for i in range(1, max(a, b)+1):
  if i in [a, b]:
    dpb[i] = factrialb
  factriala *= i
  factrialb *= n-i
  if i in [a, b]:
    dpa[i] = factriala

def ncr_count(r):
  return dpb[r] // dpa[r]

res = res - ncr_count(a) - ncr_count(b)

print(res%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

input = sys.stdin.readline

div = 10**9 + 7


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


def main():
    n, a, b = map(int, input().split())
    score = 2**n-1
    score -= combination(n, a)
    score -= combination(n, b)
    print(score % div)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

number = input().split(" ")
N = int(number[0])
a = int(number[1])
b = int(number[2])
ans = 0

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

for i in range(1,a):
    ans += combinations_count(N, int(i))
for i in range(a+1,b):
    ans += combinations_count(N, int(i))
for i in range(b+1,N+1):
    ans += combinations_count(N, int(i))

Ans = ans % (1000000007)
print(Ans)

Submission status: Time Limit Exceeded

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

from math import factorial

A = factorial(n) / factorial(a) / factorial(n - a)
B = factorial(n) / factorial(b) / factorial(n - b)

print( int(pow(2,n)-A-B-1)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

def ncr(n, r):
    a = 1
    b = 1
    for i in range(r):
        # a = (a * (n - i) % MOD)
        # b = (b * (r - i) % MOD)

        a *= ((n - i) % MOD)
        b *= ((r - i) % MOD)

    return a * pow(b, MOD - 2, MOD) % MOD

N, A, B = MI()

s = pow(2, N, MOD) - 1
ab = (ncr(N, A) + ncr(N, B)) % MOD

print((s - ab)  % MOD)

Submission status: Time Limit Exceeded

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

from math import factorial

A = factorial(n) / factorial(a) / factorial(n - a)
B = factorial(n) / factorial(b) / factorial(n - b)

print( int((2**n-A-B-1)%(10**9+7)))

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7
k = max(a, b)

#com = [1] * (k + 1)
#for i in range(1, k + 1):
#    com[i] = int(com[i-1] * (N - i + 1) / i) % MOD

def com(n, r):
    numer = 1
    denom = 1
    for i in range(1, r + 1):
        numer *= (n - i + 1) % MOD
        denom *= i % MOD
    return numer // denom 


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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

def ncr(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i) % MOD
        b *= (i + 1) % MOD
    
    return a * pow(b, MOD - 2, MOD) % MOD

N, A, B = MI()

s = pow(2, N, MOD) - 1
ab = (ncr(N, A) + ncr(N, B)) % MOD

print((s - ab)  % MOD)

Submission status: Time Limit Exceeded

Solution code:
N, a, b = map(int, input().split())
 
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
mod = 10**9+7 #出力の制限
X = 10**9
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
 
for i in range( 2, X + 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((pow(2, N) - ax - bx - 1)%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())
sa = cmb(N, A)
sb = cmb(N, B)

print((2**N - 1 - sa - sb) % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
#-----combination計算部分------
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

# スペース区切りの整数入力
NN,A,B = map(int, input().split())

res = 2 ** NN - 1
res -= cmb(NN,A)
res -= cmb(NN,B)

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb
n, a, b = (int(i) for i in input().split())
ans = 2 ** n -1
comb_a = comb(n,a,exact=True)
comb_b = comb(n,b,exact=True)
ans -= (comb_a + comb_b)
if ans <= 0: ans = 0
print (int(ans%(10**9+7)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
mod = p = 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]]

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

n, a, b = map(int, input().split())
nCa= 1
nCb= 1
for i in range(b):
    nCb = (nCb%p * (n-i)%p)%p
    nCb = nCb * mod_inv(i+1, p)
    if i+1 == a:
        nCa = nCb

ans = 2**n - 1- nCa%p - nCb%p
if ans < 0:
    print(0)
else:
    print(int(ans%p))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

def ncr(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i) % MOD
        b *= (r - i) % MOD
    
    return a // b % MOD

N, A, B = MI()

s = pow(2, N, MOD) - 1



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

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

Submission status: Time Limit Exceeded

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

def cmb(n, r, mod):
    r = min(n-r, r)
    if r == 0:
        return 1
    over, under = 1, 1
    for i in range(1, r+1):
        over = over * (n-i+1) % mod
        under = under * i % mod
    inv = pow(under, mod-2, mod)
    return over * inv % mod

res -= cmb(n,a,mod)
res -= cmb(n,b,mod)

print(res % mod)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

def C(n, r):
  if r == 1:
    return n
  nume = reduce(mul, range(n, n - r, -1))
  deno = reduce(mul, range(1, r+1))
  return nume // deno

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

mod = 10 ** 9 + 7

if n == 2:
   print(0)
   exit()
                
S = pow(2, n, mod)
A = C(n, a) % mod
B = C(n, b) % mod

print(S - A - B - 1)

Submission status: Time Limit Exceeded

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

MOD = 1000000007  # type: int

def fast_pow(a,b):
    if b == 0:
        return 1
    elif b % 2 == 0:
        d = fast_pow(a, b // 2)
        return (d * d) % MOD
    else:
        return (a * fast_pow(a, b - 1)) % MOD

def cmb(n, r):
    result = 1
    for i in range(n-r+1,n+1):
        result=result*i%MOD
    for i in range(2,r+1):
        result=result*fast_pow(i,MOD-2)%MOD
    return result

def solve(n: int, a: int, b: int):
    print(str((fast_pow(2,n)-cmb(n,a)-cmb(n,b)-1)%MOD))


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = int(next(tokens))  # type: int
    b = int(next(tokens))  # type: int
    solve(n, a, b)

if __name__ == '__main__':
    main()

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
	
	num = [n - r + k + 1 for k in range(r)] #numerator(分子)
	den = [k + 1 for k in range(r)] #denominator(分母)
	
	for p in range(2, r + 1):
		pivot = den[p - 1]
		if pivot > 1:
			offset = (n - r) % p
			for k in range(p - 1, r, p):
				num[k - offset] /= pivot
				den[k] /= pivot
	
	result = 1
	for k in range(r):
		if num[k] > 1:
			result *= int(num[k])
			result = result % mod
	
	return result

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:
def comb(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
MAXN=10**9+10
g1=[1, 1]
g2=[1, 1]
inverse=[0, 1]

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

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

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

N, A, B=map(int, input().split())
ans=pow_by_binary_exponentiation(2, N)-comb(N, A)-comb(N, B)-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
mod=10**9+7
bunbo=1
bunshi=1
for i in range(1,max(a+1, b+1)):
    bunbo*=i
    bunshi*=n-i+1
    bunshi%=mod
    bunbo%=mod
    if i==a:
        comba=bunshi*(pow(bunbo,mod-2,mod))
    if i==b:
        combb=bunshi*(pow(bunbo,mod-2,mod))
print((2**n-1-comba-combb)%mod)

Submission status: Time Limit Exceeded

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

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


c = pow(2,n,mod)
c -= 1
c -= ( factorial(n) * modinv(factorial(a)) )%mod * modinv(factorial(n-a)) % mod
c -= ( factorial(n) * modinv(factorial(b)) )%mod * modinv(factorial(n-b)) % mod
print(c%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
n,a,b= map(int, input().split())
mod = 10 ** 9 + 7
def power_func(a,n,mod):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res


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


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=(power_func(2,n,mod)-1-cmb(n,a,mod)-cmb(n,b,mod))%mod
print(ans)