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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def power(val, n, mod):
    ret = 1
    while n:
        if n & 1:
            ret = (ret * val) % mod
        val = (val * val) % mod
        n = n >> 1
    return ret


def cmb(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 = result % mod

    return result % mod


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

pow_val = power(2, n, 1000000007)
ans = pow_val - 1 - cmb(n, a, 1000000007) - cmb(n, b, 1000000007)

if ans >= 0:
    print(ans)
else:
    print(ans + 1000000007)

Submission status: Wrong Answer

Solution code:
def fact(n):
    ret = 1
    while n > 1:
        ret = ret * n
        n = n - 1
    return ret


n, a, b = map(int, input().split())
print(2**n - 1 - fact(n) / fact(a) / fact(n - a) -
      fact(n) / fact(b) / fact(n - b))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**9 + 7

def pow_mod_p(n, k, p):
  x = 1
  while k:
    if k % 2 == 1:
      x *= n
      x %= p
    n **= 2
    n %= p
    k >>= 1
  return x

def comb_mod_p(n, k, p):
  x = 1
  for ik in range(k):
    x *= ((n-ik) * pow_mod_p(ik+1, p-2, p))
    x %= p
  return x


def main():
  n, a, b = map(int, input().strip().split())
  sum = (2 ** (n) - 1) % MAX
  sum = sum - comb_mod_p(n, a, MAX) - comb_mod_p(n, b, MAX)
  if sum < 0:
    print(MAX + sum)
  else:
    print(sum)


if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
from math import factorial
def combinationsCount(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))
n,a,b = map(int, input().split())
# n,a,b = 4,1,3
ans = 0
for i in range(n):
    if i==a or i==b:
        pass
    else:
        ans += combinationsCount(n, i)
        
print(ans / (10e9+7))

Submission status: Wrong Answer

Solution code:
import sys


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


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


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


ans = 0
for r in range(n + 1):
    if r == 0 or r == a or r == b:
        pass
    else:
        if r != n and n - r < r:
            pass
        else:
            ans += cmb(n, r, mod)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

li = list(map(int, input().split()))
ans = 0
for i in range(li[0]):
    if i == li[1] or i == li[2]: continue 
    ans += combinations_count(li[0], i) % 1000000007
ans = ans % 1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def comb(n, r, revfact, mod):
    ans = 1
    if r > n // 2: r = n - r
    for i in range(r):
        ans *= (n - i)
        ans %= mod
        ans *= revfact[i + 1]
        ans %= mod
    return ans

def solve():
    input = sys.stdin.readline
    n, a, b = map(int, input().split())
    mod = 7 + 10 ** 9
    total = (pow(2, n, mod) - 1) % mod
    fact = [1] * (b + 2)
    revfact = [1] * (b + 2)
    for i in range(1, b + 2):
        fact[i] = (i * fact[i-1]) % mod
    revfact[b + 1] = pow(fact[b + 1], mod - 2, mod)
    for i in reversed(range(1, b + 1)):
        revfact[i] = ((i + 1) * revfact[i + 1]) % mod

    print((total - comb(n, a, revfact, mod) - comb(n, b, revfact, mod)) % mod)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb
n, a, b = map(int, input().split())
sum = 0
for i in range(1, n+1):
  if i in (a, b):
    continue
  else:
    sum += comb(n, i)
print(int(sum))

Submission status: Wrong Answer

Solution code:
n,a,b = map(int,input().split())
mod = 10 ** 9 + 7
fact = [1]
fact_inv = [1]
for i in range(2*(10**5)+5):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))
fact2 = 1
for i in range(n,n-a,-1):
    fact2 = fact2 * i %mod
fact3 = fact2
for i in range(n-a,n-b,-1):
    fact3 = fact3 * i %mod
def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod
#print(fact2,fact3,fact_inv[a],fact_inv[b])
ans = (2 ** n - 1) % mod
ans -= fact2 * fact_inv[a] % mod
ans -= fact3 * fact_inv[b] % mod
if ans < 0:
    ans += mod
print(ans)

Submission status: Wrong Answer

Solution code:
n, a, b = map(int,input().split())
mod = 10**9+7
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

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

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

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

    return result

