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:
## 合計は2^NからnCaとnCbを引いたものに等しいので
n,a,b = list(map(int,input().split()))

mod = int(1e9+7)
ans = 1

def calc(n,mod):
  if n>25:
    return ( (calc(n//2,mod) **2 ) * (2 if n%2 == 1 else 1) )% mod
  else:
    return (2**n) % mod
    
ans = calc(n,mod)
  
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
  
a1 = 1
for i in range(1,a+1):
  a1 = int((a1*(n-a+i))*modinv(i,mod))%mod

b1 = 1
for i in range(1,b+1):
  b1 = int((b1*(n-b+i))*modinv(i,mod))%mod
  
print(int((ans-1-b1-a1))%mod)

Submission status: Accepted

Solution code:

def pow_r(x, n,s):
    """
    O(log n)
    """
    x=x%s
    if n == 0:
        return 1

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

    return K * x%s
n,a,b=map(int,input().split())
s=10**9+7
ma=1
for i in range(a):
    ma*=(n-i)
    ma%=s
ama=ma
for i in range(a,b,1):
    ma*=(n-i)
    ma%=s
bma=ma

mi=1
for i in range(a):
    mi*=(i+1)
    mi%=s
ami=mi
for i in range(a,b,1):
    mi*=(i+1)
    mi%=s
bmi=mi

if n==2:
    print(0)
else:
    print((pow_r(2,n,s)%s-(ama*pow_r(ami,s-2,s)%s+bma*pow_r(bmi,s-2,s)%s)-1)%s)

Submission status: Accepted

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

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

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


def cmb(r, mod):
    if r<0:
        return 0
    return g1[r-1] * g2[r] % mod

mod = 10**9+7 #出力の制限
N = 2 * 10 ** 5
g1 = [n % mod] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブ

for i in range( 2, N + 1 ):
    g1.append((g1[-1] * (n - i + 1)) % mod)
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ans -= cmb(a, mod)
ans -= cmb(b, mod)
ans %= mod

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7
N ,a, b = map(int, input().split())
nCr = 1
A=1
B=1
oa = 1
for r in range(b):
    nCr_1 = nCr * ((N - r) * pow(r + 1,MOD-2,MOD))%MOD
    nCr_1 %= MOD
    nCr = nCr_1
    if r==a-1:
      A = nCr_1
    if r==b-1:
      B = nCr_1
ans = pow(2,N,MOD)-1-A-B
print(ans%MOD)

Submission status: Accepted

Solution code:
from math import factorial
n, a, b = map(int, input().split())
if n == 2 and a == 1 and b == 2:
    print(0)
    exit()

mod = 10**9 + 7

limit = 0
m = n
while m > 0:
    m //= 2
    limit += 1
# print(limit)

def solve(n):
    ans = 1
    p = 2
    for i in range(limit):
        # print(i, (n >> i) & 1)
        if (n >> i) & 1 == 1:
            ans = (ans * p) % mod
        p = (p * p) % mod
    # print(p)
    return ans

ans = solve(n)
# print(ans)
# a1 = solve(a - 1)
# a2 = solve(a)
# a3 = (a1 - a2) % mod
# b1 = solve(b - 1)
# b2 = solve(b)
# b3 = (b1 - b2) % mod
# print((ans - a3 - b3) % mod)

def gcd1(a, b):
    def calc(a, b, first, second):
        if a < b:
            a, b = b, a
        r = a % b
        q = -(a - r)//b
        if r == 0:
            return b, second
        # first += q * second
        first = [x + q * y for (x, y) in zip(first, second)]
        return calc(r, b, second, first)
    first = [1, 0]
    second = [0, 1]
    return calc(a, b, first, second)

def mod_inv(n, mod):
    table = gcd1(n, mod)
    inv = table[1][1]
    if inv < 0:
        inv += mod
    return inv

def cmb(n, r, mod):
    ans = 1
    for i in range(r):
        ans = (ans * n) % mod
        n -= 1
    ans1 = 1
    for i in range(1, r + 1):
        ans1 = (ans1 * i) % mod
    return ans * mod_inv(ans1, mod)

# f_n = factorial(n) % mod
# f_a = factorial(a) % mod
# f_b = factorial(b) % mod
# f_na = factorial(n - a) % mod
# f_nb = factorial(n - b) % mod
# print(f_n, f_a, f_b, f_na, f_nb)
# ac = (f_n * mod_inv(f_a, mod)) % mod
# ac = (ac * mod_inv(f_n_a, mod)) % mod
# bc = (f_n * mod_inv(f_b, mod)) % mod
# bc = (bc * mod_inv(f_n_b, mod)) % mod

ac = cmb(n, a, mod)
bc = cmb(n, b, mod)

# print(ans, ac, bc)
print((mod + ans - ac - bc - 1) % mod)

Submission status: Accepted

Solution code:
import sys
#import collections as col
input=sys.stdin.readline

def facto(x, y, mod):
	re = 1
	for i in range(y, x+1):
		re *= i
		re %= mod
	print(re, file=sys.stderr)
	return re

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    #r = min(r, n-r)
    return facto(n, n-r+1, mod) * g2[r] % mod
    #return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
NN = 2 * 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


def main():
	N,A,B=map(int,input().split())
	#N=input().rstrip()
	#N=int(input())
	#vA=list(map(int,input().split()))
	M = 10**9 + 7
	
	res = pow(2, N, M) - 1
	res = (res+M) % M
	res -= cmb(N, A, M)
	res = (res+M) % M
	res -= cmb(N, B, M)
	res = (res+M) % M
	
	print(res)


main()

Submission status: Accepted

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

# すべての取り方
ans = pow(2, N, mod) - 1

up = [N]
down = [1]
for i in range(1, B):
    down.append(down[-1] * (i+1) % mod)
    up.append(up[-1] * (N - i) % mod)


def comb(r):
    res = up[r - 1] * pow(down[r - 1], mod - 2, mod) % mod
    return res


ans = (ans - comb(A) + mod) % mod
ans = (ans - comb(B) + mod) % mod
print(ans)

Submission status: Accepted

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

fac1 = [n] * (max + 1)
fac2 = [1] * (max + 1)
for i in range(2, max + 1):
    fac1[i] = fac1[i - 1] * (n - i + 1) % mod
    fac2[i] = fac2[i - 1] * i % mod
c = fac1[a] * pow(fac2[a], mod - 2, mod) % mod
d = fac1[b] * pow(fac2[b], mod - 2, mod) % mod

print((pow(2, n, mod) - c - d - 1) % mod)

Submission status: Accepted

Solution code:
from math import factorial
n, a, b = map(int, input().split())

mod = 10**9+7


def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    # a*x+y*mod = 1
    return (mod+x % mod) % mod


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

fact[0] = fact[1] = 1
ifact[0] = ifact[1] = 1

for i in range(2, max_num):
    fact[i] = fact[i-1] * i % mod
    ifact[i] = ifact[i-1] * inv(i, mod) % mod


def comb(x, y):
    tmp = 1
    for i in range(1, y+1):
        tmp *= (n+1-i)
        tmp %= mod
    tmp *= ifact[y]
    tmp %= mod
    return tmp

po = [2]
for i in range(1, 100):
    po.append((po[-1]**2) % mod)

nb = list(bin(n)[2:])[::-1]
n2 = 1

for i in range(len(nb)):
    if nb[i] == '1':
        n2 *= po[i]

n2 %= mod

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

Submission status: Accepted

Solution code:
n,a,b = map(int,input().split())
mod = 10**9+7
import sys
sys.setrecursionlimit(10**9)
ans = 1
now = n
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
ans = power(2,n)
com = [0]*(b+1)
com[0]=1
N = b+1
inv_t = [0]+[1]
for i in range(2,N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]
for i in range(1,b+1):
  com[i] = ((com[i-1]*(n-i+1))%mod)*(inv_t[i])%mod
ans -= com[a]+com[b]+1
print(ans%mod)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

binary_map = [(1, 2)]

while binary_map[-1][0] < N:
    binary_map.append((binary_map[-1][0]*2, binary_map[-1][1]**2 % MOD))


def modinv(a):
    b = MOD
    u = 1
    v = 0
    while b > 0:
        t = a // b
        a -= t * b
        c = a
        a = b
        b = c

        u -= t * v
        c = u
        u = v
        v = c
    u %= MOD
    if u < 0:
        u += MOD
    return u


def get_exp(mul_num):
    ret = 1
    index = -1
    while mul_num > 0:
        while mul_num < binary_map[index][0]:
            index -= 1
        mul_num -= binary_map[index][0]
        ret = (ret * binary_map[index][1]) % MOD
    return ret


bouquet_max = get_exp(N)

P_table = [N] * B

for i in range(B - 1):
    P_table[i + 1] = (P_table[i] * (N - i - 1)) % MOD

modinvexp_table = [1] * B

for i in range(1, B):
    modinvexp_table[i] = modinvexp_table[i - 1] * modinv(i + 1) % MOD

remove_a = P_table[A - 1] * modinvexp_table[A - 1] % MOD
remove_b = P_table[B - 1] * modinvexp_table[B - 1] % MOD

print((bouquet_max - P_table[A - 1] * modinvexp_table[A - 1] - P_table[B - 1] * modinvexp_table[B - 1] - 1) % MOD)

Submission status: Accepted

Solution code:
import sys
from pprint import pprint

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]]

  
def mod_inv(a,m):
    if a == 0:
        return 0
    x = extgcd(a,m)[0]
    return (m+x%m)%m


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

if __name__ == '__main__':
    mod = 10**9 + 7
    n, a, b = map(int, sys.stdin.readline().strip().split(" "))
    # print(n, a, b, mod)

    denominator = 1
    numerator = 1
    for i in range(1, a+1):
        # print(n-i+1, i)
        numerator *= (n-i+1)
        numerator %= mod
        denominator *= i
        denominator %= mod
    # print(numerator, denominator)
    cmb_a = numerator * mod_inv(denominator, mod)
        
    denominator = 1
    numerator = 1
    for i in range(1, b+1):
        # print(n-i+1, i)
        numerator *= (n-i+1)
        numerator %= mod
        denominator *= i
        denominator %= mod
    # print(numerator, denominator)
    cmb_b = numerator * mod_inv(denominator, mod)
        
    # print(pow(2, n, mod) - 1, cmb_a, cmb_b)
    ans = pow(2, n, mod) - 1 - cmb_a - cmb_b
    print(ans % mod)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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%MOD

def solve():
    n, a, b = [int(_) for _ in input().split()]
    nb = cmb(n, b)
    na = cmb(n, a)
    return (2 ** n)%MOD - 1 - na - nb

if __name__ == '__main__':
    print(solve()%MOD)

Submission status: Accepted

Solution code:
n, a, b = [int(x) for x in input().split()]

p = 10 ** 9 + 7

binom = n # n choose 1
ans = 0 if a == 1 or b == 1 else n

# x^nを求める
def exp_by_sq(x, n):
    if n == 0:
        exp = 1
    elif n == 1:
        exp = x % p
    elif  n % 2 == 0:
        exp = exp_by_sq(x * x % p, n // 2)
    else:
        exp = x * exp_by_sq(x * x % p, (n - 1) // 2) % p
    return exp % p


def binomial_p(n, k, p):
    '''
    Input: integers n, k such that n >= k >= 0, prime number p
    Output: n choose k mod p
    '''
    k = min(k, n-k)
    numer = n  # n * (n-1) * ... * (n- k + 1)
    inv = [0, 1]    # inv[i] : inverse of i mod p
    invfct_k = 1 # factorial of inverse of k mod p = 1^(-1) * 2^(-1) * ... * k^(-1) mod p

    for i in range(2, k + 1):
        numer = numer * (n - i + 1) % p
        inv.append(( inv[p % i] * (p - p//i) ) % p ) # inverse of i
        invfct_k = invfct_k * inv[-1] % p

    if k == 0:
        return 1
    elif k == 1:
        return n
    else:
        return numer * invfct_k % p

ans = (exp_by_sq(2, n) - 1 - binomial_p(n, a, p) - binomial_p(n, b, p)) % p

print(ans)

Submission status: Accepted

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

MOD = 1000000007


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 * pow(denom, 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:
MAX_NUM = 2 * (10**5)+ 1
MOD = 10**9+7

fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]

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

for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def combinations(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    res = 1
    for i in range(n, n - k, -1):
      res = (res * i) % MOD

    res = (res * finv[k]) % MOD

    return res

n, a, b = map(int, input().split())
if n == 2:
  print(0)
  exit(0)

sum = pow(2, n, MOD) - 1
sum = (sum - combinations(n, a)) % MOD
sum = (sum - combinations(n, b)) % MOD

print(sum)

Submission status: Accepted

Solution code:
def f(x,r,p):
  ans=1
  for i in range(r):
    ans=(ans*(x-i))%p
  return ans
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
  else:
    return (a*power_func(a,b-1,p))%p
n,a,b=map(int,input().split())
mod=10**9+7
a=min(a,n-a)
b=min(b,n-b)
ca=f(n,a,mod)*power_func(f(a,a,mod),mod-2,mod)
cb=f(n,b,mod)*power_func(f(b,b,mod),mod-2,mod)
ans=(-1+power_func(2,n,mod)-ca-cb)%mod
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right, bisect_left
from collections import Counter, deque
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import groupby, permutations, combinations, product
from sys import stdin, stderr


# 最大公約数（ユークリッドの互除法）
# Python3.5 で math.gcd()が追加され、
# AtCoder環境と最新環境でパッケージが分かれてしまったので、自分で書いておく
def gcd(x, y):
    return x if y == 0 else gcd(y, x % y)


# 拡張ユークリッド互除法
# 正整数x, y について、a*x + b*y == gcd(x,y)なるa,bを返す。
# 特に、互いに素なるx, yについては a*x + b*y == 1 となる a, b。
def exgcd(x, y):
    if y == 0:
        return 1, 0
    a, b = exgcd(y, x % y)
    return b, a - (x // y) * b


# 最小公倍数
def lcm(x, y):
    m = gcd(x, y)
    return (x // m) * (y // m)


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


def mod_pow(x, n):
    res = 1
    mod = 10**9 + 7
    while n > 0:
        if n % 2 == 1:
            res *= x
            res %= mod
        x *= x
        x %= mod
        n //= 2
    return res


def mod_comb(n, r):
    r = min(r, n-r)
    mod = 10 ** 9 + 7
    res = mod_fac(n, r)
    return res * mod_pow(mod_fac(r, r), mod - 2) % mod


def main():
    mod = 10**9 + 7
    n, a, b = [int(x) for x in input().split()]
    ret = mod_pow(2, n) - 1
    # print(ret, mod_comb(n,a), mod_comb(n, b))
    ret -= mod_comb(n, a)
    if ret < 0:
        ret += mod
    ret -= mod_comb(n, b)
    if ret < 0:
        ret += mod
    return ret


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

Submission status: Accepted

Solution code:
def modpow(a,b,mod):
    ans=1
    a=a%mod
    while b>0:
        if b%2==1:
            ans=(ans*a)%mod
        a=(a**2)%mod
        b=b//2
    return ans

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

ans=modpow(2,N,10**9+7)-1
c=1
d=1
for i in range(A):
  c=(c*(N-i))%(10**9+7)
for i in range(A):
  d=(d*(i+1))%(10**9+7)
d=modpow(d,10**9+5,10**9+7)
ans-=(c*d)%(10**9+7)
c=1
d=1
for i in range(B):
  c=(c*(N-i))%(10**9+7)
for i in range(B):
  d=(d*(i+1))%(10**9+7)
d=modpow(d,10**9+5,10**9+7)
ans-=(c*d)%(10**9+7)
while ans<0:
  ans+=10**9+7
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
from fractions import gcd 
from functools import reduce
import sys
sys.setrecursionlimit(200000000)
from inspect import currentframe


# my functions here!
#標準エラー出力
def printargs2err(*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),file=sys.stderr)
def debug(x):
    print(x,file=sys.stderr)
def printglobals():
    for (symbol, value) in globals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
def printlocals():
    for (symbol, value) in locals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
#入力（後でいじる）
def pin(type=int):
    return map(type,input().split())
#繰り返し自乗法だよ
#これはnのp乗をmで割ったあまりをだすよ
def modular_w_binary_method (n,m,p):
    ans=1 if n>0 else 0
    while(p>0):
        if p%2==1:
            ans=(ans*n)%m
        n=(n**2)%m
        p//=2
    return ans
#mod上でのaの逆元を出すよ
"""
    フェルマーの小定理より a**(p)%p==a isTrue
    これを利用すれば a**(p-2)%p==a**(-1) isTrue
    元と逆元とをかけてpで割れば1が余るよ！
"""
def modular_inverse(a,prime):
    return(modular_w_binary_method(a,prime,prime-2))



def conbination(n,a,mod=0):
    #cはイラない
    res=1 
    for s in range(a):
        res=(res*(n-s)*(modular_inverse(s+1,mod)))%mod

        
    return res
"""
"""

#solution:

#input
bigmod=(10**9)+7
#print(modular_w_binary_method(bigmod+10,bigmod,2))#modular_w_binary_methodはバグってない


n,a,b=pin()
an=0

allcombination=modular_w_binary_method(2, bigmod,n)
ans= allcombination -1 %bigmod
A=conbination(n,a,bigmod)
B=conbination(n,b,bigmod)
print((ans-A-B)%bigmod)

#print(["No","Yes"][cond])
#print([["NA","YYMM"],["MMYY","AMBIGUOUS"]][cMMYY][cYYMM])
"""
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""

Submission status: Accepted

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


mod = 1000000007

inv = [1] * 222222

# 0 = a * MOD/a + MOD % a
# a*MOD/a = -MOD%a
# a = -MOD%a * inv[MOD/a]
# inv[a] = -inv[MOD%a] * MOD/a
for i in range(2, 222222):
    inv[i] = -inv[mod % i] * (mod // i)
    inv[i] %= mod
    
def comb(n, a):
    res = 1
    for i in range(a):
        res *= n-i
        res *= inv[i+1]
        res %= mod
    return res

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

ans %= mod
if ans < 0:
    ans += mod

print(ans)

Submission status: Accepted

Solution code:
n, a, b = [int(x) for x in input().split()]

M = 10 ** 9 + 7
# return 2 ** n % 10^9 + 7
def pow2(n):
    pow2s = [2]
    i = 1
    while 2 ** i <= n:
        pow2s.append(pow2s[-1] ** 2 % M)
        i += 1
    r = 1
    for i in range(len(pow2s)):
        if n & (1 << i) != 0:
            r = (r * pow2s[i]) % M
    return r

def fact(n):
    r = 1
    for i in range(1, n + 1):
        r = (r * i) % M
    return r

def inv(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 x0

def comb(n, k):
    r1 = 1
    for i in range(k):
        r1 = r1 * (n - i) % M
    r2 = 1
    for i in range(k):
        r2 = r2 * (i + 1) % M
    return r1 * inv(r2, M) % M
r = pow2(n) - 1 - comb(n, a) - comb(n, b)
while r < 0:
    r += M
print(r)

Submission status: Accepted

Solution code:
def nCr(n, r):
    mod=10**9+7
    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

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

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

ans=(power_func(2,n,10**9+7)-1)-nCr(n,a)-nCr(n,b)

if ans<0:
       while ans<0:
              ans+=10**9+7
       print(ans)
else:
       print(ans)

Submission status: Accepted

Solution code:
mod = int(1e9 + 7)
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


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

base = 1
waru = 1000
syou = n // waru
amari = n % waru
kakeru = 2**waru % mod
for _ in range(syou):
    base = base * kakeru
    base %= mod
base = base * 2**amari
base %= mod

nca = cmb(n, a%mod)
ncb = cmb(n, b%mod)
answer = (base - 1 - nca - ncb) % mod
print(answer)

Submission status: Accepted

Solution code:
import math
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 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 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
def pow(x, n):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = (ans*x)
      ans%=MOD 
    x = (x*x)%MOD
    n = n >> 1 #ビットシフト
  return ans
def COMint():
  fac[0]=1
  fac[1]=1
  finv[0]=1
  finv[1]=1
  inv[1]=1
  for i in range(2,N+1):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD
def com(n,k):
  if n<k:
    return 0
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
MOD=10**9+7
#繰り返し２乗法を使う場合
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n,a,b=[int(x) for x in input().split()]
ans1 = pow(2,n)-1
N = n
a1=combination(n,a)
b1 = combination(n,b)
if ans1-a1%MOD-b1%MOD<0:
  print(((ans1-a1%MOD-b1%MOD)%MOD+MOD)%MOD)
else:
  print(ans1-a1%MOD-b1%MOD)

Submission status: Accepted

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

MOD = 10**9+7
from math import factorial

class Facts():
    # 階乗のメモ化
    # 組み合わせ数、順列数の計算を高速に行う
    def __init__(self, max_num=(2 * 10**5) + 1, p=10**9 + 7):
        self.p = p
        self.max_num = max_num
        self.fact = [1] * (self.max_num + 1)
        for i in range(1, self.max_num + 1):
            self.fact[i] = self.fact[i-1] * i
            self.fact[i] %= self.p

    def comb(self, n, k):
        # nCk mod p を求める
        if n < 0 or k < 0 or n < k:
            return 0
        if n == 0 or k == 0:
            return 1
        a = n
        for i in range(1, k):
            a *= (n-i)
            a %= MOD

        b = k
        for i in range(1, k):
            b *= (k-i)
            b %= MOD

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


    def power_func(self, a, b):
        # a^b mod p　を繰り返し二乗法で求める
        if b == 0:
            return 1
        if b % 2 == 0:
            d = self.power_func(a, b//2)
            return d*d % self.p
        if b % 2 == 1:
            return (a*self.power_func(a, b-1)) % self.p

class FLT:
    #フェルマーの小定理
    # a^(-1) = a^(m-2) mod p
    def __init__(self, mod=10**9+7):
        self.mod = mod

    def rep_sqr(self, base, k):
        if k == 0:
            return 1
        elif k % 2 == 0:
            return (self.rep_sqr(base, k // 2) ** 2) % self.mod
        else:
            return (self.rep_sqr(base, k - 1) * base) % self.mod

    def inv(self, a):
        # 逆元を取る
        return self.rep_sqr(a, self.mod-2)

fact = Facts()
flt = FLT()
a_comb = fact.comb(n, a)
b_comb = fact.comb(n, b)

ans = (flt.rep_sqr(2, n) - 1 - a_comb - b_comb) % MOD
print(ans)

Submission status: Accepted

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

com = [1] * (max(a, b) + 1)
inv = [0] * (max(a, b) + 1)
inv[1] = 1

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

for i in range(1, max(a,b)+1):
  com[i] = com[i-1] * ((n-i+1) % p) * inv[i] % p

ans = pow(2, n, p) - 1 - com[a] - com[b]

print(ans % p)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**9 + 7

def pow_mod_p(n, k, p):
  x = 1
  while k:
    if k % 2 == 1:
      x *= n
      x %= p
    n **= 2
    n %= p
    k >>= 1
  return x

def comb_mod_p(n, k, p):
  x = 1
  for ik in range(k):
    x *= ((n-ik) * pow_mod_p(ik+1, p-2, p))
    x %= p
  return x


def main():
  n, a, b = map(int, input().strip().split())
  sum = pow_mod_p(2, n, MAX) - 1
  sum = sum - comb_mod_p(n, a, MAX) - comb_mod_p(n, b, MAX)
  print(sum % MAX)


if __name__=='__main__':
  main()

Submission status: Accepted

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


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

sou = pow(2,n,mod) -1
ans = (sou - combination(n, a)-combination(n, b))
if (ans<0):
        ans += mod
if (ans<0):
        ans += mod
print(ans)

Submission status: Accepted

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

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

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

ans -= comb(a)
ans -= comb(b)
ans = (ans % mod + mod) % mod

print(ans)

Submission status: Accepted

Solution code:
def comb(n, k, MOD):
    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 = map(int, input().split())
mod = 10 ** 9 + 7
t = pow(2, N, mod) - 1
t -= comb(N, a, mod)
t %= mod
t -= comb(N, b, mod)
t %= mod
print(t)

Submission status: Accepted

Solution code:
mod = 10**9 + 7

def modpow(a, n, mod):
    res = 1
    while(n>0):
        if(n&1):
            res = res * a % mod
        a = (a**2) % mod
        n >>= 1
    return res

def modinv(a, mod):
    return modpow(a, mod-2, mod)

N, A, B = [int(i) for i in input().split()]
A = min(A, N-A)
B = min(B, N-B)
ext_A = 1
ext_B = 1
for ind, a in enumerate(range(N, N-A, -1)):
    ext_A *= a
    ext_A *= modinv(ind+1, mod)
    ext_A %= mod

for ind, b in enumerate(range(N, N-B, -1)):
    ext_B *= b
    ext_B *= modinv(ind+1, mod)
    ext_B %= mod

print((modpow(2, N, mod) - 1 -ext_A - ext_B)%mod)

Submission status: Accepted

Solution code:
n, a, b= [int(i) for i in input().split()]
mod = 10**9 + 7

def nCk(N, K, mod):
  ret = 1  
  for k in range(K):
    ret = (ret *(n - k)) %mod
    
  inv = [1 for _ in range(K+1)]
  finv = [1 for _ in range(K+1)]
  for i in range(2, K+1):
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] =finv[i-1] * inv[i] % mod
    
  return (ret * finv[K]) % mod

def mod_pow(a, n, mod):
  res = 1
  while  n > 0:
    if n & 1:
      res = (res * a ) % mod
    a = a * a  % mod
    n = n >> 1
  return res

print(int(mod_pow(2, n, mod) - nCk(n, a, mod) - nCk(n, b, mod) - 1)%mod)

Submission status: Accepted

Solution code:
n, a, b = map(int, input().split())
def powermod(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 combimod(n, r, p):
    a = 1
    for i in range(n-r+1, n+1):
        a *= i
        a %= p
    b = 1
    for i in range(1, r + 1):
        b *= i
        b %= p
    return (a * powermod(b, p-2, p)) % p
print((powermod(2, n, 1000000007) - combimod(n, a, 1000000007) - combimod(n, b, 1000000007) - 1 + 3000000021) % 1000000007)

Submission status: Accepted

Solution code:
N,a,b=map(int,input().split())
mod=10**9+7
n=max(a,b)
fra=[1]*(n+2)
inv=[1]*(n+2)
t=1
for i in range(1,n+2):
    t*=i
    t%=mod
    fra[i]=t
t=pow(fra[n+1],mod-2,mod)
for i in range(n+1,0,-1):
    inv[i]=t
    t*=i
    t%=mod
ans=pow(2,N,mod)-1
tmp=inv[a]
for i in range(1,a+1):
    tmp*=(N+1-i)%mod
    tmp%=mod
ans-=tmp
tmp=inv[b]
for i in range(1,b+1):
    tmp*=((N+1-i)%mod)
    tmp%=mod
ans-=tmp
ans%=mod
print(ans)

Submission status: Accepted

Solution code:
N,A,B = map(int,input().split())
def power_func(a,n,p=10**9+7):
    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 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
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
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
#ans = power_func(2,N) - 1 - combination(N,A) - combination(N,B)
ans = power_func(2,N) - 1
ans = ans if ans >= 0 else ans + 10 ** 9 + 7
ans = ans - combination(N,A)
ans = ans if ans >= 0 else ans + 10 ** 9 + 7
ans = ans - combination(N,B)
ans = ans if ans >= 0 else ans + 10 ** 9 + 7
print(ans)

Submission status: Accepted

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


c = max(a,b)
mod = 10**9+7
 
fact = [1,n]
finv = [1,1]
inv = [0,1]
 
for i in range(2,c+1):
    fact.append((fact[-1]*(n+1-i))%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
      
    return fact[r]*finv[r]%mod

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

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

    return K * x % mod
ans = pow_k(2,n,mod)-1-nCr(n,a,mod)-nCr(n,b,mod)

print(ans%mod)