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:
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD

class Inv:
  def __init__(s, mod):
    s.MOD = mod
  def modpow(s, a, n):
    res = 1
    while n > 0:
      if n & 1:
        res = res * a % s.MOD
      a = a * a % s.MOD
      n >>= 1
    return res
  def invx(s, a):
    return s.modpow(a, s.MOD - 2)
  def invL(s, a, n):
    ia = s.invx(a)
    L = [1] * (n + 1)
    for i in range(1, n + 1):
      L[i] = L[i - 1] * ia % s.MOD
    return L

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

inv = Inv(MOD)
com = comb(max(a, b) + 1, MOD)

ans = inv.modpow(2, n) - 1

def nasu(n, a):
  ans = 1
  for i in range(a):
    ans = ans * (n - i) * com.I[i + 1] % MOD
  return ans

ans = ans - nasu(n, a)
ans = ans - nasu(n, b)

while ans < 0:
  ans += MOD

print(ans)

Submission status: Accepted

Solution code:
M = 10 ** 9 + 7

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

# negative
def calc_inverse(n, law):
	if n == 1:
		return 1
	
	pre_r = law
	pre_x = 0
	pre_y = 1
	cur_r = n
	cur_x = 1
	cur_y = 0
	
	while True:
		d = pre_r // cur_r
		r = pre_r % cur_r
		
		nxt_r = r
		nxt_x = pre_x - d * cur_x
		nxt_y = pre_y - d * cur_y
		
		if nxt_r == 1:
			ret = nxt_x
			while ret < 0:
				ret += law;
			return ret;
		elif nxt_r == 0:
			return None
		
		pre_r = cur_r;
		pre_x = cur_x;
		pre_y = cur_y;
		cur_r = nxt_r;
		cur_x = nxt_x;
		cur_y = nxt_y;

invs = [None]
for i in range(1, max(a, b) + 1):
	invs.append(calc_inverse(i, M))

def c(a, b):
	n = 1
	
	for i in range(a - b + 1, a + 1):
		n = (n * i) % M
	
	for i in range(1, b + 1):
		n = (n * invs[i]) % M
	
	return n

print((pow(2, n, M) - c(n, a) - c(n, b) - 1) % M)

Submission status: Accepted

Solution code:
n,a,b = map(int, input().split())
mod = 10 ** 9 + 7
ans = pow(2,n,mod) - 1
MIN = min(a,b)
MAX = max(a,b)
min_c = 1
max_c = 1
child = 1
mother = 1
for i in range(MIN):
  child = (child * (n-i)) % mod
  mother = (mother * (i+1)) % mod
min_c = (child * pow(mother,mod-2,mod)) % mod
for i in range(MIN,MAX):
  child = (child * (n-i)) % mod
  mother = (mother * (i+1)) % mod
max_c = (child * pow(mother,mod-2,mod)) % mod
ans = (ans - min_c - max_c) % mod
print(ans)

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
MOD = 10 ** 9 + 7

factorial = [1, 1]  # 元テーブル
inverse = [1, 1]  # 逆元テーブル
inverse_from = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, 2 * 10 ** 5 + 10):
    factorial.append((factorial[-1] * i) % MOD)
    inverse_from.append((-inverse_from[MOD % i] * (MOD // i)) % MOD)
    inverse.append((inverse[-1] * inverse_from[-1]) % MOD)


def calc(n):
    ret = 1
    for i in range(n):
        ret = ret * (N - i) % MOD
    return ret * inverse[n] % MOD


print(max(0, (pow(2, N, MOD) - ((calc(A) + calc(B)) % MOD) - 1) % MOD))

Submission status: Accepted

Solution code:
MOD = 1000000007

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

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

def com(n, k):
    x = 1
    for i in range(k):
        x *= n - i
        x *= mod_inv(i+1,MOD)
        x %= MOD
    return x

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

x = pow(2, n, MOD)
y = 1 + com(n, a) + com(n, b)
y %= MOD

print((x+MOD-y)%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)-ans1-ans2-1) % mod)


main()

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
from bisect import *
import copy

n,a,b=map(int,input().split())
mod=10**9+7
fac=[0,1]

num=n
for i in range(2,b+1):
    num=num*pow(i,mod-2,mod)*(n+1-i)%mod
    #print(num,i)
    if a==i:
        numa=num
    if b==i:
        numb=num
if a==1:
    numa=n
#print(numa,numb)
print((pow(2,n,mod)-numa-numb)%mod-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# %%
from functools import reduce

# %%
stdin = open(0)

# %%
N, A, B = map(int, stdin.read().split())
MOD = 10 ** 9 + 7

# %%


def f(A):
    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))
    return num * pow(den, MOD - 2, MOD) % MOD


