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

def powerDX(n, r, mod):
  if r == 0: return 1
  if r%2 == 0:
    return powerDX(n*n % mod, r//2, mod) % mod
  if r%2 == 1:
    return n * powerDX(n, r-1, mod) % mod

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

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

Submission status: Accepted

Solution code:
# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
  return pow(a, mod-2, mod)

# nCr mod m
# modinvが必要
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
  r = min(r, n-r)
  res = 1
  for i in range(r):
    res = res * (n - i) * modinv(i+1, mod) % mod
  return res

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

# すべての組み合わせ = 2 ** n - 1
all_comb = 2 ** n - 1

NG_comb_a = combination(n, a)
NG_comb_b = combination(n, b)

ans = (all_comb - NG_comb_a - NG_comb_b) % MOD

print(ans)

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 modinv(a, mod=10**9 + 7):
    return pow(a, mod - 2, mod)


def combination(n, r, mod=10**9 + 7):
    r = min(r, n - r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i + 1, mod) % mod
    return res


ans = 2**n

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

ans -= 1

ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

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

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

btmp=1
waru=1
for i in range(b):
    btmp*=n-i
    waru*=i+1
    btmp%=mod
    waru%=mod
waru=pow(waru,mod-2,mod)
btmp*=waru
# print(atmp,btmp)
ans=ans-(atmp+btmp)+mod*2
ans%=mod
print(ans)

Submission status: Accepted

Solution code:
n,a,b = list(map(int,input().split()))
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a = 1
  b = 1
  c = 1
  for i in range(1,n+1):
    a = (a*i)%p
  for i in range(1,k+1):
    b = (b*i)%p
  for i in range(1,n-k+1):
    c = (c*i)%p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
mod = 10**9 + 7
ans = (power_func(2,n,mod)-1)%mod
ac = 1
for i in range(1,a+1):
    ac = (ac*(n-i+1)*power_func(i,mod-2,mod))%mod
ans = (ans-ac)%mod
bc = ac
for i in range(a+1,b+1):
    bc = (bc*(n-i+1)*power_func(i,mod-2,mod))%mod
ans = (ans-bc)%mod
print(ans)

Submission status: Accepted

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

MOD = 10**9 + 7

def nCr(n,r):
  p = 1
  q = 1
  if n-r >= r:
    for i in range(r):
      p *= n-i
      p %= MOD
      q *= i+1
      q %= MOD
  else:
    for i in range(n-r):
      p *= n-i
      p %= MOD
      q *= i+1
      q %= MOD
  return p*pow(q,MOD-2,MOD)

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

Submission status: Accepted

Solution code:
def ncr(n, r, p): 
    num = den = 1 
    for i in range(r): 
        num = (num * (n - i)) % p 
        den = (den * (i + 1)) % p 
    return (num * power(den,  
            p - 2, p)) % p 

def power(x, y, p) : 
    res = 1 
    x = x % p  
    while (y > 0) : 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
        y = y >> 1  
        x = (x * x) % p 
    return res 
n,a,b=list(map(int,input().split()))
p=1000000007;
r=ncr(n,a,p)
s=ncr(n,b,p)
ans=power(2,n,p)-1
ans=ans-r-s
print(ans%p)

Submission status: Accepted

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

#print(x*pow(y,(mod-2),mod)%mod)

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

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

#print(conv(n, a, mod))
#print(conv(n, b, mod))

ans = power_func(2, n, mod) - conv(n, a, mod) - conv(n, b, mod) - 1
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

# nCr mod m
# modinvが必要
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10 ** 9 + 7):
    r = min(r, n - r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i + 1, mod) % mod
    return res


n, a, b = map(int, input().split())
res = 0
mod = 1000000000 + 7
res = (2** (n) -1 )% mod
res -= combination(n, a)
res %= mod
res -= combination(n, b)
res %= mod
print(res)

Submission status: Accepted

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