nm = (2**n)%mod -1
am = cmb(n,a)%mod
bm = cmb(n,b)%mod
ans = (nm - am - bm)
if ans < 0:
    ans += mod

Submission status: Wrong Answer

Solution code:
n,a,b = map(int,input().split())
mod = 10**9+7
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod



xx = 2**n % mod


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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,a,b=map(int,input().split())
    def modinv(a, mod):
        b,u,v = mod,1,0
        while b:
            t=a//b
            a-=t*b
            a,b=b,a
            u-=t*v
            u,v=v,u
        u%=mod
        if u < 0:
            u+=mod
        return u
    
    def COM(N,k):
        tmp=1
        k=min(k,N-k)
        for i in range(N,N-k,-1):
            tmp*=i
            tmp%=MOD
        for i in range(1,k+1):
            tmp*=modinv(i,MOD)
            tmp%=MOD
        return tmp
            
    ans=pow(2,N,MOD)-1-COM(N,a)-COM(N,b)
    ans=ans if ans>=0 else ans+MOD
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

li = list(map(int, input().split()))
ans = 0
for i in range(li[0]):
    if i == li[1] or i == li[2]: continue 
    ans += combinations_count(li[0], i) % 1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n,a,b=map(int, input().split())
ans=0
surplus=10**9+7
m=math.factorial(n)

def comb_count(n,r): #組み合わせを数える関数
    return m//(math.factorial(n-r)*math.factorial(r))

for i in range(n):
    if i==a or i==b:
        continue
    else:
        ans+=(comb_count(n,i)%surplus)
print(ans)

Submission status: Wrong Answer