# %%
answer = pow(2, N, MOD) - f(A) - f(B) - 1
answer %= MOD
print(answer)

Submission status: Accepted

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

MOD = pow(10, 9) + 7


def my_pow(n, p, m):
    """
    calculate n^p (mod m) effectively
    """
    if p == 0:
        return 1
    elif p%2 == 0:
        return ((my_pow(n, p//2, m)) ** 2) % m
    else:
        return (my_pow(n, p-1, m) * n) % m


def comb(n, r, m):
    """
    calculate nCr using the factorial table
    return: nCr % MOD
    """
    numerator = 1
    for i in range(n-r+1, n+1):
        numerator = (i * numerator) % m
    denominator = 1
    for i in range(1, r+1):
        denominator = (i * denominator) % m

    # a^p-1 ≡ 1 (mod p) (p: prime)
    # a^p-2 ≡ a^-1
    fermat = my_pow(denominator, m-2, m)
    return (numerator * fermat) % m


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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
def examA():
    N, R = LI()
    ans = R+100*max(0,(10-N))
    print(ans)
    return

def examB():
    N, K = LI()
    ans = 1
    while(N>=K):
        N //=K
        ans += 1
    print(ans)
    return

def examC():
    N = I()
    X = LI()
    ans = inf
    for i in range(101):
        cur = 0
        for x in X:
            cur += (i-x)**2
        ans = min(ans,cur)
    print(ans)
    return

def examD():
    def cmb(n, r, mod):
        cur = 1
        for i in range(r):
            cur *= (n-i)
            cur %= mod
        for i in range(r):
            cur *= pow(i+1,mod-2,mod)
            cur %= mod
        return cur
    n, a, b = LI()
    ans = pow(2,n,mod) - cmb(n,a,mod) - cmb(n,b,mod) -1
    ans = (ans+mod*2)%mod
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Accepted

Solution code:
N,A,B = map(int,input().split())
MOD = 10**9+7

ans = pow(2,N,MOD)-1
Ab,Ac = 1,1
for i in range(A):
    Ac = ((N-i)*Ac)%MOD
    Ab = (Ab*(i+1))%MOD
Bb,Bc = 1,1
for i in range(B):
    Bc = ((N-i)*Bc)%MOD
    Bb = (Bb*(i+1))%MOD
A = Ac * pow(Ab,MOD-2,MOD)
B = Bc * pow(Bb,MOD-2,MOD)


ans = (ans-A-B)%MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9+7

def nCr(n, r, mod=MOD):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

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

ans = pow(2, n, MOD) - 1 - nCr(n, a) - nCr(n, b)
ans += MOD * 2
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __imod__(self, other):
        self.x %= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __mod__(self, other):
        return (
            mint(self.x % other.x) if isinstance(other, mint) else
            mint(self.x % other)
        )
    def __truediv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rmod__(self, other):
        return (
            mint(other.x % self.x) if isinstance(other, mint) else
            mint(other % self.x)
        )
    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )



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

ans+=mint(2)**n-1

minus=mint(1)
for i in range(a):
    minus*=n-i
    minus/=i+mint(1)

ans-=minus

minus=mint(1)
for i in range(b):
    minus*=n-i
    minus/=i+mint(1)

ans-=minus

print(ans)

Submission status: Accepted

Solution code:
def factorial(n, r, mod=10**9+7):
    a = 1
    for i in range(n, n-r, -1):
        a = a * i % mod
    return a


def power(n, r, mod=10**9+7):
    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=10**9+7):
    if n < k or k < 0:
        result = 0
    else:
        a = factorial(n, k, mod=mod)
        b = factorial(k, k, mod=mod)
        result = a * power(b, mod-2, mod=mod) % mod
    return result


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

class InverseTable:
    __slots__ = ['In', 'fac', 'Ifac']

    def __init__(self, mod, maxnum):
        self.In = [0, 1]; self.fac = [1, 1]; self.Ifac = [1, 1]
        for i in range( 2, maxnum + 1 ):
            self.In.append( ( -self.In[mod % i] * (mod//i) ) % mod )
            self.fac.append( ( self.fac[-1] * i ) % mod )
            self.Ifac.append( (self.Ifac[-1] * self.In[-1]) % mod )
        
    def cmb(self, n, r):
        if ( r<0 or r>n ): return 0
        r = min(r, n-r)
        over = 1
        for i in range(n,n-r,-1):
          over *= i; over %= mod
        
        return over * self.Ifac[r]  % mod
        # return self.fac[n] * self.Ifac[r] * self.Ifac[n-r] % mod
    
    def per(self, n, r):
        if ( r<0 or r>n ): return 0
        return self.fac[n] * self.Ifac[n-r] % mod

invt = InverseTable(mod, 10**6)
# maxnum=10**6だとテーブル生成に200ms程かかるので（Pythonだと1000msほど）
# 最大生成領域は問題ごとに要検討

from operator import mul
from functools import reduce

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

def ncr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i 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 *= numerator[k]
            result %= mod
    return result

# N = 10000
# cnt = 0
# for a in xrange(N + 1):
#     cnt += ncr(N, a)

# print cnt == 2 ** N

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def modInverse(a, p):
    return pow(a, p - 2, p)


def modBinomial(n, k, p):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % p

    denominator = 1
    for i in range(1, k + 1):
        denominator = (denominator * i) % p

    return (numerator * modInverse(denominator, p)) % p


def main():
    N, A, B = [int(x) for x in input().split()]

    MOD = 10 ** 9 + 7

    ans = pow(2, N - 1, MOD)
    ans = ans * 2
    a = modBinomial(N, A, MOD)
    b = modBinomial(N, B, MOD)
    print((ans - a - b) % MOD - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 10 ** 9 + 7

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

ans = pow(2, n, MOD) - 1
ans -= combination(n, a)
ans %= MOD
ans -= combination(n, b)
ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def nCr(n, r, MOD):
    """ 組み合わせの数(大きいnに対して使用する。計算量はr) """

    if n < r: return 0
    # 10C7 = 10C3
    r = min(r, n-r)
    num = den = 1
    # 分子の計算
    for i in range(n, n-r, -1):
        num *= i % MOD
        num %= MOD
    # 分母の計算
    for i in range(r, 0, -1):
        den *= i % MOD
        den %= MOD
    # logがつくため、MOD除算は最後の1回だけにする
    return num * pow(den, MOD-2, MOD) % MOD
N, a, b = MAP()

ans = pow(2, N, MOD) - 1 - nCr(N, a, MOD) - nCr(N, b, MOD)
print(ans%MOD)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']
Yn=['Yes','No']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
#ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo


show_flg=False
show_flg=True

ans=0

n,a,b=LI()
cm=Comb(2*10**5+20)
ans=pow(2,n,mo)-1

def f(x):
    t=1
    for i in range(x):
#        print(x,(n-i,i+1,cm.invf(i+1)))
        t*=n-i
        t%=mo
    t*=cm.invf(x)
    return t%mo

ans-=f(a)+f(b)

print(ans%mo)

Submission status: Accepted

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

mod = 10**9+7

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

c = 1
for i in range(a):
    c *= (n-i)
    c *= pow(i+1, mod-2, mod)
    c %= mod

ans -= c
c = 1
for i in range(b):
    c *= (n-i)
    c *= pow(i+1, mod-2, mod)
    c %= mod

ans -= c
ans += 2*(10**9+7)

print(ans%mod)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
inpl = lambda: list(map(int,input().split()))
def inv_mod(a, p=10**9+7):
    p = abs(p)
    a %= p
    stack = []
    p0 = p
    while a > 1:
        d, a, p = p//a, p%a, a
        stack.append(d)
    x, y = 1, 0
    while stack:
        d = stack.pop()
        x, y = y-d*x, x
    return x % p0

def comb_mod(n,k,p):
    ans = 1
    k = min(k,n-k)
    if k < 0:
        return 0
    for i in range(k):
        ans = ans * (n-i) * inv_mod(k-i,p) % p
    return ans

n, a, b = inpl()
ans = pow(2,n,MOD) - 1
ans -= comb_mod(n,a,MOD)
ans -= comb_mod(n,b,MOD)
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n, a, b = map(int, raw_input().split())
mod = 10**9 + 7
ans = pow(2, n, mod) - 1
anum = 1
for i in range(n, n - a, -1):
	anum = (anum*i)%mod
aden = 1
for i in range(1, a + 1):
	aden = (aden*i)%mod
aden = pow(aden, mod - 2, mod)
anum *= aden
anum %= mod
ans -= anum
ans %= mod

if a != b:
	anum = 1
	for i in range(n, n - b, -1):
		anum = (anum*i)%mod
	aden = 1
	for i in range(1, b + 1):
		aden = (aden*i)%mod
	aden = pow(aden, mod - 2, mod)
	anum *= aden
	anum %= mod
	ans -= anum
	ans %= mod

print ans

Submission status: Accepted

Solution code:
def ncr(n, r):
    num = den = 1

    for i in range(r):
        num = (num * (n - i)) % MOD
        den = (den * (i + 1)) % MOD

    return (num * pow(den, MOD - 2, MOD)) % MOD

MOD = 10 ** 9 + 7

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

x = pow(2, n, MOD)

print((x - ncr(n, a) - ncr(n, b) - 1) % MOD)

Submission status: Accepted

Solution code:
MOD = 1000000007

class Factorial():
    def __init__(self,N,n,mod):
        self.N = N
        self.mod = mod
        self.factorial = [0 for _ in range(n+1)]
        self.inv = [0 for _ in range(n+1)]
        self.factorial[0] = 1
        self.inv[0] = 1
        self.factorial_ = [0 for _ in range(n+1)]
        self.factorial_[0] = N
        for i in range(n):
            self.factorial[i+1] = self.factorial[i]*(i+1)%mod
        self.inv[n] = pow(self.factorial[n],mod-2,mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i+1]*(i+1)%mod
        for i in range(n):
            self.factorial_[i+1] = self.factorial_[i]*(N-i-1)%mod
    def comb(self,m,k): #組み合わせ 0<=k<=m<=n 重複組み合わせはcomb(m+k-1,k)
        return self.factorial[m]*self.inv[k]*self.inv[m-k]%self.mod
    def comb_(self,k):
        return self.factorial_[k-1]*self.inv[k]%self.mod

N,A,B = map(int,input().split())

F = Factorial(N,200010,MOD)

ans = pow(2,N,MOD) - F.comb_(A) - F.comb_(B) -1

print(ans%MOD)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
mod = int(1e+9) + 7
def extgcd(a, b):
  if b == 0:
    return 1, 0
  else:
    x, y, u, v, k, l = 1, 0, 0, 1, a, b
    while l != 0:
      x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
      k, l = l, k % l
    return x
def inved(x):
  a = extgcd(x, mod)
  return a % mod
def doubling(N, M):
  y = 1
  base = N
  while M != 0:
    if M % 2 == 1:
      y *= base
      y %= mod
    base *= base
    base %= mod
    M //= 2
  return y
S = [inved(i+1) for i in range(b)]
A = doubling(2, n)
A = (A - 1) % mod
proda, prodb = 1, 1
for i in range(a):
  proda *= ((n - i) * S[i]) % mod
  proda %= mod
for i in range(b):
  prodb *= ((n - i) * S[i]) % mod
  prodb %= mod
print((A - proda - prodb) % mod)

Submission status: Accepted

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

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

ans = 0
m = 10**9+7

all_num = large_expo(2,n,m)-1

minus1 = 1
minus2 = 1

inv_m = [0]+[1]
for i in range(2,max(a,b)+1):
  inv_m += [inv_m[m % i] * (m - int(m / i)) % m]


for i in range(a):
    minus1 *= (n-i)
    minus1 = minus1 * inv_m[i + 1]
    minus1 %= m

for i in range(b):
    minus2 *= (n-i)
    minus2 = minus2 * inv_m[i + 1]
    minus2 %= m

# print(all_num,minus1,minus2)
# print(minus1+minus2)
# print((all_num-minus1-minus2))
# print((all_num-minus1-minus2)+2*m)
print((all_num-minus1-minus2)%m)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

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

ans = pow(2,n,MOD) -1 - comb_mod(n,a) - comb_mod(n,b) %MOD
ans = (ans + MOD ) % MOD
print(ans)

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
mod = 10**9 + 7
double = [2]
for _ in range(30):
  tmp = double[-1] ** 2
  tmp %= mod
  double.append(tmp)
#print(double)
ans = 1
m = int(n)
for i in range(32):
  if m % 2 == 1:
    ans *= double[i]
    ans %= mod
  m //= 2
  if m == 0:
    break
def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    y %= mod
    x -= mod % x
  return y
ta = 1
for i in range(a):
  ta *= n-i
  ta %= mod
  ta *= inv(i+1)
  ta %= mod
tb = 1
for i in range(b):
  tb *= n-i
  tb %= mod
  tb *= inv(i+1)
  tb %= mod
ans -= ta
ans -= tb
ans -= 1
ans %= mod
print(ans)
#print(inv(5))

Submission status: Accepted

Solution code:
def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod


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

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


W = 1
X = 1
for i in range(a):

    W *= i + 1

    X *= n - i

    W %= mod
    X %= mod

ans -= X * inverse(W,mod)
ans %= mod

W = 1
X = 1
for i in range(b):

    W *= i + 1

    X *= n - i

    W %= mod
    X %= mod

ans -= X * inverse(W,mod)

print (ans % mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


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

    numer = [n - r + k + 1 for k in range(r)]
    denom = [k + 1 for k in range(r)]

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

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

    return result


def solve(n: int, a: int, b: int):

    ans = pow(2, n, MOD)-1
    ans -= cmb(n, a)
    ans %= MOD
    ans -= cmb(n, b)
    ans %= MOD
    print(ans)
    return


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:
n,a,b=map(int, input().split())
MOD=10**9+7

def comb(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

ans=(pow(2,n,MOD)-1)%MOD
ans=(ans+MOD-comb(n,a))%MOD
ans=(ans+MOD-comb(n,b))%MOD

print(ans)