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
import numpy as np
sys.setrecursionlimit(10 ** 7)

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

MOD = 10 ** 9 + 7

def myPow(x, n, MOD):
    if n == 0:
        return 1

    res = 1
    while(n > 0):
        if n & 1 == 1:
            res = res * x % MOD

        x = x * x % MOD
        n = n >> 1

    return res


ans = myPow(2, N, MOD)
ans -= 1

def cumprod(arr, MOD):
    L = len(arr)
    Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]
        arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]
        arr[n] %= MOD
    return arr.ravel()[:L]


def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64)
    x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64)
    x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv


fact, fact_inv = make_fact(B + 10, MOD)

arr = cumprod(list(range(N, N-B, -1)), MOD)

a = arr[A - 1] * fact_inv[A]
a %= MOD
b = arr[B-1] * fact_inv[B]
b %= MOD

# print(mb)
# print(fact_inv)

'''
a = ma * fact_inv[A]
a %= MOD

b = mb * fact_inv[B]
b %= MOD
'''

ans -= (a + b)
ans %= MOD

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

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

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

Submission status: Accepted

Solution code:
# pythonではpow(x, y, mod)で同様のことができるので
# 今後、実装は不要
def pow(x, y):
    if y == 0:
        return 1
    if y % 2 == 0:
        ans = pow(x ** 2 % INF, y // 2)
    else:
        ans = (pow(x ** 2 % INF, y // 2) * x) % INF
    return ans

def comb_big(m, k):
    x, y = 1, 1
    for i in range(k):
        x = x * (m - i) % INF
        y = y * (k - i) % INF
    return x * pow(y, INF - 2) % INF

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

ans = pow(2, n) - 1 - comb_big(n, a) - comb_big(n, b)
print((ans + INF) % INF)

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:
    r -= c * pow(f, M - 2, M)
print((r - c * pow(f, M - 2, M)) % M)

Submission status: Accepted

Solution code:
import sys,math

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]


def main():
	n,a,b = MI()
	mod = 10 ** 9 + 7

	def f(n,r,mod):
		r = min(r,n-r)
		x = y = 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) - f(n,a,mod) - f(n,b,mod) - 1)%mod
	ans += mod if ans < 0 else 0
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def cmb(n,r,mod):
    numeator = 1
    for i in range(n-r+1,n+1):
        numeator = (i*numeator)%mod
    denominator = 1
    for i in range(1,r+1):
        denominator = (i*denominator)%mod
    fermat = pow(denominator,mod-2,mod)
    return (numeator*fermat)%mod
n,a,b=map(int,input().split(' '))
mod = 10**9+7
ans = pow(2,n,mod)-1
ans -= cmb(n,a,mod)+cmb(n,b,mod)
print(ans%mod)

Submission status: Accepted

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

mod = 10**9 + 7
res = pow(2, n, mod)

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


A = cmb(n, a, mod)
B = cmb(n, b, mod)

print((res - A - B - 1) % mod)

Submission status: Accepted

Solution code:
import sys,math

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]


def main():
	n,a,b = MI()
	mod = 10 ** 9 + 7

	def f(n,r,mod):
		r = min(r,n-r)
		x = y = 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) - f(n,a,mod) - f(n,b,mod) - 1
	ans += mod if ans < 0 else 0
	ans += mod if ans < 0 else 0
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
s=list(map(int,input().split()))
ans=0
ad=1
mod=10**9+7
def comb(x):
  a=b=1
  for i in range(x):
    a=a*(s[0]-i)%mod
    b=b*(i+1)%mod
  return a*pow(b,mod-2,mod)%mod
ans=pow(2,s[0],mod)
print((ans-1-comb(s[1])-comb(s[2]))%mod)

Submission status: Accepted

Solution code:
#!python3.4
# -*- coding: utf-8 -*-
# abc156/abc156_d
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

MAX = 2 * 10**5 + 10
MOD = 10**9 + 7

fac = [1, 1] + [0] * MAX
for i in range(2, MAX):
    fac[i] = fac[i - 1] * i % MOD

