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:
# reply to https://atcoder.jp/contests/abc156/submissions/10292789
n, a, b = list(map(int, input().split()))

mod = 10**9 + 7

# x ** a をmodで割った余りを、O(log(a))時間で求める。
def power(x, a):
	if a == 0:
		return 1
	elif a == 1:
		return x
	elif a % 2 == 0:
		return power(x, a//2) **2 % mod
	else:
		return power(x, a//2) **2 * x % mod


# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
	return power(x, mod-2)

def binomial_coefficients2(n, k):
    ans = 1
    inv = 1
    for i in range(k):
        ans *= n-i
        inv = (inv * (i + 1)) % mod
        ans %= mod
    ans *= modinv(inv)
    return ans % mod

# (2 ** n - 1) - nCa - nCb
ans = power(2, n) - 1

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

Submission status: Accepted

Solution code:
import sys, math

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))

n, a, b = read_int()
M = pow(10, 9) + 7
sys.setrecursionlimit(300000)

def solve():
    ans = (pow(2, n, M) - 1) - kai(n, 0, a) * pow(kai(a, 0, a), M - 2, M) - kai(n, 0, b) * pow(kai(b, 0, b), M - 2, M)
    return ans % M

def kai(n, i, m):
    if i == m:
        return 1
    return (n * kai(n - 1, i + 1, m)) % M

if __name__ == "__main__":
    print(solve())

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

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

