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
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]



def mcomb(n, k, mod):
    def mfac(l, r, mod):
        ans = l
        for i in reversed(range(r, l)):
            ans *= i
            ans %= mod
        return ans

    A = mfac(n,n-k+1,mod)
    B = mfac(k,1,mod)
    # B = mpow(B,mod-2,mod)
    B = pow(B, mod-2, mod)
    return A * B % mod

INF = float('inf')

def solve():
    n, a, b = MI()
    mod = 1000000007

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def choose(n, a):
    x = 1; y = 1
    for i in range(a):
        x = x * (n-i) % mod
        y = y * (i+1) % mod
    return x * pow(y, mod-2, mod) % mod

mod = 10 ** 9 + 7

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


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

print(ans % mod)

Submission status: Accepted

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

    nn = n
    ans1 = 1
    while a > 0:
        ans1 = (ans1 * n * pow(a, mod-2, mod)) % mod
        n -= 1
        a -= 1

    ans2 = 1
    n = nn
    while b > 0:
        ans2 = (ans2 * n * pow(b, mod-2, mod)) % mod
        n -= 1
        b -= 1

    print((pow(2, nn, mod)-ans1-ans2-1) % mod)


main()

Submission status: Accepted

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

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

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

Sum %= mod

Sum -= fur(n,a,mod) % mod
Sum -= fur(n,b,mod) % mod
Sum %= mod
print(Sum)

Submission status: Accepted

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

MOD = 1000000007  # type: int
def combination(n: int, r:int, mod=MOD):
    n1 = n+1
    r = 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



def solve(n: int, a: int, b: int):
    k = pow(2, n, MOD) - combination(n,a) - combination(n,b)
    print(k % MOD - 1)
    return


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

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


# 参考：https://qiita.com/MyOden/items/b669bfbf6dbf83242bdf =>フェルマーの小定理を基に演算関数を用意
def fur(n, r):
    p, q = 1, 1
    for i in range(r):
        p = p * (n - i) % mod
        q = q * (i + 1) % mod
    return p * pow(q, mod - 2, mod) % mod


nca = fur(n, a)
ncb = fur(n, b)
ans = (al - nca - ncb) % mod

print(ans)

Submission status: Accepted

Solution code:
def comb(n,r):
    if n-r < r:
        r=n-r
    p=1
    q=1
    for i in range(r):
        p *=n-i #=n(n-1)・・(n-r+1)
        p %= mod
        q *=i+1 #=1・2・・r =r!
        q %=mod
    return p*pow(q,mod-2,mod)

# 初期入力
N,a,b = (int(x) for x in input().split())
mod =10**9 +7
#
all_n =pow(2,N,mod) -1

#嫌いな数の組み合わせ
dislike_a =comb(N,a)
dislike_b =comb(N,b)

ans = (all_n -dislike_a -dislike_b)%mod
print(ans)

Submission status: Accepted

Solution code:
MOD=10**9+7
def com(n,k,mod):
    res=1
    tmp=1
    for i in range(1,k+1):
        res=res*(n-i+1)%mod
        tmp=tmp*i%mod
    a=pow(tmp,1000000005,mod)
    return res*a%mod

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

Submission status: Accepted

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

def comb(n,r,mod=10**9+7):
    a=1
    b=1
    r = min(r,n-r)
    for i in range(r):
        a = a*(n-i)%mod
        b = b*(i+1)%mod
    return a*pow(b,mod-2,mod)%mod

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

Submission status: Accepted

Solution code:
def mod_power(x,y,p):
    if y == 1:
        return x % p
    elif y % 2 == 0:
        return (mod_power(x,y/2,p)**2) % p
    else:
        return (mod_power(x,y-1,p) * x ) % p

def mod_inv(x,p):
    return mod_power(x,p-2,p)

def mod_nCa(n,a,p):
    num = 1
    den = 1
    for i in range(a):
        num = (num * (n-i)) % p
        den = (den * (a-i)) % p
    return (num * mod_inv(den,p)) % p


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

m = 10**9 + 7

