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

Solution code:
import sys
from itertools import combinations, permutations, product, combinations_with_replacement, accumulate
from heapq import heapify, heappop, heappush, heappushpop
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from math import sqrt, log, floor, ceil, factorial, cos, sin, pi#, gcd
from fractions import gcd
from operator import mul
from functools import reduce
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
INF = float('inf')
LINF = 2**63-1
NIL = -LINF
MOD = 10**9+7
MGN = 4
def II(): return int(input())
def IF(): return float(input())
def IS(): return input().replace('\n', '')
def ILCI(n: int): return [II() for _ in range(n)]
def ILCF(n: int): return [IF() for _ in range(n)]
def ILI(): return list(map(int, input().split()))
def ILLI(n: int): return [[int(j) for j in input().split()] for i in range(n)]
def ILF(): return list(map(float, input().split()))
def ILLF(n: int): return [[float(j) for j in input().split()] for i in range(n)]
def LTOS(lst: list, sep: str = ' '): return sep.join(map(str, lst))
def DEC(lst: list): return list(map(lambda x: x-1, lst))
def INC(lst: list): return list(map(lambda x: x+1, lst))


def nck_mod(N: int, K: int, MOD: int = 10**9+7) -> int:
    """ 非負整数 N, K を受け取り、
    N 個の物から K 個を選ぶ組み合わせの数を返す """
    assert N is not None and K is not None, "N, K は None でない"
    assert N >= 0 and K >= 0

    x, y = 1, 1
    for i in range(K):
        x = x * (N - i) % MOD
        y = y * (i + 1) % MOD

    return x * pow(y, MOD-2, MOD) % MOD


def main():
    N,A,B = ILI()

    all = pow(2, N, MOD)
    ans = (all - nck_mod(N, A, MOD) - nck_mod(N, B, MOD) - 1) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

MOD = 10**9 + 7

def factorial(a):
    return 1 if a == 1 else a * factorial(a - 1) % MOD

def inverse(x):
    return pow(x, MOD - 2, MOD)

def combination(a, b):
    ans = 1
    for i in range(b):
        ans = ans * (a - i) * inverse(i + 1) % MOD
    return ans

n, a, b = map(int, input().split())
ans = pow(2, n, MOD) - 1
ans -= combination(n, a) + combination(n, b)
print(ans % MOD)

Submission status: Accepted

Solution code:
def mod_rep_pow(a, n, mod=(10 ** 9 + 7)):
    res = 1
    while n > 0:
        if n % 2 == 0:
            a = a ** 2 % mod
            n //= 2
        else:
            res = res * a % mod
            n -= 1
    return (res % mod)


def mod_comb(n, k, mod=(10 ** 9 + 7)):
    res1 = 1
    for i in range(n, (n - k), -1):
        res1 *= i
        res1 %= mod
    res2 = 1
    for i in range(1, (k + 1)):
        res2 *= i
        res2 %= mod
    return ((res1 * mod_rep_pow(res2, (mod - 2), mod)) % mod)


n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
ans = mod_rep_pow(2, n, mod) - 1
ans -= mod_comb(n, a, mod)
ans -= mod_comb(n, b, mod)
while ans < 0:
    ans += mod
print(ans)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,a,b = mi()
p = 10 **9 + 7
nstr = str(n)
nstr = nstr[::-1]
two_ten = []
two_ten.append(2)
for i in range(1,11):
    ima = two_ten[i-1]
    temp = 1
    for _ in range(10):
        temp = temp*ima % p
    two_ten.append(temp)

ans = 1
for i in range(len(nstr)):
    temp = 1
    for j in range(int(nstr[i])):
        temp = temp * two_ten[i] % p
    ans = ans * temp % p
ans -= 1

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

#  これは計算量rでncr mod p を求められる。
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

ans -= combination(n,a)
ans -= combination(n,b)
print(ans % p)

Submission status: Accepted

Solution code:
import math

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

p = 10**9 + 7