print(res%MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
from string import ascii_uppercase
import sys, bisect, math, heapq

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

n, a, b = read_int()
M = pow(10, 9) + 7
sys.setrecursionlimit(300000)
comk = [1 for _ in range(b + 2)]
def solve():
    ans = (pow(2, n, M) - 1) - kai(n, 0, a) * pow(kai(a, 0, a), M - 2, M) - kai(n, 0, b) * pow(kai(b, 0, b), M - 2, M)
    return ans % M

def kai(n, i, m):
    if i == m:
        return 1
    return (n * kai(n - 1, i + 1, m)) % M

if __name__ == "__main__":
    print(solve())

Submission status: Accepted

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

MOD = 10**9+7

def modcmb(n, r, m):
    x = 1
    y = n
    for i in range(2,r+1):
        x *= i
        x %= MOD
        y *= n-i+1
        y %= MOD
    return y * pow(x, m-2, m) % m

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

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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

def nPk(n,k):
    x = 1
    for a in range(n-k+1, n+1):
        x = x * a % MOD
    return x

def nCk(n,k):
    return nPk(n,k) * inv(kaijo[k])

MOD = 10**9+7

kaijo = [0] * 400020
kaijo[0] = 1
for i in range(1, len(kaijo)):
    kaijo[i] = kaijo[i-1] * i % MOD

# def fac(N):
#     known = { 0: 1, 1000000000: 698611116, 320000000: 30977140, 820000000: 629786193, 740000000: 375297772, 470000000: 909210595, 200000000: 933245637, 940000000: 83868974, 400000000: 429277690, 130000000: 623534362, 870000000: 256473217, 600000000: 724464507, 330000000: 522049725, 60000000: 27368307, 800000000: 203191898, 530000000: 256141983, 260000000: 135498044, 730000000: 663307737, 460000000: 275105629, 190000000: 109838563, 930000000: 778983779, 660000000: 769795511, 390000000: 917084264, 120000000: 661224977, 860000000: 116667533, 10000000: 682498929, 590000000: 131772368, 50000000: 67347853, 790000000: 748510389, 520000000: 608823837, 250000000: 112390913, 990000000: 847549272, 720000000: 852304035, 450000000: 462639908, 180000000: 547665832, 920000000: 193781724, 650000000: 92255682, 380000000: 940567523, 110000000: 281863274, 850000000: 823845496, 580000000: 848924691, 310000000: 128487469, 40000000: 723816384, 780000000: 624500515, 510000000: 97830135, 240000000: 136026497, 980000000: 377329025, 710000000: 435887178, 440000000: 780072518, 170000000: 66404266, 20000000: 491101308, 670000000: 373745190, 910000000: 172114298, 640000000: 903466878, 370000000: 148528617, 100000000: 927880474, 840000000: 814362881, 570000000: 811575797, 300000000: 668123525, 30000000: 76479948, 770000000: 671734977, 500000000: 733333339, 230000000: 268838846, 970000000: 492741665, 700000000: 957939114, 430000000: 568392357, 160000000: 195888993, 900000000: 586445753, 630000000: 456152084, 360000000: 189239124, 90000000: 888050723, 830000000: 672850561, 560000000: 637939935, 290000000: 500780548, 760000000: 624148346, 490000000: 703397904, 220000000: 368925948, 270000000: 217544623, 960000000: 965785236, 690000000: 825871994, 420000000: 358655417, 150000000: 261384175, 890000000: 245795606, 620000000: 326159309, 350000000: 386027524, 80000000: 199888908, 550000000: 696628828, 280000000: 419363534, 750000000: 217598709, 480000000: 99199382, 210000000: 724691727, 950000000: 315103615, 680000000: 606241871, 410000000: 996164327, 140000000: 970055531, 880000000: 627655552, 610000000: 272814771, 340000000: 309058615, 70000000: 625544428, 810000000: 423951674, 540000000: 141827977}

#     ans = known[ N - N % int( 1e7 ) ]
#     for i in range( N - N % int( 1e7 ) + 1, N + 1, 1 ):
#         ans = ans * i % MOD
#     return ans

n,a,b = get_nums_l()

nCa = nCk(n,a)
nCb = nCk(n,b)
ans = pow(2, n, MOD) - 1 - nCa - nCb
print(ans % (10**9 + 7))

Submission status: Accepted

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

mod = 10**9 + 7

# x ** a をmodで割った余りを、O(log(a))時間で求める。
def power(x, a):
	if a == 0:
		return 1
	elif a == 1:
		return x
	elif a % 2 == 0:
		return power(x, a//2) **2 % mod
	else:
		return power(x, a//2) **2 * x % mod


# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
	return power(x, mod-2)

mod_table = [-1] * (b+1)
mod_table[1] = 1
for i in range(2, b+1):
    mod_table[i] = (mod_table[i - 1] * (i)) % mod

def binomial_coefficients2(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans %= mod
    ans *= modinv(mod_table[k])
    return ans % mod

# (2 ** n - 1) - nCa - nCb
ans = power(2, n) - 1

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

Submission status: Accepted

Solution code:
# coding: utf-8


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


def solve(*args: str) -> str:
    n, a, b = map(int, args[0].split())
    mod = 10**9+7
    return str((pow(2, n, mod) - 1 - ncr(n, a, mod) - ncr(n, b, mod)) % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

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


def modcmb(n, k, mod):
    rtn = n
    for i in range(1, k):
        rtn = (rtn * ((n-i) % mod) * pow(i+1, mod-2, mod)) % mod

    return rtn


ans = (pow(2, n, MOD) - 1 - modcmb(n, a, MOD) - modcmb(n, b, MOD)) % MOD
print(ans if ans >= 0 else ans + MOD)

Submission status: Accepted

Solution code:
M = 10**9 + 7
n, a, b = map(int, input().split())
r = pow(2, n, M) - 1
f = c = 1
l = iter((a,b))
for i in range(b):
  f = f * (i + 1) % M
  c = c * (n - i) % M
  if i + 1 == a:
    a = b
    r -= c * pow(f, M - 2, M)
print(r % M)

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

comb = [0 for _ in range(2*10**5 + 2)]
comb[0] = 1

for i in range(2*10**5+1):
    comb[i]

def NCMMod(n, a):
    cur = n
    for i in range(2, a+1):
        cur = cur * (n-i+1) // i
    return cur % mod


fac = [-1] * (10**7+1)
finv = [-1] * (10**7+1)
inv = [-1] * (10**7+1)

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

def initNCMMod(limit):
    for i in range(2, limit):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod
initNCMMod(2*10**5 + 1)

def main():
    n, a, b = LI()
    comb[1] = n
    n_pow = power_func(2, n, mod)
    for i in range(2, 2*10**5+1):
        comb[i] = comb[i-1] * (n-i+1) * inv[i] % mod
    ans = n_pow - 1
    ans %= mod
    ans = ans - comb[a] - comb[b]
    ans %= mod
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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


def countComb(n, r, MOD=1e9 + 7):
    res = 1
    fac = 1
    for i in range(r):
        res *= n - i
        res %= MOD
        fac *= i + 1
        fac %= MOD
    return res * pow(fac, MOD - 2, MOD) % MOD


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

for k in [a, b]:
    ans -= countComb(n, k, MOD)

ans %= MOD

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import factorial
 
M = 10**9 + 7
n, a, b = map(int, input().split())
r = pow(2, n, M) - 1
c = 1
for i in range(b):
  c = c * (n - i) % M
  if i + 1 == a:
    r -= c * pow(factorial(a) % M, M - 2, M)
    a = b
print(r % M)

Submission status: Accepted

Solution code:
from math import factorial
 
M = 10**9 + 7
n, a, b = map(int, input().split())
r = pow(2, n, M) - 1
c = 1
for i in range(b):
  c = c * (n - i) % M
  if i + 1 == a:
    r -= c * pow(factorial(a), M - 2, M)
    a = b
print(r % M)

Submission status: Accepted

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

def cmb(n,k):
    x,y = 1,1
    for i in range(k):
        x = x * (n-i) % mod
        y = y * (k-i) % mod
    return x * pow(y, mod-2, mod) % mod

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

Submission status: Accepted

Solution code:
#from fractions import gcd
#mod = 10 ** 9 + 7
#N = int(input())
#a = list(map(int,input().split()))
#a,b,c = map(int,input().split())
#ans = [0] * N
#math.ceilで切り上げ
#dp = [[0] * 4 for i in range(3)] #2次元配列初期化
#dp = [[[0] * 2 for i in range(3)] for j in range(5)]
#(ord('A'))でASCII出力 Aは65
import math
import statistics
import string

def intinput():
    return int(input())

def listintinput():
    return list(map(int,input().split()))

def splitintinput():
    return map(int,input().split())

def repeatsurplus(x,y,z): #xのy乗をzで割ったあまりを高速に求める
    ret = 1
    m = y
    tmp = x
    for i in range(100000):
        if m == 1:
            ret = (ret * tmp) % z
            break
        if m % 2 == 1:
            ret = (ret * tmp) % z
        m = m // 2
        tmp = (tmp * tmp) % z
    return(ret)

def factorialsurplus(x,y,z): #xからyまでの階乗をzで割ったあまりを求める
    ret = 1
    for i in range(x, y+1):
        ret = (ret * i) % z
    return(ret)
    
    
    
n,a,b = splitintinput()
de = 10 ** 9 + 7
ans = repeatsurplus(2,n,de) - 1
ansa = factorialsurplus(n-a+1, n, de) * repeatsurplus(factorialsurplus(1, a, de), de-2, de)
ansb = factorialsurplus(n-b+1, n, de) * repeatsurplus(factorialsurplus(1, b, de), de-2, de)
print((ans-ansa-ansb+2*de)%de)

Submission status: Accepted

Solution code:
def cmd(n, r, D):
    r = min(r, n-r)
    upper = 1
    lower = 1
    counter = 1
    while counter <= r:
        upper = (upper * (n - counter +1)) % D
        lower = (lower * counter) % D
        counter = counter + 1
    return (upper * pow(lower, D - 2, D)) % D

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

N = pow(2, n, D)
P = cmd(n, a, D)
Q = cmd(n, b, D)
Ans = (N - 1 - P - Q) % D
print(Ans)

Submission status: Accepted

Solution code:
def d_bouquet(MOD=10**9 + 7):
    from functools import reduce
    N, A, B = [int(i) for i in input().split()]

    def comb(m, r):
        numerator = reduce(lambda x, y: x * y % MOD, range(m, m - r, -1))
        denominator = reduce(lambda x, y: x * y % MOD, range(1, r + 1))
        return (numerator * pow(denominator, MOD - 2, MOD)) % MOD

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

print(d_bouquet())

Submission status: Accepted

Solution code:
MOD = 10**9+7
def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

def cmb(n,k,p):
    if n < k:
        return 0
    if n-k<k:
        k=n-k

    # 分母
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD

    # 逆行列
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

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

# 2**n-1
total = power_func(2,n,MOD)-1
print((total-cmb(n,a,MOD)-cmb(n,b,MOD))%MOD)

Submission status: Accepted

Solution code:
#pが素数の時、p未満の数の積xについてx^(p-1)=1(mod p) <=> x^(p-2)=1/x(mod p) (オイラの小定理)
#ここでpは素数なので、p以下の数a,b,nにおいてcmb(n,a)≡n!/((n-a)!*a!)≡((n-a+1)*…*n)/(a!)≡((n-a+1)*…*n)(a!)^(p-2) (mod p)
#あとは((n-a+1)*…*n)(a!)^(p-2) (mod p)を繰り返し2乗法でO(log(p))で求められる…らしいが普通にpow(n,r,mod)つよそう

def modcmb(n,r,mod):
    upper=1
    for i in range(n-r+1,n+1,1):
        upper=(upper*i)%mod
    rfrac=1
    for i in range(1,r+1,1):
        rfrac=(rfrac*i)%mod
    pwrfrac=pow(rfrac,mod-2,mod)
    return (upper*pwrfrac)%mod

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

print((pow(2,n,p)-1-modcmb(n,a,p)-modcmb(n,b,p))%p)

Submission status: Accepted

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

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

def com(n,k,mod=10**9+7):
    u = 1
    s = 1
    for i in range(n,n-k,-1):
        u = u*i % mod
    for i in range(k,0,-1):
        s = s*i % mod
    return u * modinv(s)

c = pow(2,n,mod)
c -= 1
c -= com(n,a)
c -= com(n,b)
print(c%mod)

Submission status: Accepted

Solution code:
def loop_pow(x,n,mod):
    if n==0:
        return 1
    if n%2==0:
        t=loop_pow(x,n//2,mod)
        return (t*t)%mod
    return x*loop_pow(x,n-1,mod)%mod

def com(N,K,mod):
    n=N
    k=K
    up=1
    down=1
    for _ in range(K):
        up*=n
        up%=mod
        n-=1
    for _ in range(K):
        down*=k
        down%=mod
        k-=1
    down=loop_pow(down,10**9+5,mod)
    return up*down%mod

def main():
    N,a,b=map(int,input().split())
    mod=10**9+7
    t=(loop_pow(2,N,mod)-1-com(N,a,mod)-com(N,b,mod))%mod
    print(t)

if __name__=="__main__":
    main()

Submission status: Accepted

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

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

n,a,b=mii()

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


def p_f(a,n,p):
    bi=str(format(n,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
            res=(res*a) %p
    return res
def nCk(n, k, mod=10 ** 9 + 7):
    if n < k:
        return 0
    k = min(k, n - k)
    numer = 1
    for x in range(n - k + 1, n + 1):
        numer = (numer * x) % mod
    denom = 1
    for x in range(1, k + 1):
        denom = (denom * x) % mod
    return numer * pow(denom, mod - 2, mod) % mod
 

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, a, b = MAP()

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

ans = power(2, n)-1

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def loop_pow(x,n,mod):
    if n==0:
        return 1
    if n%2==0:
        t=loop_pow(x,n//2,mod)
        return (t*t)%mod
    return x*loop_pow(x,n-1,mod)

def com(N,K,mod):
    n=N
    k=K
    up=1
    down=1
    for _ in range(K):
        up*=n
        up%=mod
        n-=1
    for _ in range(K):
        down*=k
        down%=mod
        k-=1
    down=loop_pow(down,10**9+5,mod)
    return up*down%mod

def main():
    N,a,b=map(int,input().split())
    mod=10**9+7
    t=(loop_pow(2,N,mod)-1-com(N,a,mod)-com(N,b,mod))%mod
    print(t)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def comb(n, r, p):
    ret = 1
    while 1:
        if (r == 0):
            break
        N = n % p
        R = r % p
        if N < R:
            return 0
        for i in range(R):
            ret = ret * (N-i) % p
        imul = 1
        for i in range(R):
            imul = imul * (i+1) % p
        ret = ret * modinv(imul, p) % p
        n //= p
        r //= p
    return ret

mod = 10 ** 9 + 7
N, A, B = map(int, input().split())
tmp = (2 ** N - 1) % mod 
a = comb(N, A, mod)
b = comb(N, B, mod)
print(((tmp + mod) - a - b ) % mod)

Submission status: Accepted

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

MOD = 1000000007


def combination(n, r):
    r = min(r, n - r)

    num = 1
    den = 1

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

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


def func(a, n, p):
    bi = str(format(n, "b"))
    res = 1

    for i in range(len(bi)):
        res = (res * res) % p
        if bi[i] == "1":
            res = (res * a) % p

    return res


s = func(2, n, MOD) - 1
xa = combination(n, a)
xb = combination(n, b)

p = (s - xa - xb) % MOD

if p < 0:
    print(p + MOD)
else:
    print(p)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def combMod(n, r, p):
    numer = 1
    denom = 1
    for i in range(1, r+1):
        numer = numer * (n-r+i) % p
        denom = denom * i % p
    return numer * pow(denom, p-2, p) % p

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

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

mod=10**9+7

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

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

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

Submission status: Accepted

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

p = 10**9 + 7

def cmb(n, r, p):
    x = 1
    y = 1
    for i in range(r):
        x = x*(n-i) % p
        y = y*(r-i) % p
    return x*pow(y, p-2, p) % p

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

print(ans%p)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import setrecursionlimit

setrecursionlimit(2 * 10 ** 9)

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

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


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


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


print(int(ans % mod))

Submission status: Accepted

Solution code:
M = 10**9 + 7
n, a, b = map(int, input().split())
r = pow(2, n, M) - 1
f = c = 1
for i in range(b):
  f = f * (i + 1) % M
  c = c * (n - i) % M
  if i + 1 ==a or i + 1 == b:
    r -= c * pow(f, M - 2, M)
print(r % M)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
m=10**9+7
def cmb(x,y):
    c=1
    for i in range(1,y+1):
      c=(c*(x-i+1)*pow(i,m-2,m))%m
    return c
print((pow(2,n,m)-1-cmb(n,a)-cmb(n,b))%m)

Submission status: Accepted

Solution code:
M = 10**9 + 7
n, a, b = map(int, input().split())
r = pow(2, n, M) - 1
f = c = 1
for i in range(b):
  f = f * (i + 1) % M
  c = c * (n - i) % M
  if a != i + 1 != b:
    continue
  r -= c * pow(f, M - 2, M)
print(r % M)

Submission status: Accepted

Solution code:
from collections import defaultdict
from functools import reduce

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

MOD = 10 ** 9 + 7

def mul(a, b):
  return ((a % MOD) * (b % MOD)) % MOD

def power(x, y):
  if y == 0:
    return 1
  elif y == 1:
    return x % MOD
  elif y % 2 == 0:
    return power(x, y // 2) ** 2 % MOD
  else:
    return mul(power(x, y // 2) ** 2, x)

def div(a, b):
  return mul(a, power(b, MOD - 2))

def dict1():
  return {0: 1}

numer_cache = defaultdict(dict1)
denom_cache = dict1()

def combinations_count(n, r):
  r = min(r, n - r)

  r2 = max(x for x in numer_cache[n] if x <= r)
  if r2 < r:
    numer_cache[n][r] = reduce(mul, range(n - r2, n - r, -1), numer_cache[n][r2])
  numer = numer_cache[n][r]

  r3 = max(x for x in denom_cache if x <= r)
  if r3 < r:
    denom_cache[r] = reduce(mul, range(r3 + 1, r + 1), denom_cache[r3])
  denom = denom_cache[r]

  return div(numer, denom)

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

if r1 > r2:
  r1, r2 = r2, r1

print((power(2, n) - 1 - combinations_count(n, r1) - combinations_count(n, r2)) % MOD)

Submission status: Accepted

Solution code:
from functools import reduce

def main():
    n, a, b = map(int,input().split())
    mod = 10 ** 9 + 7
    def f(k):
        num = reduce(lambda x,y: x * y % mod, range(n, n-k, -1))
        den = reduce(lambda x,y: x * y % mod, range(1, k+1))
        return num * pow(den, mod-2, mod) % mod
    ans = pow(2,n,mod) - f(a) - f(b) - 1
    ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from math import factorial


def comb(n,k,p):
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    mink = min(k,n-k)
    a = 1
    b = 1
    for i in range(mink):
        a = a * (n-i) % p
        b = b * (i+1) % p

    return (a*power_func(b,p-2,p))%p


def power_func(a,b,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 main():
    n,a,b = map(int,input().split())

    mod = 10 ** 9 + 7

    temp1 = comb(n,a,mod)
    temp2 = comb(n,b,mod)

    res = power_func(2,n,mod) - 1
    res -= temp1 + temp2
    res %= mod

    print(res)



main()

Submission status: Accepted

Solution code:
n,a,b=map(int,input().split())
N=10**9+7
def modpow(a,n,p):#a^n mod p ,O(log n)
    res=1
    while n>0:
        if n&1:#１とのビット論理積が１、つまり奇数
            res=res*a%p
        a=a*a%p
        n>>=1
        #ビットの右シフト_2進数表記のnを小数点を固定して右に１桁ずらす_１桁小さくなる
    return res
cmban=1
faca=1
cmbbn=1
facb=1
for i in range(a):
    cmban=cmban*(n-i)%N
    faca=faca*(i+1)%N
for i in range(b):
    cmbbn=cmbbn*(n-i)%N
    facb=facb*(i+1)%N
print((modpow(2,n,N)-cmban*modpow(faca,N-2,N)%N-cmbbn*modpow(facb,N-2,N)%N-1)%N)

Submission status: Accepted

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

mod = int(1e9+7)
def comb(n, r, mod):
    bunsi = 1
    bunbo = 1
    for i in range(r):
        bunsi = (bunsi * (n - i)) % mod
        bunbo = (bunbo * (r - i)) % mod
    return (bunsi*pow(bunbo, mod-2, mod)) % mod

print((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 cmb(n, r,mod):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    #X//Y
    X=1
    Y=1
    for i in range(r):
        X*=(n-i)
        X%=mod
        Y*=(i+1)
        Y%=mod
        
    inv=pow(Y,mod-2,mod)
    return (X*inv)%mod
        
        


allp=pow(2,n,mod)-1
ans=(allp-cmb(n,a,mod)-cmb(n,b,mod))%mod
if n==2:
    ans=0

print(ans)

Submission status: Accepted

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

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

for i in range(a, b):
  x1 = x1 * (n-i) % mod
  y1 = y1 * (i+1) % mod
B = (x1 * pow(y1, mod - 2, mod)) % mod

print((S - A - B) % mod)