def two_power(x):
    if x == 0:
        return 1
    half = two_power(x // 2)
    return half * half * (2 ** (x % 2)) % MOD


M = max(a, b)
inv = [0] * (M + 1)
inv[1] = 1
for i in range(2, M + 1):
    inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD


def nCk(x, y):
    ans = 1
    for i in range(1, y + 1):
        ans *= (x - i + 1) * inv[i]
        ans %= MOD
    return ans


ans = two_power(n) - nCk(n, a) - nCk(n, b) - 1
print(ans % MOD)

Submission status: Accepted

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

def nCr(n, r, 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

ans = pow(2, n, m) - 1 - nCr(n, a, m) - nCr(n, b, m)

while ans < 0:
    ans += m

print(ans)

Submission status: Accepted

Solution code:
from operator import mul
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 power(x, y//2)**2 * x % mod

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

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

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

numer1 = reduce(mul, range(n, n - r1, -1), 1)
denom1 = reduce(mul, range(1, r1 + 1), 1)
numer2 = reduce(mul, range(n - r1, n - r2, -1), numer1)
denom2 = reduce(mul, range(r1 + 1, r2 + 1), denom1)

print((power(2, n) - 1 - div(numer1, denom1) - div(numer2, denom2)) % (10 ** 9 + 7))

Submission status: Accepted

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

mod = 10 ** 9 + 7
f = [1]
for i in range(1,2*(10 ** 5)+1):
    f.append((f[-1] * i) % mod)
def comb(n,r):
    z = 1
    for i in range(n-r+1, n+1):
        z *= i
        z %= mod
    return (z * pow(f[r], mod-2, mod)) % mod

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

print(ans)

Submission status: Accepted

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

def 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

mod = int(1e9+7)
n,a,b= map(int,input().split())

S = (power_func(2,n,mod) - 1)%mod
A = combination(n,a)
B = combination(n,b)
ans = (S-A-B)%mod

print(ans)

Submission status: Accepted

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

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
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
def cmb(n, r, mod):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
  
print((func(2,n,mod)-cmb(n,a,mod)-cmb(n,b,mod)-1)%mod)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def C(n,r):
    return fact[n]*pow(fact[n-r],mod-2,mod)*pow(fact[r],mod-2,mod)%mod

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

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

tmp *= pow(fact[a],mod-2,mod)
ans -= tmp
ans %= mod
tmp = 1
for i in range(b):
    tmp *= (n-i)
    tmp %= mod
tmp *= pow(fact[b],mod-2,mod)
ans -= tmp
ans %= mod
print(ans)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def get_fraction_mod(numerator, denominator):
    '''
        returns numerator / denominator (mod MOD)
    '''
    inv = pow(denominator, MOD - 2, MOD)
    return numerator * inv % MOD

def make_comb(n, k):
    a = 1
    b = 1
    for i in range(k):
        a = a * (n - i) % MOD
        b = b * (i + 1) % MOD
    ret = get_fraction_mod(a, b)
    return ret


def solve(n: int, a: int, b: int):
    ret = (pow(2, n, MOD) - 1) % MOD
    ret = ret + MOD - make_comb(n, a)
    ret = ret + MOD - make_comb(n, b)
    ret %= MOD
    print(ret)
    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, raw_input().split())
 
mod=10**9+7
inv_fact=[1]
fact_tmp = 1
for i in range(1, b+1):
    fact_tmp *= i
    fact_tmp %= mod
    inv_fact.append(pow(fact_tmp, mod-2, mod))
 
fact=[1]
fact_tmp = 1
for i in range(N,N-b-2,-1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)

def ncr(n,r):
    return (fact[r]*inv_fact[r])%mod

ans=pow(2,N,mod)-ncr(N,a)-ncr(N,b)-1
if 0<=ans:
    print ans%mod
else:
    while ans<0:
        ans+=mod
    print ans%mod

Submission status: Accepted

Solution code:
import functools, operator


def read():
    N, A, B = list(map(int, input().strip().split()))
    return N, A, B


table = []

def solve(N, A, B, MOD=10**9+7):
    n = (pow(2, N, MOD) + MOD - 1) % MOD
    a = nCk(N, A, MOD)
    b = nCk(N, B, MOD)
    return (n + MOD + MOD - a - b) % MOD


def factorial(n, MOD=10**9+7):
    return functools.reduce(lambda x, y: (x*y) % MOD, range(1, n+1))



def modinv(n, p):
    """
    逆元のmod pを求める
    """
    if n >= p:
        raise ValueError('p must be larger than n')
    return pow(n, p-2, p)


def nCk(n, k, MOD=10**9+7):
    r = 1
    kmin = min(k, n-k)
    for i in range(1, kmin+1):
        r = (r * modinv(i, MOD)) % MOD
    for i in range(n-kmin+1, n+1):
        r = r * i % MOD
    return r

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Accepted

Solution code:

def extended_gcd(a, b):
    c0, c1 = a, b
    a0, a1 = 1, 0
    b0, b1 = 0, 1

    while c1 != 0:
        q, m = divmod(c0, c1)
        c0, c1 = c1, m
        a0, a1 = a1, a0 - q*a1
        b0, b1 = b1, b0 - q*b1
    return a0, b0, c0


def mod_inverse(a, n):
    s, _, g = extended_gcd(a, n)
    if g != 1:
        raise Exception('The inverse does not exist.')
    return s % n

def comb(n, k):
    c = 1
    k = min(k, n-k)
    for i in range(k):
        c *= n-i
        c *= mod_inverse(i+1, MOD)
        c %= MOD
    return c

n,a,b=map(int, input().split())
MOD = 1000000007
ans = pow(2, n, MOD)
ans -= comb(n, a)
while ans < 0:
    ans += MOD
ans -= comb(n, b)
while ans < 0:
    ans += MOD
print(ans-1)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,a,b = inpl()
p = pow(2,n,mod)
x = y = 1
for i in range(a):
    x *= n-i
    x %= mod
for i in range(a):
    x *= pow(a-i,mod-2,mod)
    x %= mod

for i in range(b):
    y *= n-i
    y %= mod
for i in range(b):
    y *= pow(b-i,mod-2,mod)
    y %= mod
# print(x,y)
print((p-x-y-1)%mod)

Submission status: Accepted

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans


'''
p = 10 ** 9 + 7
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
'''


#a = list(map(int, input().split()))

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

p = 10 ** 9 + 7
N = 10 ** 5 * 5
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
        

di131072 = 1

for i in range(131072):
    di131072 *= 2
    di131072 %= p
    
q = n // 131072
r = n % 131072


ans = 1

for i in range(q):
    ans *= di131072
    ans %= p
for i in range(r):
    ans *=2
    ans %=p
    
fact2num = max(a,b)+2
fact2 = []
now = 1

for i in range(fact2num):
    now *= (n-i)
    now %= p
    fact2.append(now)
#print(fact2)
#print(factinv[0:4])

#print(ans)
    
ans -= 1
ans -= (fact2[a-1] * factinv[a])%p
#print((fact2[a-1] * factinv[a])%p)
ans -= (fact2[b-1] * factinv[b])%p
#print((fact2[b-1] * factinv[b])%p)
ans%=p

#print()
print(ans)

Submission status: Accepted

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

MOD = 10**9 + 7

# https://qiita.com/derodero24/items/91b6468e66923a87f39f


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

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

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

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

  return result


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

Submission status: Accepted

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

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range(2, 2 * (10 ** 5) + 1):
    g1.append((g1[-1] * i) % p)
    inverse.append((-inverse[p % i] * (p//i)) % p)
    g2.append((g2[-1] * inverse[-1]) % p)


def comb(n, a):
    ans = 1
    for i in range(1, a + 1):
        ans = ans * (n - i + 1) % p
    return ans * g2[a] % p


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

Submission status: Accepted

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

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

comb = [1] * (b + 1)

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

ans -= comb[a] + comb[b]
ans %= mod


print(ans)

Submission status: Accepted

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

PRIME = 10 ** 9 + 7
maximum = min(n + 1, 200001)

fac = [1 for i in range(maximum)]
finv = [1 for i in range(maximum)]
inv = [1 for i in range(maximum)]

fac[1] = n
for i in range(2, maximum):
  fac[i] = fac[i - 1] * (n + 1 - i) % PRIME
  inv[i] = PRIME - inv[PRIME % i] * (PRIME // i) % PRIME
  finv[i] = finv[i - 1] * inv[i] % PRIME

ans = pow(2, n, PRIME) - 1
ans = (ans + PRIME - ((fac[a] * finv[a])  % PRIME) % PRIME) % PRIME
ans = (ans + PRIME - ((fac[b] * finv[b])  % PRIME) % PRIME) % PRIME
print(ans)

Submission status: Accepted

Solution code:
def modinv(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % (10**9+7)

MOD=10**9+7
am=[2]
for i in range(60):
    am.append((am[-1]**2)%MOD)

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

n,a,b=map(int,input().split())
a=min(a,n-a)
b=min(b,n-b)
s=bin(n)[2::][::-1]

ans=1
for i in range(len(s)):
    if s[i]=="1":
        ans*=am[i]
        ans%=MOD

for x in [a,b]:
    tmp=1
    for i in range(n-x+1,n+1):
        tmp=(tmp*i)%MOD
    tmp*=modinv(fr[x],MOD)
    ans=(ans-tmp)%MOD

ans=(ans-1)%MOD
print(ans)

Submission status: Accepted

Solution code:
import math

MOD = 10**9+7
fact = [1]
for i in range(1, 2*10**5+10):
    fact.append((fact[i-1]*i)%MOD)

def comb(n, k):
    ans = 1
    for i in range(k):
        ans = (ans*(n-i))%MOD
    return (ans*pow(fact[k], MOD-2, MOD))%MOD

n, a, b = map(int, input().split())
ans = 1
x = 2
y = n
while y != 0:
    if y%2 != 0:
        ans = (ans*x)%MOD
    x = (x*x)%MOD
    y >>= 1
ans = (ans - comb(n, a) - comb(n, b) -1)%MOD
print(ans)

Submission status: Accepted

Solution code:
def ExtGCD(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, x, y = ExtGCD(b, a % b)
        x -= (a // b) * y
        return d, y, x
def ModInv(a, mod):
    return ExtGCD(a, mod)[1] % mod
def ModComb(n, k, mod):
    if n < k or n < 0 or k < 0:
        return 0
    elif n == 0 or k == 0:
        return 1
    q, a = 1, 1
    for i in range(n-k+1, n+1):
        q = (q * i) % mod
    for i in range(2, k+1):
        a = (a * i) % mod
    return int(q * ModInv(a, mod) % mod)
def ModPow(a,n,mod):
    bi=str(format(n,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) % mod
        if bi[i]=="1":
            res=(res*a) % mod
    return res
def main():
    n,a,b=map(int,input().split())
    mod=10**9+7
    print((ModPow(2,n,mod) - (ModComb(n,a,mod) + ModComb(n,b,mod))-1)%mod)
main()

Submission status: Accepted

Solution code:
mod = 10**9 + 7

def power(b, e):
	if e == 0: return 1

	half = power(b, e // 2)

	if e % 2 == 0:
		return (half * half) % mod
	else:
		return (((half * half) % mod) * b) % mod

def mod_inv(n):
	return power(n, mod - 2)

def choose(n, a):
	num = 1
	den = 1
	for i in range(1, a + 1):
		num = (num * (n - i + 1)) % mod
		den = (den * i) % mod

	# print("inv:", mod_inv(den))
	# print(num, den)
	return (num * mod_inv(den)) % mod


if __name__ == "__main__":
	line = input().split(" ")
	n, a, b = int(line[0]), int(line[1]), int(line[2])

	# print(power(2, n))
	# print("nca", choose(n, a))
	# print("ncb", choose(n, b))
	ans = (power(2, n) - choose(n, a) - choose(n, b) - 1 + 2* mod) % mod 

	print(ans)

Submission status: Accepted

Solution code:
def e(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1

    while c1 != 0:
        m = c0 % c1
        q = c0 // c1

        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)

    return c0, a0, b0

def c(n,r):
    ngo = 1
    ngoo = 1
    for i in range(min(n,r)):
        ngo*=(n-i)
        ngoo*=(i+1)
        ngoo%=(10**9+7)
        ngo%=(10**9+7)
        #ngo %= (10**9+7)
        #ngoo %= (10**9+7)
    return (ngo*e(ngoo,10**9+7)[1])%(10**9+7)
    
def beki(x,y):
    if y == 0:
        return 1
    if y == 1:
        return x
    if y %2 == 0:
        return beki((x**2)%(10**9+7),y//2)%(10**9+7)
    else:
        return x*beki(x,y-1)%(10**9+7)
    
import math
n,a,b = map(int,input().split())
ngo = (beki(2,n)-1)%(10**9+7)
ans = (ngo-c(n,a)-c(n,b))
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
#コンビネーション。
def comb(n,m,p=10**9+7):
    if n < m : return 0
    if n < 0 or m < 0:return 0
    m = min(m, n-m)
    top = bot = 1
    for i in range(m):
        top = top*(n-i) % p
        bot = bot*(i+1) % p
    bot = pow(bot, p-2, p)
    return top*bot % p

#累乗
def mpow(x: int, k: int, MOD=1000000007) -> int:
    res = 1
    y = x
    while (k):
        if(k % 2 == 1):
            res = (res * y) % MOD
        y = (y ** 2) % MOD
        k = k // 2
    return res



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

CA = comb(n,a,10**9+7)
CB = comb(n,b,10**9+7)
X = mpow(2,n,10**9+7)
output = X-CA-CB-1
while output<0:
    output += 10**9+7
print(output)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


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


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
# sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = True
show_flg = False

def f(n):
    r = (n - 2)
    m = (4 * (1 - 2 ** r)) // (1 - 2)
    return (3 + m) % MOD


def modinv(a):
    return pow(a, MOD-2, MOD)


def main():
    n, a, b = MI()
    M = 10**5
    # cans = []

    # for i in range(2, M + 1):
    #     g1.append((g1[-1] * i) % MOD)
    #     inverse.append((-inverse[MOD % i] * (MOD//i)) % MOD)
    #     g2.append((g2[-1] * inverse[-1]) % MOD)

    # first = cmb(n, a, MOD)
    # second = cmb(n, b, MOD)

    # for i in range(2, n+1):
    #     ans = 0
    #     red = 0
    #     for j in range(1, i+1):
    #         if j != a and j != b:
    #             ans += cmb(i, j, MOD)
    #         else:
    #             red += cmb(i, j, MOD)
    #         # print('cmb', i, j, cmb(i, j, MOD))
    #     print(i, ans, red, 'f', f(i))
    #     cans.append(ans)
        # print('ans', f(i))

    # for i in range(len(cans) - 1):
    #     print(cans[i+1] - cans[i])

    p = 1
    c = 1
    for i in range(a):
        p *= (n - i)
        c *= (i + 1)
        p = p % MOD
        c = c % MOD
    first = p * modinv(c)

    p = 1
    c = 1
    for i in range(b):
        p *= (n - i)
        c *= (i + 1)
        p = p % MOD
        c = c % MOD
    second = p * modinv(c)
    # print(first, second)

    ans = f(n)
    print((ans - first - second) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 10**9+7
rng = 400100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
def cmb(n,k):
  if n-k<0:
    return 0
  else:
    ls=[n]
    for i in range(k-1):
      ls.append(ls[-1]*(n-i-1)%mod)
    return ls[-1]*pow(fctr[k],mod-2,mod)%mod
n,a,b=map(int,input().split())
print((pow(2,n,mod)-cmb(n,a)-cmb(n,b))%mod-1)

Submission status: Accepted

Solution code:
NN = 202020
MOD = 10**9+7
INF = float("inf")

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

# f = [0]*NN
# rf = [0]*NN
# inv = [0]*NN
f = [1, 1]
rf = [1, 1]
inv = [0, 1]

for i in range(2, NN):
    f.append((f[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    rf.append((rf[-1] * inv[-1]) % MOD)


def C(n, r):
    return (f[n] * rf[r] * rf[n-r]) % MOD


ac = bc = 0
tmp = 1
for i in range(1, max(a, b)+1):
    tmp = (tmp*(n-i+1)*inv[i])%MOD
    # tmp = tmp * (n - i + 1) // i
    # print(rf[i], inv[i], tmp)
    if i == a:
        ac = tmp
    if i == b:
        bc = tmp

# print(ac, bc)

sisu = 1
x = 2
while n:
    if n&1:
        sisu = sisu*x%MOD
    x = x*x%MOD
    n = n>>1
    # print(n, x, sisu)

ans = (sisu-1-ac-bc)%MOD

print(ans)

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 = [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 %= M

    return result


def pow(x, n):
    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = (ans*x) % M
        x = (x*x) % M
        n = n >> 1  # ビットシフト
    return ans


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

print((pow(2, N) - cmb(N, a)-cmb(N, b)-1) % M)

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 invmod(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
    
def left_bin(a, n, c):
    ns = [int(i) for i in bin(n)[3:]]
    t = a
    for i in ns:
        t = t*t % c
        if i == 1:
            t = t*a % c
    return t

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

ans = left_bin(2, n, c) - 1 
temp = n
if a == 1:
    ans = (ans - n) % c
for i in range(1, b):
    temp = temp*(n-i) % c
    temp = temp*invmod(i+1, c) % c
    if i+1 == a:
        ans = (ans - temp) % c
ans = (ans - temp) % c
print(ans)

Submission status: Accepted

Solution code:
import sys

def comb(n, r, revfact, mod):
    ans = 1
    for i in range(r):
        ans *= (n - i)
        ans %= mod
        ans *= revfact[i + 1]
        ans %= mod
    return ans

def solve():
    input = sys.stdin.readline
    n, a, b = map(int, input().split())
    mod = 7 + 10 ** 9
    total = (pow(2, n, mod) - 1) % mod
    rev = [1] * (b + 2)
    for i in range(1, b + 2):
        rev[i] = pow(i, mod - 2, mod)

    print((total - comb(n, a, rev, mod) - comb(n, b, rev, mod)) % mod)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:

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

#逆元テーブル
inv_t = [0]+[1]
for i in range(2,N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

def comb(n, r):
    ret = 1
    for i in range(1, r + 1):
        ret = (ret * (n - i + 1) * inv_t[i]) % mod
    return ret

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K = K * x % mod
        x = x * x % mod
        n //= 2

    return K * x % mod

print((pow_k(2, n) - 1 - comb(n, a) - comb(n,b))%mod)

Submission status: Accepted

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

ans = pow(2, n, MOD) - 1
fa = math.factorial(a)
fb = math.factorial(b)
tmp = 1
for i in range(a):
    tmp = (tmp * (n-i)) % MOD
ans -= tmp*pow(fa, MOD-2, MOD)
for i in range(a, b):
    tmp = (tmp * (n-i))%MOD
ans -= tmp*pow(fb, MOD-2, MOD)
ans = ans % MOD
print(ans)

Submission status: Accepted

Solution code:
def mod_inv(a, m):
    return pow(a, m-2, m)


def combination(a, b):
    if b > a - b:
        return combination(a, a - b)
    ans_mul = 1
    ans_div = 1
    for i in range(b):
        ans_mul *= a - i
        ans_div *= i + 1
        ans_mul %= MOD
        ans_div %= MOD
    ans = ans_mul * mod_inv(ans_div, MOD)
    return ans


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

N %= MOD
sm = pow(2, N, MOD) % MOD
sm -= 1

a = combination(N, A) % MOD
b = combination(N, B) % MOD

ans = sm - a - b
ans %= MOD
print(ans)