print((mod_power(2,n,m) - mod_nCa(n,a,m) - mod_nCa(n,b,m) - 1) % m)

Submission status: Accepted

Solution code:
def inv(N):
    #n^-1
    inv=[1,1]

    for i in range(2,N+1):
        inv.append(mod-mod//i*inv[(mod%i)]%mod)
    return inv
n,a,b=map(int,input().split())

mod=10**9+7

def repmod(n,m):
    if n==1:return 2
    nn = n // 2
    te = repmod(nn, m)
    if n%2==0:
        ans=(te*te)%mod
        return ans
    elif n%2==1:
        ans=(2*te*te)%mod
        return ans


total=repmod(n,mod)-1

c=max(a,b)

temp=1
s=0
invlist=inv(c)
for i in range(c):
    temp=(temp*(n-i))%mod
    invi=invlist[i+1]
    temp=temp*invi
    if i+1==a:
        s+=temp
    if i+1==b:
        s+=temp

ans=(total-s)%mod
print(ans)

Submission status: Accepted

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

mod=10**9+7

def repmod(n,m):
    if n==1:return 2
    nn = n // 2
    te = repmod(nn, m)
    if n%2==0:
        ans=(te*te)%mod
        return ans
    elif n%2==1:
        ans=(2*te*te)%mod
        return ans
def extgcd(a,b):
    a0,b0=a,b
    x0,y0=1,0
    x1,y1=0,1

    while b0!=0:
        q = a0 // b0
        r = a0 % b0

        a0,b0=b0,r
        temp=x1
        x0,x1=x1,x0-q*x1
        y0,y1=y1,y0-q*y1

    return a0,x0,y0

def mo(x,m):
    return (m+x%m)%m

def inv(a,m):
    g,x,y=extgcd(a,m)
    ans=mo(x,m)
    return ans

total=repmod(n,mod)-1

c=max(a,b)

temp=1
s=0
for i in range(c):
    temp=(temp*(n-i))%mod
    invi=inv(i+1,mod)
    temp=temp*invi
    if i+1==a:
        s+=temp
    if i+1==b:
        s+=temp

ans=(total-s)%mod
print(ans)

Submission status: Accepted

Solution code:
def solve():
    N,A,B = map(int, input().split())
    prod = 1
    MOD = 10**9 + 7
    ans = pow(2,N,MOD) -1 #bit全探索と同じ理屈

    for i in [A,B]:
        num, inv = 1, 1
        for j in range(N-i+1,N+1):
            num = (num * j) % MOD

        for k in range(1, i+1):
            inv = inv * k % MOD
        ans = ans -(num * pow(inv, MOD-2, MOD)) % MOD

    print(ans%MOD)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
from math import factorial

div = 10 ** 9 + 7

def cnt_combination(n, r):
    res = 1
    fac = 1

    for i in range(r):
        res *= n - i
        res %= div
        fac *= i + 1
        fac %= div

    return res * pow(fac, div - 2, div) % div


def resolve():
    n, a, b = map(int, input().split())
    ans = pow(2, n, div) - 1
    print((ans - cnt_combination(n, a) - cnt_combination(n, b)) % div)

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4 1 3"""
        output = """7"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """1000000000 141421 173205"""
        output = """34076506"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = pow(10, 9) + 7
 
def comb(N, x):
    numerator = 1
    for i in range(N-x+1, N+1):
        numerator = numerator * i % mod
    denominator = 1
    for j in range(1, x+1):
        denominator = denominator * j % mod
    d = pow(denominator, mod-2, mod)
    return numerator * d
 
a = comb(n, a)
b = comb(n, b)
 
print((pow(2, n, mod) -1 -a -b) % mod)

Submission status: Accepted

Solution code:
import math
n,a,b=map(int,input().split())
mod=10**9+7
a_tmp=1
b_tmp=1
for i in range(a):
    a_tmp*=(n-i)
    a_tmp%=mod
for i in range(b):
    b_tmp*=(n-i)
    b_tmp%=mod

nca=a_tmp*pow(math.factorial(a),mod-2,mod)%mod
ncb=b_tmp*pow(math.factorial(b),mod-2,mod)%mod

print((pow(2,n,mod)-1-nca-ncb)%mod)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
MOD = 10**9 + 7
def comb(n, k, mod):
    if n<0 or k<0 or n<k:
        return 0
    if n==0 or k==0:
        return 1
    k=k if k<=n-k else n-k
    x = 1
    y = 1
    for i in range(k):
        x=x*(n-i)%mod
        y=y*(i+1)%mod
    return (x*pow(y,mod-2,mod))%mod
n,a,b = map(int,input().split())
A = comb(n,a,MOD)
B = comb(n,b,MOD)
C = pow(2,n,MOD)
ans = C -A-B-1
print(ans%MOD)

Submission status: Accepted

Solution code:
import math
MOD = 10**9+7
def modpow(a, n, p):
  if n == 1:
    return a % p 
  elif n % 2 == 1:
    return a * modpow(a, n-1, p) % p
  else:
    return modpow(a, n//2, p) **2 % p

def I():
  return input()
def II():
  return int(input())
def MII():
  return map(int, input().split())
def LMII():
  return list(map(int, input().split()))
n,a,b = MII()
fact_a = 1
fact_n_a = 1
fact_b = 1
fact_n_b = 1
for i in range(a):
    fact_a = fact_a * (i+1) % MOD
    fact_n_a = fact_n_a * (n-a+1+i) % MOD
cmb_a = fact_n_a * modpow(fact_a, MOD-2, MOD) % MOD
for i in range(b):
    fact_b = fact_b * (i+1) % MOD
    fact_n_b = fact_n_b * (n-b+1+i) % MOD
cmb_b = fact_n_b * modpow(fact_b, MOD-2, MOD) % MOD

print((modpow(2, n, MOD)-1-cmb_a-cmb_b)%MOD)

Submission status: Accepted

Solution code:
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
            K %= MOD
        x *= x
        x %= MOD
        n //= 2

    return K * x

def cmb(n, r):
	MOD = 10**9+7
	if n - r < r: r = n - r
	if r == 0: return 1
	if r == 1: return n

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

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

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

	return result

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

ans = pow_k(2,n)-1

print((ans - cmb(n,a) - cmb(n,b))%MOD)

Submission status: Accepted

Solution code:
#import numpy as np

n,a,b=map(int,input().split())
#M=10**8
M=2*10**5+1
Mod=10**9+7
fac=[0]*M
finv=[0]*M
inv=[0]*M
ans=pow(2,n,Mod)-1

#finvに逆元、facに階乗のmod
"""
def COMinit():
  fac[0]=fac[1]=1
  finv[0]=finv[1]=1
  inv[1]=1
  for i in range(2,M):
    fac[i]=(fac[i-1]*i%Mod)%Mod
    inv[i]=Mod-inv[Mod%i]*(Mod//i) %Mod
    finv[i]=(finv[i-1]*inv[i]%Mod)%Mod
"""

def COMinit():
  fac[0]=n%Mod
  fac[1]=(fac[0]*(n-1))%Mod
  finv[0]=finv[1]=1
  inv[1]=1
  for i in range(2,M):
    fac[i]=(fac[i-1]%Mod*(n-i))%Mod
    inv[i]=Mod-inv[Mod%i]*(Mod//i) %Mod
    finv[i]=(finv[i-1]*inv[i]%Mod)%Mod
def COM(n,k):
  if n<k:
    return 0
  if n<0 or k<0:
    return 0
  return (fac[k-1]*(finv[k]%Mod))%Mod

COMinit()
ans-=(COM(n,a)+COM(n,b))
print(ans%Mod)

Submission status: Accepted

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

def cmb(n, k):
  ne = 1
  ke = 1
  for i in range(k):
    ne = ne * (n - i) % mod
    ke = ke * (i + 1) % mod
  
  res = ne * pow(ke, (mod - 2), mod) % mod
  return res

result = (pow(2, N, mod) - 1 - cmb(N, a) - cmb(N, b)) % mod
print(result)

Submission status: Accepted

Solution code:
from functools import reduce

if __name__ == '__main__':
    def mod_comb(n, k, mod):
        child = reduce(lambda x, y: x * y % mod, range(n, n - k, -1))
        parent = reduce(lambda x, y: x * y % mod, range(1, k + 1))
        return child * pow(parent, mod - 2, mod) % mod


    MOD = 10 ** 9 + 7
    n, a, b = map(int, input().split())
    all_comb = pow(2, n, MOD)
    fa = mod_comb(n, a, MOD)
    fb = mod_comb(n, b, MOD)
    ans = all_comb - fa - fb - 1
    print(ans % MOD)

Submission status: Accepted

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

mod = 10 ** 9 + 7

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

def mod_inverse(a:int):
    return (mod_pow(a, mod - 2)) % mod

def mod_nCr(n:int, r:int):
    num, den = 1, 1
    for i in range(r):
        num = (num * (n - i)) % mod
        den = (den * (r - i)) % mod
    return (num * mod_inverse(den)) % mod

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

Submission status: Accepted

Solution code:
def main():
  n,a,b=map(int,input().split())
  mod=pow(10,9)+7    
  def comb(n,r,mod):
    r=r if r<=n-r else n-r
    x,y=1,1
    for i in range(r):
      x=x*(n-i)%mod
      y=y*(i+1)%mod
    return (x*pow(y,mod-2,mod))%mod
  ans=(pow(2,n,mod)-comb(n,a,mod)-comb(n,b,mod)-1)%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):
    res = 1
    for i in range(1, r+1):
        res = res*(n-i+1) % mod
        res = res*pow(i, mod-2, mod) % mod
    return res


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

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7


class ModInt:

	def __init__(self, x, inv=None):
		self.x = x.x if isinstance(x, ModInt) else x % MOD
		self.inv = inv

	__str__ = lambda self:str(self.x)
	__repr__ = __str__
	__int__ = lambda self: self.x
	__index__ = __int__

	__add__ = lambda self, other: ModInt(self.x + ModInt(other).x)
	__radd__ = lambda self, other: ModInt(other + self.x)
	__iadd__ = __add__

	__sub__ = lambda self, other: ModInt(self.x - ModInt(other).x)
	__rsub__ = lambda self, other: ModInt(other - self.x)
	__isub__ = __sub__

	__mul__ = lambda self, other: ModInt(self.x * ModInt(other).x)
	__rmul__ = lambda self, other: ModInt(other * self.x)
	__imul__ = __mul__

	__pow__ = lambda self, other: ModInt(pow(self.x, ModInt(other).x, MOD))
	__rpow__ = lambda self, other: ModInt(pow(other, self.x, MOD))
	__pow__ = __pow__

	def __truediv__(self, other):
		if isinstance(other, ModInt) and other.inv != None:
			return ModInt(self.x * other.inv)
		else:
			return ModInt(self.x * pow(ModInt(other).x - 2))
	
	def __rtruediv__(self, other):
		if not self.inv:
			return ModInt(other * pow(self.x - 2))
		else:
			return ModInt(other * self.inv)

	__itruediv__ = __truediv__

	__floordiv__ = __truediv__
	__rfloordiv__ = __rtruediv__
	__ifloordiv__ = __itruediv__

	__mod__ = lambda self, other: ModInt(self.x % other)
	__rmod__ = lambda self, other: ModInt(other % self.x)
	__imod__ = __mod__

	__lt__ = lambda self, other: self.x < ModInt(other).x
	__gt__ = lambda self, other: self.x > ModInt(other).x
	__le__ = lambda self, other: self.x <= ModInt(other).x
	__ge__ = lambda self, other: self.x >= ModInt(other).x
	__eq__ = lambda self, other: self.x == ModInt(other).x
	__ne__ = lambda self, other: self.x != ModInt(other).x

class Fact:
	def __init__(self, MAX):
		MAX += 1
		self.fact = [0] * MAX
		finv = [0] * MAX
		inv = [0] * MAX
		self.fact[0] = 1
		self.fact[1] = 1
		finv[0] = 1
		finv[1] = 1
		inv[1] = 1
		for i in range(2, MAX):
			self.fact[i] = self.fact[i - 1] * i % MOD
			inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
			finv[i] = finv[i - 1] * inv[i] % MOD
		for i in range(MAX):
			self.fact[i] = ModInt(self.fact[i], inv=finv[i])
	def __call__(self, value):
		return self.fact[value]

class Comb:
	def __init__(self, fact):
		self.fact = fact
	def __call__(self, n, r):
		return self.fact(n) // self.fact(n-r) // self.fact(r)

class MiniComb:
	def __init__(self, fact):
		self.fact = fact
	def __call__(self, n, r):
		a = ModInt(1)
		for i in range(r):
			a *= n - i
		return a // self.fact(r)


def main():
	n, a, b = map(int, sys.stdin.readline().split())
	fact = Fact(2*10**5)
	comb = MiniComb(fact)
	print(ModInt(2**ModInt(n) - 1 - comb(n, a) - comb(n, b)))
main()

Submission status: Accepted

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

akai=1
nakai=n
bkai=1
nbkai=n
for i in range(2,a+1):
  akai=(akai%mod)*(i%mod)
  nakai=(nakai%mod)*((n-i+1)%mod)
for i in range(2,b+1):
  bkai=(bkai%mod)*(i%mod)
  nbkai=(nbkai%mod)*((n-i+1)%mod)
akai=akai%mod
bkai=bkai%mod
nakai=nakai%mod
nbkai=nbkai%mod
nakai=nakai*pow(akai,mod-2,mod)
nbkai=nbkai*pow(bkai,mod-2,mod)
print((pow(2,n,mod)-nakai-nbkai-1)%mod)

Submission status: Accepted

Solution code:
# ans = 全通り - nCa - nCb
#     = 2^n - 1 - nCa - nCb
def comb(n,r,mod=10**9+7):
    a=1
    b=1
    r = min(r,n-r)
    for i in range(r):
        a = a*(n-i)%mod
        b = b*(i+1)%mod
    return a*pow(b,mod-2,mod)%mod

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

mod = (10**9) + 7

num_all = pow(2, n, mod) - 1
nca = comb(n, a, mod=mod)
ncb = comb(n, b, mod=mod)

ans = num_all - nca - ncb
ans %= mod

print(ans)

Submission status: Accepted

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

mod = 10**9+7

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

def cmb_mod(n,k):
    mod_table = []
    for i in range(k):
        mod_table.append(pow(i+1,mod-2,mod))
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= mod_table[i]
        ans %= mod
    return ans
result = (pow_fast(2,N)-1)%mod - cmb_mod(N,A) - cmb_mod(N,B)
print(result%mod)

Submission status: Accepted

Solution code:
N, A, B = map(int, open(0).read().split())

MOD = 10 ** 9 + 7

def comb(n, k):
    ret = 1
    for i in range(1, k + 1):
        ret = ret * (n - i + 1) % MOD        
        ret = ret * pow(i, MOD - 2, MOD) % MOD

    return ret

print((pow(2, N, MOD) - 1 - comb(N, A) - comb(N, B)) % MOD)

Submission status: Accepted

Solution code:
def cmb(n, r, MOD):
    # nCr = a/b
    a, b = 1, 1
    for i in range(r):
        a = a * (n - i) % MOD
        b = b * (i + 1) % MOD
    return a * pow(b, MOD - 2, MOD)

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

Submission status: Accepted

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

def comb(n,r,mod=10**9+7):
    a=1
    b=1
    r = min(r,n-r)
    for i in range(r):
        a = a*(n-i)%mod
        b = b*(i+1)%mod
    return a*pow(b,mod-2,mod)%mod

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

Submission status: Accepted

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')

N,A,B = imn()

# 繰り返し2乗法
ans = pow(2,N,MOD)-1

MAX = (10**5)*2

# nCrを求める
def cmb(n,r):
    denominator = numerator = 1
    for i in range(1,r+1):
        denominator = (denominator*i)%MOD
        numerator = (numerator * (n-i+1)) % MOD
    return (numerator * pow(denominator, MOD-2, MOD))%MOD

print((ans-cmb(N,A)-cmb(N,B))%MOD)

Submission status: Accepted

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

def rev(x):
    re = 10**9+5
    num = 1
    ix = x
    while re > 0:
        if re%2 == 1:
            num = (num*ix)%mod
        re //= 2
        ix = (ix**2)%mod
    return(num)

def kaijo(x):
    num = 1
    for i in range(1,x+1):
        num = (num*i)%mod
    return(num)

re = n
ans = 1
i2 = 2
while re > 0:
    if re%2 == 1:
        ans = (ans*i2)%mod
    re //= 2
    i2 = (i2**2)%mod
nca = 1
ncb = 1
for i in range(a):
    nca = (nca*(n-i))%mod
for i in range(b):
    ncb = (ncb*(n-i))%mod

ans -= 1
ans = (ans-(nca*rev(kaijo(a)))%mod)%mod
ans = (ans-(ncb*rev(kaijo(b)))%mod)%mod

print(ans)

Submission status: Accepted

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

# a
x = 1
for i in range(n - a + 1, n + 1):
    x = (x*i) % mod
y = 1
for i in range(1, a + 1):
    y = (y*i) % mod

a_ans = x*pow(y, mod-2, mod)

x = 1
for i in range(n - b + 1, n + 1):
    x = (x*i) % mod
y = 1
for i in range(1, b + 1):
    y = (y*i) % mod
b_ans = x*pow(y, mod-2, mod)
print((ans - a_ans - b_ans) % mod)

Submission status: Accepted

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


def nck(n, k, mod):
    bunbo = bunshi = 1
    for i in range(k):
        bunshi = (bunshi * (n-i)) % mod
        bunbo = (bunbo * (i+1)) % mod
    return (bunshi * pow(bunbo, mod-2, mod)) % mod


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

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
def cmb(n, r, mod):
    x = 1 
    y = 1
    for i in range(r):
        x = x*(n-i)%(mod)
    for i in range(1,r+1):
        y = y*i%(mod)
    return x * pow(y,mod-2,mod) %mod

v = int(pow(2,n,10**9+7)-1-cmb(n,a,10**9+7)-cmb(n,b,10**9+7))
if v >= 0:
    print(v)
else:
    if v+10**9+7 >= 0:
        print(v+10**9+7)
    else:
        print(v+2*(10**9+7))

Submission status: Accepted

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

ans = pow(2, n, mod)

def C(n, k):
    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

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

Submission status: Accepted

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

k=10**9+7
we=pow(2,n,k)

su=1
suu=1
for i in range(a):
  su=su*(i+1)%k
  suu=suu*(n-i)%k

df=suu * pow(su,k-2,k)%k

su=1
suu=1
for i in range(b):
  su=su*(i+1)%k
  suu=suu*(n-i)%k
  
df+=suu*pow(su,k-2,k)%k
we=we-df-1

print(we%k)

Submission status: Accepted

Solution code:
import math

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

n,a,b = map(int, input().split())
s = pow(2,n,mod)

print((s-fur(n,a)-fur(n,b)-1)%mod)

Submission status: Accepted

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

from operator import mul
from functools import reduce
import math

flg = (a == n-b)
rep = math.ceil(n/2)
MOD = 10**9+7
memo = 0

def modpow(a: int, p: int, mod: int) -> int:
    # return a**p (mod MOD) O(log p)
    if p == 0:
        return 1
    if p % 2 == 0:
        half = modpow(a, p//2, mod)
        return half*half % mod
    else:
        return a * modpow(a, p-1, mod) % mod


from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mod_mul, range(n, n - r, -1), 1)
    denom = reduce(mod_mul, range(1, r + 1), 1)
    return numer*pow(denom, MOD-2, MOD)%MOD
  
def mod_mul(a, b):
  return mul(a%MOD, b%MOD)%MOD

s = 0
ans = modpow(2, n, MOD)-1
if flg:
  ans = ans - 2*combinations_count(n, a)%MOD
else:
  ans = (ans - combinations_count(n,a))%MOD - combinations_count(n,b)
print(ans%MOD)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    # https://atcoder.jp/contests/abc156/submissions/11621672
    def modpow(a, b, mod=10 ** 9 + 7):
        ret = 1
        while b > 0:
            if b % 2 == 1:
                ret = ret * a % mod
            a = a * a % mod
            b //= 2
        return ret

    def modcomb(n, c, mod=10 ** 9 + 7):
        if c > n - c:
            c = n - c
        u, d = 1, 1
        for i in range(c):
            u = u * (n - i) % mod
            d = d * (i + 1) % mod
        return u * modpow(d, mod - 2) % mod

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


resolve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    def modcomb(n, c, mod=10 ** 9 + 7):
        if c > n - c:
            c = n - c
        u, d = 1, 1
        for i in range(c):
            u = u * (n - i) % mod
            d = d * (i + 1) % mod
        return u * pow(d, mod - 2,mod)

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


resolve()

Submission status: Accepted

Solution code:
# k本の花束の作り方は正直わからない
# 2**n-1通りのはなの選び方があるのは間違いない
# その中からごうけいがa,bになるものは除く
# nCa+nCb何じゃない？
# 組み合わせ数を計算するだけならめんどくさいライブラリを使わなくてもmathのfactorialで階乗を計算すれば良い
from functools import lru_cache
import math
n,a,b = map(int,input().split())


# これはfactorialの計算がやばいことになるので(10**9+7)で割りながらやっていこう
# ホントはここの10^9のループが重いみたいだなぁ
# なんか２分累乗法を使わないといけないらしい．．．実はpythonではmathのpowに標準でついています！
Big = 10**9 + 7
#@lru_cache()
def cal_pow(num,w):
    if num==1:
        return w
    elif num==0:
        return 1
    else:
        half = num // 2
        rest = num % 2
        res = cal_pow(half,w) **2 * cal_pow(rest,w)
        res %= Big
        return res
#all = cal_pow(n,2)-1
all = pow(2,n,Big)-1

a_comb = 1
for i in range(a):
    # 逆元
    # inv_a = cal_pow(Big-2,a-i)
    inv_a = pow(a-i,Big-2,Big)
    a_comb *= (n-i)*inv_a
    a_comb %= Big
b_comb = 1
for i in range(b):
    # 逆元
    #inv_b = cal_pow(Big-2,b-i)
    inv_b = pow(b-i,Big-2,Big)
    b_comb *= (n-i)*inv_b
    b_comb %= Big
res = (all - a_comb - b_comb)
while res<0:
    res += Big
print(res)

# また出たぞ！！逆元だぁ...
# 1/x の mod p(素数) は x^(p-2)になるらしい．(フェルマーの小定理より...)
# mod(1/x) = mod(x^(p-2))

Submission status: Accepted

Solution code:
#xCy=x!/y!(x-y)!
def com(x,y):
    bunb = 1
    buns = 1
    for i in range(y):
        buns = buns * (x-i) % mod
        bunb = bunb * (i+1) % mod

    bunb_inv = pow(bunb,mod-2,mod)
    d = (buns * bunb_inv) % mod
    return buns*pow(bunb,mod-2,mod)
    
n,a,b = map(int,input().split())
mod = 10**9 + 7

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

print(ans%mod)

Submission status: Accepted

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

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

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

print((gokei-f(n, a)-f(n, b))%mod)

Submission status: Accepted

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

# calc
def nCr( n, r ):
    x = reduce( lambda a, b: a*b%dev, range(n, n-r, -1) )
    y = reduce( lambda a, b: a*b%dev, range(1, r+1,  1) )
    # mod gyakugen
    y = pow( y, dev-2, dev)
    return x * y % dev
ans  = pow(2, n, dev) - 1 - nCr(n,a) - nCr(n,b)
ans %= dev

# out
print(ans)