def getP(n, a, b):
    _n = n
    for i in range(1, a):
        _n = (_n * (n - i)) % MOD
    P_a = _n
    for i in range(a, b):
        _n = (_n * (n - i)) % MOD
    P_b = _n
    return (P_a, P_b)

def main():
    n, a, b = i2nn()
    all_C = (pow(2, n, MOD) - 1) % MOD
    P_a, P_b = getP(n, a, b)
    C_a = (P_a * pow(fac[a], MOD-2, MOD)) % MOD
    C_b = (P_b * pow(fac[b], MOD-2, MOD)) % MOD
    print((MOD + all_C - C_a - C_b) % MOD)
    return

main()

Submission status: Accepted

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

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

MOD = 10**9 + 7
res = modpow(2, n, MOD) - 1 

def combi(n, k):
    p, q = 1, 1
    for i in range(1, k + 1):
        p = p * (n - i + 1) % MOD
        q = q * i % MOD
    return p * modpow(q, MOD - 2, MOD)

res -= combi(n, a) + combi(n, b)
print(res%MOD)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7 
def cmb(n, r, mod):
    r = min(r, n -r)
    if r == 0: return 1
    over, under = 1, 1
    for i in range(1, r+1):
        over = over * (n-i+1) % mod
        under = under * i % mod
    inv = pow(under, mod-2, mod)
    return over * inv % mod

n, a, b = 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:

def mod_inverse(a, p):
    return pow(a, p-2, p)  # フェルマーの小定理より

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

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

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

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

    ans = pow(2, n, p) - mod_binominal(n, a, p) - mod_binominal(n, b, p) - 1
    print((ans + p) % p)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def cmb(n, r, MOD):
    r = min(r, n - r)
    n1 = n + 1
    numerator = denominator = 1
    for i in range(1, r + 1):
        numerator = (numerator * (n1 - i)) % MOD
        denominator = (denominator * i) % MOD
    return (numerator * pow(denominator, MOD - 2, MOD)) % MOD


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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

def modcmb(n, r, mod):
    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, mod-2, mod) % mod


def main():
    n,a,b = map(int, readline().split())

    if n == 2:
        print(0)
        exit()

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

#繰り返し二乗法
def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        x %= mod
        n //= 2
    return K * x

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

ans = (pow_k(2,n) - 1)%mod
A = cmb(n, a)
B = cmb(n, b)

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

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

def ncr(n, r):
    a = 1
    b = 1
    for i in range(r):
        a = (a * (n - i) % MOD)
        b = (b * (r - i) % MOD)

        # a *= ((n - i) % MOD)
        # b *= ((r - i) % MOD)

    return a * pow(b, MOD - 2, MOD) % MOD

N, A, B = MI()

s = pow(2, N, MOD) - 1
ab = (ncr(N, A) + ncr(N, B)) % MOD

print((s - ab)  % MOD)

Submission status: Accepted

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