Solution code:
n,a,b=map(int,input().split())
if 2*10**5>=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 = 2*10**5
    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((2**n-1-cmb(n,a,mod)-cmb(n,a,mod))%mod)

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

    mod = 10**9+7
    N=2*10**5
    g1 = [n%mod,n*(n-1)%mod] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル
    for i in range( 2, N + 1 ):
        g1.append( ( g1[-1] * (n-i) ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )
    print((2**n-1-cmb(n,a,mod)-cmb(n,b,mod))%mod)

Submission status: Wrong Answer

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


def nCk(n, k, mod=10 ** 9 + 7):
    x = max(k, n - k)
    y = min(k, n - k)
    kkai = 1
    for i in range(2, y + 1):
        kkai = (kkai * i) % mod
    nkkai = 1
    for i in range(x + 1, n + 1):
        nkkai = (nkkai * i) % mod
    answer = sq(kkai, mod - 2, mod) * nkkai % mod
    return answer
ans = 0
mod = 10**9+7
n, a, b = map(int, input().split())
for i in range(1, n//2):
    ans += nCk(n, i)
    ans %= mod
ans *= 2
ans += nCk(n, n//2)
ans += 1
print(ans)
if a <= n//2:
    ans -= nCk(n, a)
if b <= n//2:
    ans -= nCk(n, b)
if a > n//2:
    ans -= nCk(n, n-a)
if b > n//2:
    ans -= nCk(n, n-b)
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
from fractions import gcd 
from functools import reduce
import sys
sys.setrecursionlimit(200000000)
from inspect import currentframe


# my functions here!
#標準エラー出力
def printargs2err(*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),file=sys.stderr)
def debug(x):
    print(x,file=sys.stderr)
def printglobals():
    for (symbol, value) in globals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
def printlocals():
    for (symbol, value) in locals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
#入力（後でいじる）
def pin(type=int):
    return map(type,input().split())
#繰り返し自乗法だよ
#これはnのp乗をmで割ったあまりをだすよ
def modular_w_binary_method (n,m,p):
    ans=1 if n>0 else 0
    while(p>0):
        if p%2==1:
            ans=(ans*n)%m
        n=(n**2)%m
        p//=2
    return ans
#mod上でのaの逆元を出すよ
"""
    フェルマーの小定理より a**(p)%p==a isTrue
    これを利用すれば a**(p-2)%p==a**(-1) isTrue
    元と逆元とをかけてpで割れば1が余るよ！
"""
def modular_inverse(a,prime):
    return(modular_w_binary_method(a,prime,prime-2))

def conbination(n,a,mod=2):
    #cはイラない
    res=1 
    for _ in range(a):
        res=(res*(n-_))%mod
        #print(res)
    for t in range(a):
        res=res*(modular_inverse(t+1,mod))
        res%=bigmod
        #print(res)
    return res
"""
"""

#solution:
def dis2(a,p):
    return (a-p)**2
#input
n,a,b=pin()
an=0
bigmod=(10**9)+7
allcombination=modular_w_binary_method(2, bigmod,n)
ans= allcombination -1 -conbination(n,a,bigmod)-conbination(n,b,bigmod)
print(ans)
#print(["No","Yes"][cond])
#print([["NA","YYMM"],["MMYY","AMBIGUOUS"]][cMMYY][cYYMM])
"""
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""

Submission status: Wrong Answer

Solution code:
p = 10 ** 9 + 7
N = (10 ** 5)*2 +10  # 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)

def cmb(n, r, p):
    mm = 1
    for i in range(n,n-r,-1):
        mm *= i
        mm %= p
    return mm*factinv[r]%p



def pwr(n,k): #nのk乗高速版 n^k
    mod = 10**9+7
    memo = chng2(k)
    lng = len(memo)

    li = [0 for i in range(lng-1)]
    li[0] = 1
    
    a = n
    ans = 1
    for i in range(1,lng-1):
        li[i] = a%mod
        a *= a%mod
        a %= mod 
 
    for i in range(1,lng-1):
        if memo[-i]=='1':
            ans *= li[i]%mod

    return ans%mod

def chng2(n): #10進数nを2進数に変換(配列)
    ans = list(bin(n))
    return ans


mod = 10**9+7
N,A,B = map(int,input().split())
mm1 = pwr(2,N)
mm2 = cmb(N,A,mod)
mm3 = cmb(N,B,mod)

ans = mm1-mm2-mm3-1
if ans < 0:
    ans += mod

print(ans)

Submission status: Wrong Answer

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

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

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

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

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

    return result % mod



ans = pow(2, n, mod) - cmb(n, a) - cmb(n, b) - 1
print("{}, {}, {}".format(pow(2, n, mod), cmb(n, a), cmb(n, b)))
print(ans % mod)

Submission status: Wrong Answer

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

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

total = 0
for i in range(n):
    if i == a or i == b:
        continue
    total += combinations_count(n,i)

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

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

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

print((2 ** n - 1 - cmb_n_a - cmb_n_b) % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import math
n, a, b = map(int, input().split())
X = 2**n-1
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

Y = combinations_count(n, a)
Z = combinations_count(n, b)

print(X-Y-Z)

Submission status: Time Limit Exceeded

Solution code:
from scipy.special import comb

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

r=1
list=[]
while r<=n:
    if r!=a and r!=b:
        x=comb(n, r, exact=True)
        list.append(x)
        r=r+1
    else:
        r=r+1
        continue

y=sum(list)
y=y%(10**9+7)
print(str(y))

Submission status: Time Limit Exceeded

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

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

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 )

total = 2**n % mod - 1
a_sum = cmb(n,a,mod) % mod
b_sum = cmb(n,b,mod) % mod

ans = total - a_sum - b_sum
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, a, b = map(int, input().split())
    mod = 10 ** 9 + 7 #素数
    
    def modpow(x, n, mod):
        res = 1
        while n:
            if n % 2:
                res *= x % mod
            x *= x % mod
            n >>= 1
        return res
    
    def cmb(n, r, mod):
        # 分子(n*(n-1)*...*(n-r+1))
        nume = 1
        for i in range(n-r+1, n+1):
            nume = nume * i# % mod
        # 分母（1*2*...*r）
        deno = 1
        for j in range(1, r+1):
            deno = deno * j % mod
        d = modpow(deno, mod-2, mod)
        return nume * d % mod
    
    all_cmb = pow(2, n, mod) - 1
    bad_a = cmb(n, a, mod)
    bad_b = cmb(n, b, mod)    
    print((all_cmb-bad_a-bad_b) % mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

# 組み合わせ
kaijo = [(tmp := (i * tmp) % mod) for i in range(1, n + 1)]
inv = pow(kaijo[-1], mod - 2, mod)
invs = [inv] + [(inv := (inv * i) % mod) for i in range(n, 0, -1)]
C = [(((kaijo[n - 1] * invs[n - i]) % mod) * invs[i]) % mod for i in range(0, n + 1)]

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

Submission status: Time Limit Exceeded

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

n, a, b = map(int, input().split())
p = 1000000007
ret = abp(2, n, p) - nCr(n, a, p) - nCr(n, b, p) - 1
print(ret % p)

Submission status: Time Limit Exceeded

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

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

n, a, b = map(int, input().split())
p = 1000000007
ret = pow(2, n, p) - nCr(n, a, p) - nCr(n, b, p) - 1
print(ret % p)

Submission status: Time Limit Exceeded

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

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

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

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


p = 1000000007

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

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
from scipy.special import comb
cut=10**9+7

n,a,b=map(int,input().split())
s=2**n
s_1=comb(n, a, exact=True)
s_2=comb(n, b, exact=True)
answer=s-s_1-s_2-1
print(answer%cut)

Submission status: Time Limit Exceeded

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

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

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

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

mylist=list(range(1,en+1)) #1からenまでの配列
mylist.remove(a)
mylist.remove(b)

sum = 0
for r in  mylist:
  t = cmb(en,r,mod)
  sum += t
  
print(sum)

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int,input().rstrip().split())
fac = [1]
for i in range(1,n+1):
    fac.append(fac[i-1]*i)
ans = 0
for i in [i for i in range(1,n+1) if (i!=a) if (i!=b)]:
    ans += fac[n]//fac[i]//fac[n-i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math


n, a, b = map(int, input().split())
P = int(1e9+7)
ans = pow(2, n, P) - 1  # 1本以上の花束の種類


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


ans = (ans - combinations_count(n, a)) % P
ans = (ans - combinations_count(n, b)) % P
print(ans)

Submission status: Time Limit Exceeded

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

p = 10 ** 9 + 7

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

fact = [1, 1]  # 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=pow(2,n)%p-1-cmb(n,a,p)-cmb(n,b,p)

print(ans%p)

Submission status: Time Limit Exceeded

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

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

def main():
    sum = 0
    for i in range(1,n+1):
        if (i==a) or (i==b):
            continue
        sum += combinations_count(n,i)

    print(sum)

main()

Submission status: Time Limit Exceeded

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

fact=[0 for i in range(n+1)]
inv=[0 for i in range(n+1)]
fact_inv=[0 for i in range(n+1)]
fact[0],fact[1]=1,1
inv[1]=1
fact_inv[0],fact_inv[1]=1,1
for i in range(2,n+1):
  fact[i]=fact[i-1]*i%mod
  inv[i]=(mod-inv[mod%i]*(mod//i))%mod
  fact_inv[i]=fact_inv[i-1]*inv[i]%mod
def nck(k):
  return fact[n]*(fact_inv[k]*fact_inv[n-k]%mod)%mod

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

Submission status: Time Limit Exceeded

Solution code:
import math
n, a, b = map(int, input().split())
p = 10 ** 9 + 7
#ans = 2 ** n - 1 - N C a - N C b

def modpow(a, n, MOD):
  res = 1
  while (n > 0):
    if (n & 1):
      res = res * a % MOD
    a = a * a % MOD
    n >>= 1
  return res

def cmb(n, r, p):
  A = 1
  for i in range(r):
    A *= (n - i)
    A *= modpow(i + 1, p - 2, p)
    A %= p
  return A

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

print(ans % p)

Submission status: Time Limit Exceeded

Solution code:
n,a,b=map(int,input().split())
p=10**9+7
x=1
for _ in range(n):
    x=(x*2)%p
x=x-1
def fact(n,p):
    x=1
    if n==0 or n==1:
        pass
    else:
        for i in range(1,n+1):
            x=x*i%p
    return x%p
def cmb(n,r,p):
    if r<0 or n<r:
        return 0
    else:
        return fact(n,p)//fact(r,p)//fact(n-r,p)
X=x-cmb(n,a,p)-cmb(n,b,p)
print(X)

Submission status: Time Limit Exceeded

Solution code:
n,a,b = map(int,input().split())
mod = 10**9 + 7
ans = pow(2,n,mod) - 1
fact = [1]
finv = [1]
for i in range(1, n+1):
    fact += [(fact[i-1] * i) % mod]
    finv += [pow(fact[i], mod-2, mod)]
print((ans - (fact[n]*finv[n-a]*finv[a]) % mod - (fact[n]*finv[n-b]*finv[b]) % mod) % mod)

Submission status: Time Limit Exceeded

Solution code:
n,a,b=list(map(int,input().split()))
#2^n-nCa-nCbを求めればいい。ただし100000007で割ったあまりでなくてはならない
#まずは2^nを求める
def pow(x,n,m):
  if n==0:
    return 1
  res=pow(x*x%m,n//2,m)
  if n%2==1:
    res=res*x%m
  return res
#コンビネーションを求める
fac=[0 for i in range(n+1)]
inv=[0 for i in range(n+1)]
finv=[0 for i in range(n+1)]
fac[0]=1
fac[1]=1
inv[1]=1
finv[0]=finv[1]=1
for i in range(2,n+1):
  fac[i]=fac[i-1]*i%1000000007
  #iの逆数を求める。
  #mod　p=1000000007の世界で逆元を求める
  #p=(p//a)*a+(p%a)
  #mod pをとると a=-(p//a)*(p%a)^-1
  inv[i]=1000000007-(1000000007//i)*inv[1000000007%i]%1000000007
  finv[i]=finv[i-1]*inv[i]%1000000007
  
def combinations(n,k):
  return fac[n]*finv[k]*finv[n-k]%1000000007

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

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
import fractions
import itertools
import functools
import operator

def ncr(n, r):
    if n < r: return 0
    r = min(r, n-r)
    if r == 0: return 1
    numer = functools.reduce(operator.mul, range(n, n-r, -1), 1)
    denom = functools.reduce(operator.mul, range(1, r+1), 1)
    return numer // denom

def solve():
    n, a, b = map(int, input().split())
    sushi = 0
    mod = 10**9+7
    for i in range(1,n+1):
        if i != a and i != b:
            sushi += ncr(n, i)
            sushi %= mod
    sushi %= mod
    print(sushi)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import math
n, a, b = map(int, input().split())
def permutations_count(s, r):
    return math.factorial(s) // math.factorial(s - r) // math.factorial(r)
count = 0

for i in range(n):
  if i + 1 == a or i + 1 == b:
    continue
  count += permutations_count(n, i + 1) 

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

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
import math
def P(n, r):
    ans = 1
    for i in range(n,n-r,-1):
        ans *= i
    return ans

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

def trial_division(n):
    a = [1]
    for i in range(2,int(math.sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            a.append(i)
    a.append(n)
    return a

start = 2
for i in trial_division(n):
    start **= i
aa = C(n,a)
bb = C(n,b)

print((start-1-aa-bb)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n, a, b = map(int, input().split())
import math
def P(n, r):
    ans = 1
    for i in range(n,n-r,-1):
        ans *= i
    return ans

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

def trial_division(n):
    a = [1]
    for i in range(2,int(math.sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            a.append(i)
    a.append(n)
    return a

start = 2
for i in trial_division(n):
    start **= i
aa = C(n,a)
bb = C(n,b)

print(start-1-aa-bb)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

def cmb(n, r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n-r, -1))
    under = reduce(mul, range(1, r+1))
    return over // under

mod = 10**9+7

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

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

mod = 10**9+7

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc156/tasks/abc156_d

import sys
input = sys.stdin.readline


from operator import mul
from functools import reduce

def pow_k(x, n):
    """
    O(log n)
    """
    MOD = 10**9 + 7
    if n == 0:
        return 1

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

    return K * x

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    MOD = 10**9 + 7
    over,under  = 1,1
    for i in range(n, n - r, -1):
        over = over*i
    # over = reduce(mul, range(n, n - r, -1))
    for i in range(1, r + 1):
        under = under*i
    return over // under

def main():
    MOD = 10**9 + 7
    n,a,b = [int(i) for i in input().strip().split()]
    _sum = ((pow_k(2, n))-1) % MOD
    cmb_a = cmb(n, a) %MOD
    cmb_b = cmb(n, b) % MOD
    ans = (_sum - cmb_a - cmb_b) % MOD
    
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

def cmb(n, r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

mod = 10**9+7

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

print(ans)