def pow_mod(n, m, p):
  if m == 0:
    return 1
  elif m % 2 == 0:
    nm2p = pow_mod(n, m//2, p)
    return (nm2p * nm2p) % p
  elif m % 2 == 1:
    return (pow_mod(n, m-1, p) * (n % p)) % p

def compute_ncr_mod(n, r, p):
  r = min(n-r, r)
  n_factorial = 1
  r_factorial = 1
  for i in range(1, r+1):
    n_factorial *= n-i+1
    n_factorial %= p
    r_factorial *= i
    r_factorial %= p
  ncr_modp = (n_factorial * pow_mod(r_factorial, p-2, p)) % p
  return ncr_modp

print((pow_mod(2, n, p) - 1 - compute_ncr_mod(n, a, p) - compute_ncr_mod(n, b, p)) % p)

Submission status: Accepted

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

def cal_Combination_mod(n, r, mod):
    r = min(n - r, r)
    
    X = 1
    Y = 1
    
    for i in range(1, r + 1):
        X *= n - i + 1
        Y *= i
        X %= mod
        Y %= mod
    
    ans = X * pow(Y, mod - 2, mod) % mod
    
    return(ans)

ans = (pow(2, N, mod) -1 - cal_Combination_mod(N, a, mod) - cal_Combination_mod(N, b, mod)) % mod


print(ans)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
mod=10**9+7
res=pow(2,n,mod)-1
p=1
for i in range(n,n-a,-1):
    p=p*i%mod
q=1
for i in range(n,n-b,-1):
    q=q*i%mod
for i in range(1,a+1):
    p=p*pow(i,mod-2,mod)%mod
for i in range(1,b+1):
    q=q*pow(i,mod-2,mod)%mod
print((res-p-q)%mod)

Submission status: Accepted

Solution code:
from sys import stdin
from functools import reduce


def comb_mod(n, a, mod=10**9+7):
    # https://img.atcoder.jp/abc156/editorial.pdf
    # nCk は, k回の積で計算できる
    num = reduce(lambda x, y: x * y % mod, range(n, n - a, -1))
    den = reduce(lambda x, y: x * y % mod, range(1, a + 1))
    # nCk mod = X/Y mod = X * Y^(10**9+7-2) mod
    return num * pow(den, mod - 2, mod) % mod


def get_result(data):
    n, a, b = data[0]
    mod = 10**9+7
    out = pow(2, n, mod) - comb_mod(n, a, mod) - comb_mod(n, b, mod) - 1 
    out %= mod
    return out

if __name__ == '__main__':
    raw_data = [val.rstrip('\n') for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,a,b = list(map(int,input().split()))

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

#くり返し2乗法
def pow(x, n, mod=10**9+7):
    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = (ans*x)%mod
        x = (x*x)%mod
        n = n >> 1 #ビットシフト
    return ans
ret=0
ret=pow(2,n)-1
ret -= combination(n,a)
ret -= combination(n,b)
print(ret%(10**9+7))

Submission status: Accepted

Solution code:
from functools import reduce
 
n,a,b=map(int,input().split())
DIV = 10**9 + 7

def nCr(N,R,DIV):
  f=lambda x,y:x*y%DIV
  X=reduce(f,range(N-R+1,N+1))
  Y=reduce(f,range(1,R+1))
  return X*pow(Y,DIV-2,DIV)%DIV


print((pow(2,n,DIV) - 1 - nCr(n,a,DIV) - nCr(n,b,DIV) ) % DIV)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
M=10**9+7
v=pow(2,n,M)-1
s,t=1,1
for i in range(1,a+1):
  s =s * (n-i+1) % M
  t =t * i %M
v-=(s*pow(t,M-2,M)) % M
s,t=1,1
for i in range(1,b+1):
  s =s * (n-i+1) % M
  t =t * i % M
v-=(s*pow(t,M-2,M)) % M
print(v%M)

Submission status: Accepted

Solution code:
# 2**nの繰り返し二乗法によるあまり計算
def mpow(a,n,mod):
  if n == 0:
    return 1
  elif n == 1:
    return a
  elif n%2==0:
    return (pow(a,n//2,mod))**2%mod
  else:
    return a*pow(a,n-1,mod)%mod
# 2項係数のあまり計算
def mfac(l,r,mod):
  ans = l
  for i in reversed(range(r,l)):
    ans *= i
    ans %= mod
  return ans
def mcomb(n,k,mod):
  A = mfac(n,n-k+1,mod)
  B = mfac(k,1,mod)
  B = mpow(B,mod-2,mod)
  return A*B%mod
 
def main():
  mod = 10**9+7
  n,a,b = map(int,input().split(" "))
  ans = mpow(2,n,mod)-1-mcomb(n,a,mod)-mcomb(n,b,mod)
  ans %= mod
  print(ans)
 
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = 10**9+7
def comb(n, r, mod):
    if r == 0 or r == n:
        return 1
    r = min([r, n-r])
    x, y = 1, 1
    for i in range(1, r+1):
        x *= n+1-i
        x %= mod
        y *= i
        y %= mod
    return x*pow(y, mod-2, mod)%mod

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

Submission status: Accepted

Solution code:
import sys


def alg_combination_mod(n, r, mod):
    r = min(n - r, r)
    if r == 0:
        return 1
    else:
        denominator = 1
        for i in range(n, n - r, -1):
            denominator = (denominator * i) % mod
        molecule = 1
        for i in range(1, r + 1):
            molecule = (molecule * i) % mod
        return denominator * pow(molecule, mod - 2, mod) % mod


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, a, b = list(map(int, input().rstrip('\n').split()))
    all_cnt = pow(2, n, mod)
    a_cnt = alg_combination_mod(n, a, mod)
    b_cnt = alg_combination_mod(n, b, mod)
    print((all_cnt - a_cnt - b_cnt - 1) % mod)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def mpow(a,n,mod):
  if n == 0:
    return 1
  elif n == 1:
    return a
  elif n%2==0:
    return (pow(a,n//2,mod))**2%mod
  else:
    return a*pow(a,n-1,mod)%mod
def mfac(l,r,mod):
  ans = l
  for i in reversed(range(r,l)):
    ans *= i
    ans %= mod
  return ans
def mcomb(n,k,mod):
  A = mfac(n,n-k+1,mod)
  B = mfac(k,1,mod)
  B = mpow(B,mod-2,mod)
  return A*B%mod

def main():
  mod = 10**9+7
  n,a,b = map(int,input().split(" "))
  ans = mpow(2,n,mod)-1-mcomb(n,a,mod)-mcomb(n,b,mod)
  ans %= mod
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys


def alg_combination_mod(n, r, mod):
    r = min(n - r, r)
    if r == 0:
        return 1
    else:
        denominator = 1
        for i in range(n, n - r, -1):
            denominator = (denominator * i) % mod
        molecule = 1
        for i in range(1, r + 1):
            molecule = (molecule * i) % mod
        return denominator * pow(molecule, mod - 2, mod) % mod


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, a, b = list(map(int, input().rstrip('\n').split()))
    all_cnt = pow(2, n, mod) + mod
    a_cnt = alg_combination_mod(n, a, mod)
    b_cnt = alg_combination_mod(n, b, mod)
    print((all_cnt - a_cnt - b_cnt - 1) % mod)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
mod=10**9+7

def modpow(a,n):
    if n==0:
        return 1
    elif n==1:
        return a%mod
    elif n%2==0:
        return (modpow(a,n/2)**2)%mod
    else:
        return (a*modpow(a,n-1))%mod

def modfact(l,r):
    fact=1
    for i in range(l-r+1):
        fact=fact*(r+i)%mod
    return fact

def comb(n,x):
    S=modfact(n,n-x+1)
    fact=modfact(x,1)
    T=modpow(fact,mod-2)
    return S*T%mod

n,a,b=map(int,input().split())
fact=modpow(2,n)
ans=fact-1-comb(n,a)-comb(n,b)
while ans<0:
    ans+=mod
print(ans)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = 10**9+7
def comb(n, r, mod):
    if r == 0 or r == n:
        return 1
    r = min([r, n-r])
    x, y = 1, 1
    for i in range(1, r+1):
        x *= n+1-i
        x %= mod
        y *= i
        y %= mod
    return x*pow(y, mod-2, mod)%mod

ans = (pow(2, n, mod)+3*mod-1-comb(n, a, mod)-comb(n, b, mod))%mod
print(ans)

Submission status: Accepted

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

max_n = 2 * 10 ** 5


MOD = 10 ** 9 + 7
inv = [1] * (max_n + 1)
finv = [1] * (max_n + 1)
perm = [1] * (max_n + 1)
comb = [1] * (max_n + 1)

perm[1] = n
comb[1] = n

for i in range(2, max_n + 1):
	inv[i] = MOD - inv[MOD%i] * (MOD//i) % MOD
	finv[i] = finv[i-1] * inv[i] % MOD
	perm[i] = perm[i-1] * (n - (i - 1)) % MOD
	comb[i] = perm[i] * finv[i] % MOD

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


print((modpow(2, n, MOD) - 1 - comb[a] - comb[b]) % MOD)

Submission status: Accepted

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

mod = 10**9 + 7

def comb(n,k,mod):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%mod
    for i in range(2,k+1):
        inv[i]=mod-inv[mod%i]*(mod//i)%mod
        ans=ans*(n-k+i)*inv[i]%mod
    return ans

m = pow(2,n,mod) - 1

s = comb(n,a,mod)
t = comb(n,b,mod)

ans = m - s - t

print(ans%mod)

Submission status: Accepted

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

mod = 10**9 + 7

def comb(n,k,mod):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%mod
    for i in range(2,k+1):
        inv[i]=mod-inv[mod%i]*(mod//i)%mod
        ans=ans*(n-k+i)*inv[i]%mod
    return ans

def comb_mod(n, r, mod):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    else:
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fac.append(fac[-1] * i % mod)
            inv.append(-inv[mod % i] * (mod // i) % mod)
            finv.append((finv[-1] * inv[-1]) % mod)
        return int(fac[n] * finv[r] * finv[n - r] % mod)

m = pow(2,n,mod) - 1

import math
def perm(n,r):
    return (math.factorial(n)//math.factorial(n-r))

s = comb(n,a,mod)
# print(s)

t = comb(n,b,mod)
# print(t)

ans = m - s - t

print(ans%mod)

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
mod=10**9+7
ans=pow(2,n,mod)-1
def comb(n,m):
    mod=10**9+7
    import functools
    import operator
    x,y=1,1
    for i in range(n-m+1,n+1):
        x*=i
        x%=mod
    for i in range(1,m+1):
        y*=i
        y%=mod
    if n-m<0:
        return 0
    return((x*pow(y,mod-2,mod))%mod)

ans=(ans-comb(n,a)-comb(n,b))%mod
print(ans)

Submission status: Accepted

Solution code:
import math

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


def cmb(n, r, mod):
    c=1
    for i in range(1, r+1):
        c = (c * (n-i+1) * pow(i, mod-2, mod)) % mod
    return c


mod = 10**9+7

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

while ans<0:
    ans+=mod
    
print(ans)

Submission status: Accepted

Solution code:
def pow(x, n, m):
    res = 1
    if n > 0:
        res = pow(x, n // 2, m)
        if n % 2 == 0:
            res = (res * res) % m
        else:
            res = (((res * res) % m) * x) % m
    return res

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

def mod_minus(a, b, m):
    if a < b:
        return a + m - b
    else:
        return a - b

n, a, b = map(int, input().split())
count = pow(2, n, 10**9 + 7) - 1
count = mod_minus(count, comb(n, a), 10**9 + 7)
count = mod_minus(count, comb(n, b), 10**9 + 7)
print(count)

Submission status: Accepted

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

def make_inv(n, mod=10**9+7):
    inv = [0, 1] + [0] * (n-2)
    for i in range(2, n):
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
    return inv

inv = make_inv(10**6)

ac, bc = 1, 1
for i in range(n, n-a, -1):
    ac *= i
    ac %= MOD
for i in range(1, a+1):
    ac *= inv[i]
    ac %= MOD

for i in range(n, n-b, -1):
    bc *= i
    bc %= MOD
for i in range(1, b+1):
    bc *= inv[i]
    bc %= MOD

print((pow(2, n, MOD) - ac - bc - 1) % MOD)

Submission status: Accepted

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

#2^n
nlist=[]#create n(10)=?(2)<-reversed
A=n
while A>=2:
    B=A%2
    nlist.append(B)
    A=A//2
nlist.append(A)
twoexplist=[2]#2,2^2,2^2^2,%p 2^(2^i)
for i in range(len(nlist)):
    twoexplist.append((twoexplist[i]*twoexplist[i])%p)
#2^n=2*2^2*2^2^2 [1,1,1]
twoexp=1
for i in range(len(nlist)):
    if nlist[i]==1:
        twoexp=(twoexp*twoexplist[i])%p

#nCa
ca=1
for i in range(a):
    ca=(ca*(n-i))%p
aa=1
for i in range(a):
    aa=(aa*(i+1))%p
plist=[]
A=p-2
while A>=2:
    B=A%2
    plist.append(B)
    A=A//2
plist.append(A)
aaexplist=[aa]#(aa)^(2^i)
for i in range(len(plist)):
    aaexplist.append((aaexplist[i]*aaexplist[i])%p)
aaexp=1
for i in range(len(plist)):
    if plist[i]==1:
        aaexp=(aaexp*aaexplist[i])%p
nCa=(ca*aaexp)%p

#nCb
cb=1
for i in range(b):
    cb=(cb*(n-i))%p
bb=1
for i in range(b):
    bb=(bb*(i+1))%p
bbexplist=[bb]#(bb)^(2^i)
for i in range(len(plist)):
    bbexplist.append((bbexplist[i]*bbexplist[i])%p)
bbexp=1
for i in range(len(plist)):
    if plist[i]==1:
        bbexp=(bbexp*bbexplist[i])%p
nCb=(cb*bbexp)%p

print((twoexp-1-nCa-nCb)%p)

Submission status: Accepted

Solution code:
import sys, math
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter
from math import factorial
from bisect import bisect_left # bisect_left(list, value)
#from fractions import gcd
enu = enumerate

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

class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
                ) if isinstance(other, ModInt) else
                ModInt(self.x * pow(other, MOD - 2, MOD))
            )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
            )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
                ModInt(other * pow(self.x, MOD - 2, MOD))
            )

    def __rpow__(self, other):
        return (
                ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
                ModInt(pow(other, self.x, MOD))
                )

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

cnt = pow(2, n, MOD)
ng1 = cmb(n, a, MOD)
ng2 = cmb(n, b, MOD)

cnt, ng1, ng2 = map(ModInt, [cnt, ng1, ng2])

res = (cnt - ng1 - ng2 - 1)

print(res)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def M(n): return ModInt(n)
def MI(): return M(I())

class ModInt():
    def __init__(self, n):
        self.n = n

    def __add__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n+x) % mod)

    def __sub__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n-x) % mod)

    def __mul__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n*x) % mod)

    def __truediv__(self, x):
        x = ModInt.xn(x)
        return ModInt(self.n * pow(x, mod-2, mod) % mod)

    @classmethod
    def xn(cls, x):
        if isinstance(x, ModInt):
            return x.n
        return x

    def __str__(self):
        return str(self.n)

def main():
    n,a,b = LI()
    t = pow(2,n,mod) - 1

    def f(a,b):
        t = M(1)
        for j in range(a):
            t *= n-j
            t /= j+1
        r = t.n
        for j in range(a,b):
            t *= n-j
            t /= j+1
        return r + t.n

    t -= f(a,b)

    return t % mod


print(main())

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
def combination(n, a, mod):
    bunbo = 1
    bunshi = 1
    for i in range(a):
        bunshi *= n-i
        bunshi = bunshi%mod
        bunbo *= a-i
        bunbo = bunbo%mod
        
    return bunshi*pow(bunbo, mod-2, mod)%mod
        
        
mod = 1000000007
answer = pow(2, n, mod)
answer -= 1
answer -= combination(n, a, mod)
answer -= combination(n, b, mod)
print(answer%mod)

Submission status: Accepted

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

def combination(n, a, mod):
    bunbo = 1
    bunshi = 1
    for i in range(a):
        bunshi *= n-i
        bunshi = bunshi%mod
        bunbo *= a-i
        bunbo = bunbo%mod
        
    return bunshi*pow(bunbo, mod-2, mod)%mod
        
        
mod = 1000000007
answer = pow(2, n, mod)
answer -= 1
answer -= combination(n, a, mod)
answer -= combination(n, b, mod)
print(answer%mod)

Submission status: Accepted

Solution code:
import sys, math
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter
from math import factorial
from bisect import bisect_left # bisect_left(list, value)
#from fractions import gcd
enu = enumerate

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

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

cnt = pow(2, n, mod)
ng1 = cmb(n, a, mod)
ng2 = cmb(n, b, mod)

res = (cnt - ng1 - ng2 - 1) % mod

print(res)

Submission status: Accepted

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

a=min(a,n-a)
b=min(b,n-b)

mod=10**9+7

def modinv(n):
    return pow(n,mod-2,mod)

ra=1
for i in range(a):
    ra*=(n-i)
    ra*=modinv(i+1)
    ra%=mod

rb=1
for i in range(b):
    rb*=(n-i)
    rb*=modinv(i+1)
    rb%=mod
    
r=((2**n-1)%mod-ra-rb)%mod

print(r)

Submission status: Accepted

Solution code:
import unittest
import functools


class TestD(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think(4, 1, 3), 7)

    def test_2(self):
        self.assertEqual(think(1000000000, 141421, 173205), 34076506)


def solve():
    n, a, b = read()
    result = think(n, a, b)
    write(result)


def read():
    return read_int(3)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(n, a, b):
    mode = 10 ** 9 + 7

    result = pow(2, n, mode) - 1
    if result < 0:
        result += mode
    result -= combi(n, a, mode)
    if result < 0:
        result += mode
    result -= combi(n, b, mode)
    if result < 0:
        result += mode
    return result


def write(result):
    print(result)


def combi(n, a, mode):
    numer = functools.reduce(lambda x, y: (x * y) % mode, range(n, n - a, -1))
    denom = functools.reduce(lambda x, y: (x * y) % mode, range(1, a + 1))
    return (numer * pow(denom, mode - 2, mode)) % mode


def fact(n, mode=None):
    result = 1
    for i in range(1, n + 1):
        result *= i
        if mode:
            result %= mode
    return result


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Accepted

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

def kurikaeshi(x, n, mod):
    if n == 1:
        return x%mod
    elif n %2 == 0:
        return kurikaeshi(x, n//2, mod)**2%mod
    elif n %2 == 1:
        return kurikaeshi(x, n//2, mod)**2*x%mod
    
    
def combination(n, a, mod):
    bunbo = 1
    bunshi = 1
    for i in range(a):
        bunshi *= n-i
        bunshi = bunshi%mod
        bunbo *= a-i
        bunbo = bunbo%mod
        
    return bunshi*pow(bunbo, mod-2, mod)%mod
        
        
mod = 1000000007
answer = pow(2, n, mod)
answer -= 1
answer -= combination(n, a, mod)
answer -= combination(n, b, mod)
print(answer%mod)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
  
def perm(n, k, p):
  ret = 1
  for i in range(n, n-k, -1):
    ret = (ret * i)%p
  return ret

def comb(n, k, p=1000000007):
  a = perm(n, k, p)
  b = perm(k, k, p)
  return (a*pow(b, p-2, p))%p

def main():
    mod = 1000000007
    n,a,b = map(int, input().split())
    ans = pow(2,n,mod) - 1 - comb(n,a) - comb(n,b)
    print(ans%mod)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from functools import reduce
  
def perm(n, k, p):
  ret = 1
  for i in range(n, n-k, -1):
    ret = (ret * i)%p
  return ret

def comb(n, k, p):
  """power_funcを用いて(nCk) mod p を求める"""
  a = perm(n, k, p)
  b = perm(k, k, p)
  return (a*pow(b, p-2, p))%p
  
n, a, b = map(int, input().split())

MOD = 10**9 + 7


print((pow(2,n,MOD) - 1 - comb(n, a, MOD) - comb(n, b, MOD))%MOD)

Submission status: Accepted

Solution code:
from functools import reduce

def comb(n, k, p):
  a = reduce(lambda x,y: x*y%p, range(n,n-k,-1))
  b = reduce(lambda x,y: x*y%p, range(1,k+1))
  return (a*pow(b, p-2, p))%p
      
n, a, b = map(int, input().split())
MOD = 10**9 + 7
     
print((pow(2,n,MOD) - 1 - comb(n, a, MOD) - comb(n, b, MOD))%MOD)

Submission status: Accepted

Solution code:
from functools import reduce
  
def comb(n, k, p):
  """power_funcを用いて(nCk) mod p を求める"""
  a = reduce(lambda x,y: x*y%p, range(n,n-k,-1))
  b = reduce(lambda x,y: x*y%p, range(1,k+1))
  return (a*pow(b, p-2, p))%p
  
n, a, b = map(int, input().split())

MOD = 10**9 + 7


print((pow(2,n,MOD) - 1 - comb(n, a, MOD) - comb(n, b, MOD))%MOD)

Submission status: Accepted

Solution code:
def factorial_mod(a, M):
    # return a!(mod M)
    ans = 1
    for i in range(a,1,-1):
        ans = (ans * i) % M
    return ans
def test(n, a, M):
    # return (nCaの分子) % M
    ans = 1
    for i in range(a):
        ans = (ans * (n-i)) % M
    return ans
def combination_mod(n,a,M):
    # return nCa % M
    tmp = factorial_mod(a,M)
    tmp = pow(tmp, M-2, M)
    ans = test(n,a,M) * tmp % M
    return ans
def output(n,a,b):
    M = 10**9+7
    ans = (pow(2,n,M) - 1 - combination_mod(n,a,M) - combination_mod(n,b,M)) % M
    return ans
n, a, b = map(int, input().split())
print(output(n,a,b))

Submission status: Accepted

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

MAX = 2*10**5
bikkuri=[1]
for i in range(1,MAX+1):
    bikkuri.append((bikkuri[-1]*i)%mod)

tmpN = n
tmp = 1
for _ in range(a):
    tmp *= tmpN
    tmp %= mod
    tmpN -= 1
#%print(tmp)
A = (tmp*pow(bikkuri[a],mod-2,mod))%mod

tmpN = n
tmp = 1
for _ in range(b):
    tmp *= tmpN
    tmp %= mod
    tmpN -= 1
B = (tmp*pow(bikkuri[b],mod-2,mod))%mod

#print(beki,A,B)
print((beki-A-B)%mod)

Submission status: Accepted

Solution code:
from functools import reduce

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

def fast_comb(a,b,mod):
    up = reduce(lambda x,y: x*y%mod, range(a,a-b,-1))
    down = reduce(lambda x,y: x*y%mod, range(1,b+1))
    return (up * pow(down, mod-2, mod)) % mod

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

Submission status: Accepted

Solution code:
def mod_kaijou(n,MOD = 10 ** 9 + 7 ):
    ans = 1
    for i in range(1,n + 1):
        ans *= i
        ans %= MOD
    return ans
# def pow_r(x, n,MOD = 1):
#     """
#     O(log n)
#     """
#     if n == 0:  # exit case
#         return 1
#     if n % 2 == 0:  # standard case ① n is even
#         return pow_r(x ** 2, n // 2) % MOD
#     else:  # standard case ② n is odd
#         return x * pow_r(x ** 2, (n - 1) // 2) % MOD

def 逆元_一覧(n,MOD = 10 ** 9 + 7):
    li = [0]
    for i in range(1,n+ 1):
        li.append(pow(i,MOD-2,MOD))
    return li


def mod_nCr(n,r,MOD = 10 ** 9 + 7 ):
    ans = 1
    mul = n
    li = 逆元_一覧(r + 1)
    for i in range(r ):
        ans *= mul
        ans *= li[i + 1]
        mul -= 1
        ans %= MOD
    return ans


MOD= 10 ** 9 + 7
n,a,b = list(map(int,input().split()))
all = pow(2,n,MOD)  - 1
all %= MOD
A = mod_nCr(n,a,MOD)
all -= A
all %= MOD
B = mod_nCr(n,b,MOD)
all -= B
all %= MOD
print(all)

Submission status: Accepted

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

ans = 0
mod = 10**9+7
ans = (pow(2,n,mod)-1)%mod

com1 = 1
for i in range(n-a+1,n+1):
    com1 = com1*i%mod
for i in range(1,a+1):
    com1 = com1 * pow(i,mod-2,mod)%mod
com2 = 1
for i in range(n-b+1,n+1):
    com2 = com2*i%mod
x = 1
for i in range(1,b+1):
    x = x*i%mod
com2 = com2*pow(x,mod-2,mod)%mod

ans = (ans - com1 - com2)%mod
print(ans)