mod = 1000000007
width = 1000
table = [ 1, 128233642, 993191796, 246084337, 175673566, 883787401, 470931556, 119995528, 225567908, 757928892, 250015370, 913979655, 754758, 207715304, 680281231, 630322311, 642314838, 834078844, 599226039, 918470969, 777847830, 188150013, 936569805, 609321015, 803755964, 506567627, 733034722, 525152703, 125374323, 229063893, 64381203, 331225140, 239876153, 938119791, 238030663, 963888220, 269540267, 288849729, 868543185, 176093029, 129227219, 57384053, 510217116, 42904984, 1283621, 229119361, 122050053, 83923714, 99441611, 723598838, 664720426, 824990192, 899870337, 994461247, 78470227, 616312139, 585511607, 457301297, 774218347, 24761471, 220551652, 797724439, 42696969, 433164019, 825454299, 183907026, 881797659, 823559228, 703904407, 624713517, 805011386, 175293956, 157911929, 315160646, 59387184, 711105445, 710926865, 239798930, 734168782, 513146799, 71626953, 883937988, 613778426, 107738376, 960564286, 84887701, 771212964, 71595332, 319321717, 980960223, 368173468, 67320689, 862499851, 864972828, 48646097, 670160814, 725736339, 790163830, 663423088, 255691818, 388742192, 305094892, 522669454, 472392039, 946047214, 445919328, 748072600, 923340633, 932008794, 641127822, 633943807, 473400148, 55310953, 397250219, 468376442, 583215176, 797665328, 890028978, 528044431, 795787957, 546160751, 21487680, 168379396, 292434098, 414672346, 74193376, 460353865, 599810935, 250857617, 915366231, 248863345, 970381475, 792991318, 740333468, 505276601, 404393468, 273222696, 38135257, 776858195, 153730583, 642800490, 383597969, 352113689, 326414281, 751880110, 401720832, 321560177, 799699361, 847915310, 122391227, 227253170, 943226946, 628558171, 741676814, 471158688, 954631869, 493837145, 558658912, 420443735, 350090863, 217956259, 331145950, 853718873, 294871436, 441691230, 450998982, 237913344, 891941663, 1946260, 405112401, 448399780, 134526127, 246436561, 278169858, 460138465, 93785028, 536128669, 614812564, 895531956, 53159706, 343122361, 979426864, 535308676, 821698590, 111592160, 392955473, 447760971, 209213748, 847593978, 203062304, 203128902, 787544197, 498828478, 184919578, 105720019, 69934934, 13384364, 973282740, 449768173, 269308198, 904824556, 182396273, 584885733, 396642025, 609732757, 302161309, 183805719, 163566228, 479978003, 98799651, 976400196, 125377402, 799132752, 870397588, 644664934, 129577634, 690319271, 611331587, 653433224, 140236662, 409788350, 991717810, 62680229, 190864441, 36959486, 149551212, 850748843, 164689931, 861991239, 929807057, 969665321, 847381024, 849985007, 211790079, 300573111, 274608474, 852794964, 947517699, 845476998, 892993251, 942841378, 752521136, 160135971, 872092879, 947081586, 43872472, 699047819, 356785202, 852607095, 799881153, 78633765, 743118036, 270375915, 917589851, 68917553, 710229437, 55629368, 618076743, 280545717, 675792083, 46429647, 151769255, 451990910, 175101818, 843430958, 38053664, 646697534, 23357308, 206681493, 888773710, 419288563, 102196642, 166544838, 158026445, 853567157, 547481582, 271969574, 391772235, 700892631, 483230045, 622773713, 745587272, 464843479, 112408178, 48833532, 419683777, 357283581, 893210864, 753476511, 49462239, 43950471, 623405550, 245081995, 772845334, 469206379, 631437749, 684644905, 793794697, 569684184, 860006640, 158036420, 392172613, 162031808, 602247245, 203070433, 384809257, 29972101, 344657818, 105304879, 159934700, 539867530, 111755839, 775104266, 722056100, 480533881, 603649910, 730015093, 32522487, 687171713, 684911737, 629028067, 75924301, 327784991, 613277615, 911404085, 68597770, 92366073, 745625029, 473314335, 507714509, 98679775, 522660661, 475294170, 305900432, 650978491, 240960675, 954022341, 297423873, 233051932, 288347091, 181067811, 822741050, 72596087, 389928500, 925730861, 660630476, 418823335, 494735470, 956973216, 280787188, 577131628, 195596415, 780760749, 646964034, 492636384, 290950928, 665101198, 971833316, 402869341, 31542354, 448714637, 853057984, 859647481, 659285587, 703667161, 442458694, 57325142, 151885002, 151752857, 953328299, 274699378, 797580192, 900864549, 977052491, 903191059, 560104200, 52364315, 317587469, 733519519, 51326765, 172718980, 394213323, 499127130, 125665101, 599958067, 570048626, 358205301, 955898164, 396169962, 863114450, 524877565, 561615134, 336979830, 751853389, 98033418, 914857313, 669594871, 233002010, 798378948, 353985696, 132400827, 853908795, 633800050, 114199369, 8366891, 369520637, 840068688, 154949227, 766964103, 1213933, 283566441, 213654982, 766431359, 140028557, 389857786, 592586116, 294866824, 626984599, 88266364, 960355422, 299777072, 159529372, 433368021, 546910609, 640482852, 176367836, 62590712, 619758852, 519471843, 689296297, 688241748, 125464096, 549853046, 180640016, 669655376, 304486472, 552708211, 641131096, 250145685, 522823788, 422054382, 614827289, 213695506, 564996794, 816097193, 472957326, 627305145, 419352923, 233618208, 201907686, 789638131, 935757716, 321551236, 258348634, 248012645, 915754672, 94217171, 566557194, 883879696, 841856794, 386613162, 570112346, 183700660, 278268556, 308943479, 160666387, 737303060, 567134616, 327727771, 639296326, 219084929, 949740710, 467443562, 16455771, 875530545, 782951703, 711107295, 863411295, 578371653, 66207956, 375238282, 908681407, 515884084, 90795523, 455372810, 89837046, 165491515, 545433366, 660354454, 653260780, 270146387, 283056775, 39236829, 89221906, 548284763, 958657863, 647273634, 738216290, 960141650, 192631043, 647619052, 435099529, 111019175, 387052722, 349026437, 943168803, 597199864, 798930903, 280032050, 191489048, 871756271, 864201473, 573902924, 776735804, 795907052, 513212481, 703258263, 151087418, 176917020, 492333520, 645927523, 842232145, 918613011, 167094468, 506609335, 871613850, 791653278, 688384948, 512230762, 466482156, 483519685, 433675444, 266224879, 712040274, 316470404, 6297629, 247528343, 266547054, 831469341, 917532298, 459833872, 954893577, 614837703, 484625452, 614869637, 917743182, 905427381, 449126127, 796820262, 408509829, 273602905, 130924280, 1363238, 389499824, 954805317, 932440256, 34161376, 646994455, 672836257, 808301053, 929096963, 231765547, 390778694, 403445961, 653868071, 549355895, 901843642, 882716412, 125812900, 266137390, 250231633, 801863164, 862419855, 603909210, 141087179, 919738330, 901776094, 636804992, 717115643, 982881315, 278589981, 897622715, 592874475, 963773361, 139945137, 389252372, 890252510, 865544569, 462018791, 972099566, 849449796, 319640588, 967009768, 977653667, 710029654, 805234475, 831002177, 275336330, 422855006, 949746887, 541794170, 641881338, 296285475, 292901421, 107561334, 338689309, 112458779, 325082011, 3976415, 304229218, 601214344, 86328828, 751441489, 862204727, 554702266, 186018851, 166853623, 545193868, 432626342, 498556538, 860331963, 609479011, 974179405, 836442658, 315554906, 589911857, 242364047, 745675667, 630588185, 96935486, 898831734, 753652548, 83905053, 205072787, 486649120, 696978729, 371086126, 376354590, 740911902, 983182992, 959047580, 971565881, 279013191, 628219669, 483423122, 559666181, 748528679, 349865602, 276254737, 103092679, 990713044, 883898451, 334011645, 643112778, 85592384, 110938911, 78761716, 162118715, 110215007, 361560450, 218658983, 958290706, 760866197, 29604925, 704254054, 884528885, 571553124, 722545849, 511824535, 189127084, 293444525, 539142876, 642675615, 952158794, 312246024, 275756454, 200298706, 261130169, 62294542, 510890694, 385243308, 87361521, 503202218, 685328461, 550921230, 668093102, 699944378, 251795690, 907314994, 834548983, 352821537, 549529635, 281274542, 587974019, 795434349, 753132255, 415545290, 77523025, 281787237, 176567548, 722869575, 34478434, 714412522, 671034944, 329114990, 958416239, 745926726, 754875902, 211334210, 513547036, 381109223, 400825307, 949915497, 794380771, 663920989, 690042117, 830304630, 901554891, 751723357, 837761558, 378511108, 115298175, 325447247, 614534142, 840758997, 813807256, 591333543, 691718994, 672655144, 699954263, 85458370, 19198497, 754433496, 300341823, 886939169, 54570137, 616323646, 496090306, 34402024, 817983914, 915965688, 479650439, 388452570, 454605978, 750397062, 559638074, 303896928, 22416828, 441748912, 635659640, 815695490, 812160395, 166688469, 740163360, 14049893, 284479436, 190422595, 187192515, 376697732, 47634513, 160874373, 126508400, 775997892, 99363239, 493832830, 763882002, 701596576, 15590851, 257335774, 894463993, 185206871, 441874230, 746700252, 302941806, 868371723, 139345496, 869630341, 144717208, 187345841, 866229903, 724450461, 648235214, 776271119, 672074506, 602185675, 656002752, 240125575, 759576687, 463430427, 24769850, 862837188, 53160078, 513987022, 118514895, 188179897, 699945777, 115323244, 199918423, 833621264, 805714018, 463715736, 180028074, 475829876, 235402877, 772103983, 49684084, 443337661, 655366896, 289638503, 258332145, 360855087, 899672361, 530502576, 801491866, 641986630, 940068353, 797422831, 378645901, 853709985, 87792814, 398991956, 660101704, 243383485, 532777074, 459644547, 702843272, 209971686, 829986137, 470834910, 246066405, 806738292, 39284371, 389133055, 321621467, 698830270, 670701663, 45171714, 633003395, 90710349, 967169522, 541775025, 988685463, 21712927, 170049523, 503374186, 602599325, 962557054, 800216315, 767004598, 737518012, 609437737, 530398437, 82759720, 621977664, 548979006, 245507299, 832068105, 80911832, 416356617, 318565618, 40420676, 412673617, 923197226, 594087420, 42029599, 521233968, 806698019, 833042288, 321490146, 468133703, 773978131, 414775293, 774760659, 300992794, 274025195, 445949927, 819855707, 528038317, 620344533, 51066611, 742263715, 539906647, 9185408, 244838920, 887410937, 539585878, 233938533, 832701367, 208941375, 890452341, 320097016, 460377592, 383972524, 956067685, 534451216, 946322067, 950977861, 379271132, 363268251, 740246294, 446595916, 554740081, 585267057, 666743526, 941443156, 923656781, 122441988, 203736886, 815895710, 498136156, 239856470, 992717436, 743674726, 96127672, 932528338, 278615623, 146992535, 68306453, 131167060, 272573946, 851897254, 782985541, 759971846, 767877668, 505054565, 682447171, 154820240, 351374909, 29839511, 846987109, 213673769, 590919567, 264042121, 189663389, 717706128, 781660659, 590772569, 670325982, 9239468, 791592672, 51083743, 740568821, 281574447, 587141513, 553122503, 340747559, 726765483, 771154066, 145504712, 464498808, 328555850, 866235034, 289880945, 310574040, 31723627, 26631855, 19526377, 58086236, 918654424, 582386705, 784853394, 657402015, 976196645, 154059840, 149978308, 600014675, 7004660, 658540583, 953807513, 842210720, 300038049, 525785906, 487155590, 970029619, 25074612, 511691999, 455850881, 892170974, 730230612, 811413348, 426045335, 640134437, 120756795, 527174688, 712332795, 372350239, 770574347, 775312159, 726265742, 117585021, 808434455, 150599746, 257106196, 676730440, 520558862, 38297346, 220183171, 564917745, 346371991, 627835740, 900198419 ]
def factrial(n):
    if n >= mod:
        return 0
    acc = table[n // (mod // width)]
    init = n // (mod // width) * (mod // width)
    for i in range(max(1, init), n+1):
        acc = acc * i % mod
    return acc

def power_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

X = power_func(2,n,mod)
X = X- 1
Y = (factrial(n)* pow(factrial(a),mod-2,mod)*pow(factrial(n-a),mod-2,mod)) % mod
Z = (factrial(n)* pow(factrial(b),mod-2,mod)*pow(factrial(n-b),mod-2,mod)) % mod
X = (X-Y-Z) % mod
print(int(X))

Submission status: Accepted

Solution code:
from functools import reduce

def cmb(n, r, mod):
    r = min(r, n-r)
    if r == 0: return 1
    num = reduce(lambda x, y: x * y % mod, range(n, n-r, -1))
    den = reduce(lambda x, y: x * y % mod, range(1, r+1))
    return num * pow(den, mod-2, mod) % mod

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

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

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    input = stdin.readline

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

    P = 10**9 + 7

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

def comb(n,k,p):
    min_k = min(k,n-k)

    n_kaijyo = 1
    k_kaijyo = 1
    for i in range(min_k):
        n_kaijyo = n_kaijyo * (n - i) % p
        k_kaijyo = k_kaijyo * (i + 1) % p

    return n_kaijyo * pow(k_kaijyo,p-2,p) % p
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,a,b = map(int, input().split())
mod = 10**9 + 7
def power_(n, p, mod):
    if p == 1:
        return n
    if p % 2 == 0:
        return (power_(n, p//2, mod) ** 2) % mod
    else:
        return n * (power_(n, p//2, mod) ** 2) % mod
#互いに素な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は互いに素であることが前提)
#a/b = a*(b`)となるb`を求める
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod
def mod_cmb(p,q,mod):
    #pCqを計算
    res = 1
    for i in range(q):
        res *= (p - i) * mod_inv(q - i, mod)
        res %= mod
    return res % mod
p = power_(2,n, mod)
sub = mod_cmb(n,a,mod) + mod_cmb(n,b,mod)
print((p - sub - 1) % mod)

Submission status: Accepted

Solution code:
def cmb(n, r):
    if n - r < r:
      r = n - r
    if r == 0: 
      return 1
    if r == 1: 
      return n
    numerator = [] 
    mod = 10**9+7
    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
def power_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
n, a, b = map(int, input().split())
mod = 10**9+7
ALL = power_func(2,n,mod)-1
A = cmb(n,a)
B = cmb(n, b)
ans = ALL-A-B
while ans < 0:
  ans = mod + ans
print(ans)

Submission status: Accepted

Solution code:
def cmb(n, r, mod):
    numerator = 1
    # n * (n-1) * ... * (n-r+1)
    for i in range(n-r+1, n+1):
        numerator = (i * numerator) % mod
    denominator = 1
    # r * (r-1) * ... * 1
    for i in range(1, r+1):
        denominator = (i * denominator) % mod
    # y^(mod-2) % mod
    fermat = pow(denominator, mod-2, mod)
    return (numerator * fermat) % mod


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

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

print(ans % mod)

Submission status: Accepted

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


def nCr(n, r, mod):
    r = min(r, n-r)
    x = y = 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) - nCr(n, a, mod) - nCr(n, b, mod) - 1
ans += mod if ans < 0 else 0
ans += mod if ans < 0 else 0
print(ans)

Submission status: Accepted

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

ans = (pow(2, n, m) - ((cmb(a) + cmb(b) + 1)%m))%m
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
#s = readline().rstrip().decode('utf-8')
#n = int(readline())
n,a,b = map(int,readline().split())

mod = 10**9+7


def pow(n, p): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod


case_all = pow(2,n) -1 #少なくとも1つは選ぶ為-1
case_a_n = 1
for i in range(n-a+1,n+1):
    case_a_n *= i
    case_a_n %= mod
case_a_r = 1
for i in range(1,a+1):
    case_a_r *= i
    case_a_r %= mod
case_a = case_a_n*pow(case_a_r,mod-2)%mod

case_b_n = 1
for i in range(n-b+1,n+1):
    case_b_n *= i
    case_b_n %= mod
case_b_r = 1
for i in range(1,b+1):
    case_b_r *= i
    case_b_r %= mod
case_b = case_b_n*pow(case_b_r,mod-2)%mod

case_all-=case_a+case_b
while case_all<0:
    case_all += mod
print(case_all)

Submission status: Accepted

Solution code:
MOD = (10**9) + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

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

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

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

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

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

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    n, a, b = (int(i) for i in input().split())
    MOD = 10**9 + 7
    COMB_a = modint(1)
    COMB_b = modint(1)
    for k in range(a):
        COMB_a *= n - k
    for k in range(1, a+1):
        COMB_a /= k
    for k in range(b):
        COMB_b *= n - k
    for k in range(1, b+1):
        COMB_b /= k
    ans = (pow(2, n, MOD) - 1 - COMB_a - COMB_b)
    print(ans)


if __name__ == '__main__':
    main()