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: Runtime Error

Solution code:
um_line=input().rstrip().split(" ")
num=int(num_line[0])
a=int(num_line[1])
b=int(num_line[2])

allcase=pow(2,num,1000000007)-1
#print(allcase)

if(a>num//2):
    a=num-a
if(b>num//2):
    b=num-b

abunshi=1
for i in range(num-a+1,num+1):
    abunshi*=i
#print(abunshi)

abumbo=1
for i in range(1,a+1):
    abumbo*=i
#print(abumbo)

abumbo=pow(abumbo,1000000005,1000000007)
#print(abumbo)

aminus=abunshi*abumbo%1000000007
#print(aminus)

bbunshi=1
for i in range(num-b+1,num+1):
    bbunshi*=i
#print(bbunshi)

bbumbo=1
for i in range(1,b+1):
    bbumbo*=i
#print(bbumbo)

bbumbo=pow(bbumbo,1000000005,1000000007)
#print(bbumbo)

bminus=bbunshi*bbumbo%1000000007
#print(bminus)

print((allcase-aminus-bminus)%1000000007)

Submission status: Runtime Error

Solution code:
MOD = 1000000007
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
    

fac = [0]*(n+1)
finv = [0]*(n+1)
inv = [0]*(n+1)

# テーブルを作る前処理
def COMinit(n, MOD):
    fac[0] = fac[1] = 1
    finv[0] = 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
    if (n < 0 or k < 0): return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


COMinit(n, MOD)
answer = modpow(2, n, MOD) - 1 - COM(n, a) - COM(n, b)
print(answer)

Submission status: Runtime Error

Solution code:
def comb_mod(n,m,mod):
  p = q = 1
  for i in range(m):
    p = p*(n-i) % mod
    q = q*(i+1) % mod
  return p* pow(q,mod-2,mod) % mod

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

print( (pow(2,n,mod)-1 -comb_mod(n,a,mod) -comb_mod(n,b,mod) ) % mod )

Submission status: Runtime Error

Solution code:
def kaijo(n):
    if n == 0:
        return 1
    if n == 1:
        return n
    else:
        return n * kaijo(n-1)

nandaandb = input()
nandaandb = nandaandb.split(' ')
ans = 0
n = int(nandaandb[0]) ; a = int(nandaandb[1]) ; b =int(nandaandb[2])
for k in range(1,a):
    ans +=  kaijo(n) / (kaijo(k)*kaijo(n-k))
for k in range(a+1, b):
    ans +=  kaijo(n) / (kaijo(k)*kaijo(n-k))
for k in range(b+1, n + 1):
    ans +=  kaijo(n) / (kaijo(k)*kaijo(n-k))
print(int(ans % (10 ** 9 + 7)))

Submission status: Runtime Error

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

#def combinations_count(n, r):
#    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
#print(combinations_count(4, 2))
# 6
ans = 0
X = 1
for i in range(1, N + 1):
  X = int(X * (N + 1 - i) / i)
  if i != a:
    if i != b:
      ans += X
      
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N,a,b = np.array(input().split()).astype(int)
mod = 10**9+7
import math
def power(x, n):
    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = ans*x%mod
        x = x*x%mod
        n = n >> 1 #ビットシフト
    return ans
def fact(m, n):
    val = 1
    for i in range(m, n + 1):
        val = (val*i)%mod
    return val
def cmb(N, r):
print((power(2, N)-1-cmb(N, a)-cmb(N, b))%mod)

Submission status: Runtime Error

Solution code:
import numpy as np
import math
N,a,b = np.array(input().split()).astype(int)
def cmb(N, r, mod):
  A = math.factorial(N)
  B = math.factorial(r)
  C = math.factorial(N-r)
  return A*B**(10**9+5)*C**(10**9+5)
print(2**N-1-cmb(N, a)-cmb(N, b))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np
import math
N,a,b = np.array(input().split()).astype(int)
print(2**N-1-math.factorial(N)//(math.factorial(a)*math.factorial(N-a))-math.factorial(N)//(math.factorial(b)*math.factorial(N-b))

Submission status: Runtime Error

Solution code:
import numpy as np
N,a,b = np.array(input().split()).astype(int)
for i in range(1,N+1):
  S = 0
  if((i!=a)&(i!=b)):
    S += math.factorial(N)/(math.factorial(i)*math.factorial(N-1))
print(S%(10**9+7))

Submission status: Runtime Error

Solution code:
N,a,b = np.array(input().split()).astype(int)
for i in range(1,N+1):
  S = 0
  if((i!=a)&(i!=b)):
    S += math.factorial(N)/(math.factorial(i)*math.factorial(N-1))
print(S%(10**9+7))

Submission status: Runtime Error

Solution code:
Sn = pow(2,n,MOD) - 1
if a > b:
    a,b = b,a
Xa, Xb = 1,1
Ya, Yb = 1,1
for i in range(b):
    if i < a:
        Xa = ( Xa * (n-i) ) % MOD
        Ya = ( Ya * pow((a-i),MOD-2, MOD)) % MOD
    Xb = ( Xb * (n-i) ) % MOD
    Yb = ( Yb * pow((b-i),MOD-2, MOD)) % MOD

ans = Sn - Xa*Ya % MOD - Xb*Yb % MOD
while ans < 0:
    ans += MOD
    
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque, Counter
from itertools import chain, combinations
import json
import numpy as np
import bisect
import sys

sys.setrecursionlimit(10 ** 10)
mem = {}

M = 10 ** 9 + 7


def C(a, b):
    if a < b * 2:
        return C(a, a - b)
    if a <= 1:
        return 1
    if b == 0:
        return 1
    if b == 1:
        return a

    if (a, b) not in mem:
        aa = C(a - 1, b)
        bb = C(a - 1, b - 1)
        mem[(a, b)] = aa + bb
    return mem[(a, b)]


def main():
    # N = int(input())
    n, a, b = [int(a) for a in input().split()]

    res = 0
    for k in range(1, n + 1):
        if k in [a, b]:
            continue
        res = (res + C(n, k)) % M
    print(res)

    # A = [int(a) for a in input().split()]
    #
    # A = sorted(A)
    # A = np.array(A)
    #


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque, Counter
from itertools import chain, combinations
import json
import numpy as np
import bisect
import sys

sys.setrecursionlimit(10 ** 6)
mem = {}

M = 10 ** 9 + 7


def C(a, b):
    if a < b * 2:
        return C(a, a - b)
    if a <= 1:
        return 1
    if b == 0:
        return 1
    if b == 1:
        return a

    if (a, b) not in mem:
        aa = C(a - 1, b)
        bb = C(a - 1, b - 1)
        mem[(a, b)] = aa + bb
    return mem[(a, b)]


def main():
    # N = int(input())
    n, a, b = [int(a) for a in input().split()]

    res = 0
    for k in range(1, n + 1):
        if k in [a, b]:
            continue
        res = (res + C(n, k)) % M
    print(res)

    # A = [int(a) for a in input().split()]
    #
    # A = sorted(A)
    # A = np.array(A)
    #


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N,a,b=map(int,input().split())
def kaijo(n):
  if n==1:
    return n
  return n*kaijo(n-1)
def nCk(n,k):
  return kaijo(n)/(kaijo(k)*kaijo(n-k))
s=2**N-nCk(N,a)-nCk(N,b)-1
print(s%(10**9+7))

Submission status: Runtime Error

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


def choose(n, r, mod):
    r = min(r, n - r)
    x = 1
    y = 1
    for i in range(r):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    y = pow(y, -2, mod)
    return x * y % mod


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

while ans < 0:
    ans += mod
print(ans)

Submission status: Runtime Error

Solution code:
from scipy.special import comb

if __name__ == '__main__':
   n, a, b = map(int, input().split())
   x = 0
   for i in range(1, n + 1):
       if i == a or i == b:
           pass
       else:
           x += comb(n, i, exact=True)

   print(x)

Submission status: Runtime Error

Solution code:
from scipy.special import comb

if __name__ == '__main__':
    n, a, b = map(int, input().split())
    x = 0
    for i in range(1, n + 1):
        if i == a or i == b:
            pass
        else:
            x += comb(n, i, exact=True)

    print(x)

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce
n, a, b = map(int, input().split())

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

def cmb(n,r):
    r = min(n-r, r)
    if r == 0: return
    over = reduce(mul, range(n, n-r, -1))
    under = reduce(mul, range(1, r+1))
    under = inv_felmat(under, 10**9 + 7)
    return over * under

all = pow(2, n, 10**9 + 7) - 1 
tmp1 = 1
tmp2 = 1
# for i in range(n-a+1, n+1):
#     tmp1 *= i
# for i in range(1, a+1):
#     tmp2 *= i
tmp1 = cmb(n,a) % (10**9 + 7)
tmp3 = cmb(n,b) % (10**9 + 7)
# for i in range(n-b+1, n+1):
#     tmp3 *= i
# for i in range(1, b+1):
#     tmp4 *= i

result = all - tmp1 - tmp3
print(result%(10**9 + 7))

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <numeric>
#include <functional>
using namespace std;
using ll = long long int;
ll AtMod = 1000000000+7;
ll RS(ll N, ll P, ll M);

int main(void){
  ll n,a,b;
  cin >> n >> a >> b;
  ll ans;
  ans = RS(2,n,AtMod) - 1;
  
  //nCaの値を求める
  ll a_comb = 1; ll bunbo = 1; ll bunshi = 1;
  a = min(a,n-a);
  for (ll i = 0; i < a; i++){
	bunshi = bunshi * (n-i) % AtMod;
    bunbo = bunbo * (i+1) % AtMod;
  }
  a_comb = bunshi * RS(bunbo,AtMod-2,AtMod) % AtMod;

  ll b_comb = 1; bunbo = 1; bunshi = 1;
  b = min(b,n-b);
  for (ll i = 0; i < b; i++){
	bunshi = bunshi * (n-i) % AtMod;
    bunbo = bunbo * (i+1) % AtMod;
  }
  b_comb = bunshi * RS(bunbo,AtMod-2,AtMod) % AtMod;
  
  cout << ans - (a_comb + b_comb)%AtMod << endl;
  return 0;
}

ll RS(ll N, ll P, ll M){
  if (P==0) return 1;
  else if (P%2==0){
    ll sq = RS(N,P/2,M);
    return sq*sq%M;
  }
  else{
    return N*RS(N,P-1,M)%M;
  }
}

Submission status: Runtime Error

Solution code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int acs(const void *a, const void *b) { 
  return *(int*)a - *(int*)b;
} /* 1,2,3,4.. */
int des(const void *a, const void *b) {
  return *(int*)b - *(int*)a;
} /* 8,7,6,5.. */
int cmp_char(const void *a, const void *b) { 
  return *(char*)a - *(char*)b;
} /* a,b,c,d.. */
int cmp_str(const void *a, const void *b) {
  return strcmp(*(const char **)a, *(const char **)b);
} /* aaa,aab.. */
#define min(a,b) (a < b ? a : b)
#define max(a,b) (a > b ? a : b)
#define rep(i, l, r) for (int i = l; i < r; i++)
#define MAX 100001
#define MOD 1000000007
#define INF 1000000009

typedef long long int lli;

void swap(lli *a, lli *b)
{
  lli tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}

// a ÷b (mod MOD) →(a % MOD) * modinv(b, MOD) % MDO
lli modinv(lli a, lli m) {
    lli b = m, u = 1, v = 0;
    while (b) {
        lli t = a / b;
        a -= t * b; swap(&a, &b);
        u -= t * v; swap(&u, &v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}


long long int combi(long long int n, long long int r) {
	long long int ans = 1;
	rep(i, 0, r) {
		ans = (ans * (n - i) % MOD) * modinv(r - i, MOD) % MOD;
	}
	return ans;
}

int main(void) {
	long long int n, a, b;
	scanf("%lld %lld %lld", &n, &a, &b);

	long long int sum = 1;
	for ( int i = n; i > 0; i-- )
		sum = sum * 2 % MOD;
	
	sum = (sum - combi(n, a) - combi(n, b) - 1 + MOD) % MOD;
	printf("%lld\n", sum);
  return 0;
}

Submission status: Runtime Error

Solution code:
def pow_mod(a, n, m): # (a^n) % m
    res = 1
    while n > 0:
        if n % 2 == 1:
            res = (res * a) % m
        a = (a * a) % m
        n = n // 2
    return res

def combi_mod(p, q, m):
    numerator, denominator = 1, 1
    for i in range(1, q+1):
        numerator *= (p - i + 1)
        numerator %= m
        denominator *= i
        denominator %= m
    return numerator * pow_mod(denominator, m-2, m) % m

n, a, b = list(map(int, input().split()))
res = pow_mod(2, n, M) - 1
res -=combi_mod(n, a, M)
if res < 0:
    res += M
res -= combi_mod(n, b, M)
if res < 0:
    res += M
print(res)

Submission status: Runtime Error

Solution code:
1000000000 141421 173205

Submission status: Runtime Error

Solution code:
# modなしの場合は，mod=1にする

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def nhr(self, n, r):  # 重複組合せ
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

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

def calc(k):
    ret = 1
    for i in range(k):
        ret = ret * (N - i) * pow(i + 1, -1, MOD) % MOD
    return ret

ans = pow(2, N, MOD) - 1 - calc(A) - calc(B)
print(ans % MOD)

Submission status: Runtime Error

Solution code:
# return x^{-1} % mod
# it take O(log{mod})
def mod_inverse(x, mod):
    return pow(x, mod-2, mod)

# return nCk % mod
# it take O(k)
def mod_comb(n, k, mod):
    numer, denom = 1, 1
    for i in range(k):
        # numer: 分子, denom: 分母
        numer = numer * ((n-i) % mod) % mod
        denom = denom * ((i+1) % mod) % mod

    return numer * mod_inverse(denom) % mod

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

Submission status: Runtime Error

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

# 逆元配列の作成
inv = [1] * (2 * (10 ** 5))
for i in range(2, 2 * (10 ** 5)):
    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  # 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: Runtime Error

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

import sys

def read_int_list(sep = " "):
    return [int(s) for s in sys.stdin.readline().rstrip().split(sep)]


def dprint(*args, **kwargs):
    return
    print(*args, **kwargs)


def choose(a, b, mod):
    numer, denomi = 1, 1 
    for i in range(0, b):
        denomi = (denomi * (i + 1)) % mod
        numer = ((a - i) * numer) % mod
    return (numer * pow(denomi, mod - 2, mod)) % mod


def main():
    mod = 1000_000_007
    n, a, b = read_int_list()
    ans = pow(2, n, mod)
    ans -= 1  # case for zero flowers
    ans -= choose(n, a, mod)
    ans -= choose(n, b, mod)
    if ans < 0:
        ans += mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

N = 2 * (10 ** 5)
inv = [1] * N
for i in range(2, N):
    inv[i] = -inv[mod % i] * (mod // i)
    inv[i] %= mod


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


ans = total - comb(n, a) - comb(n, b)
if ans < 0:
    ans += mod
print(ans)

Submission status: Runtime Error

Solution code:
n,a,b=map(int,input().split())
m=10**9+7
def com(n,k,m):
  p,q=1,1
  for i in range(n-k,n+1):
    p*=i
    p%=m
  for i in range(1,k+1):
    q*=i
    q%=m
  return p*pow(q,m-2,m)%m
ans=(pow(2,n,m)-ca-cb)%m

Submission status: Runtime Error

Solution code:
def comb(n_, k_, mod_=10**9+7):
    ans_ = 1
    for i in range(1,k_+1):
        ans_ *= ((n_+1-i)/i)
        ans_ = ans_%mod_
    return round(ans_//1%mod_)

n,a,b = map(int, input().split())
ans_tmp = (2**n-1)#%mod

for i in [a,b]:
    tmp = comb(n,i)
    ans_tmp -= tmp
print(ans_tmp%mod)

Submission status: Runtime Error

Solution code:
n = int(input())
print(pow(2,n)%(10**9+7))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

int A=1;
int fact(int n)
{
    int x = 1; // 0! = 1

    for (int i = 1; i <= n; ++i)
        x *= i;

    return x;
}


int main() {
  int n,a,b,mod=pow(19,9)+7,ans;
  cin>>n>>a>>b;
  for (int i=0;i<n;i++){
    ans+=fact(n)/(fact(i)*fact(n-i));
  }
  int aa,bb;
  aa=fact(n)/(fact(a)*fact(n-a));
  bb=fact(n)/(fact(b)*fact(n-b));
  cout<<ans-aa-bb<<endl;
  
}

Submission status: Runtime Error

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

mod = 10**9 + 7

import time
start = time.time()

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

modinv_table = [-1] * (b+1)
for i in range(1, b+1):
    modinv_table[i] = modinv(i)

end = time.time()
# print("time: ", end - start)

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

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

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


# print(binomial_coefficients2 (5, 2) % mod)

Submission status: Runtime Error

Solution code:
from math import factorial

def com(n, r):
  return factorial(n) // facotrial(n - r) // factorial(r)

n, a, b = [int(s) for s in input().split()]

print((2**n - com(n, a) - com(n, b) - 1) % (10**9 + 7))

Submission status: Runtime Error

Solution code:
from scipy.special import comb



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

print(((2 ** n) - comb(n, a, exact=True) - comb(n, b, exact=True))%(10 ** 9 + 7)-1)

Submission status: Runtime Error

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
from operator import mul
from functools import reduce
# a, b = [int(v) for v in input().split()]


def main():

    mod = 1000000007

    def modcmb(n, r, mod):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        over = reduce(lambda v1, v2: (v1 * v2) % mod, range(n, n-r, -1))
        under = reduce(lambda v1, v2: (v1 * v2) % mod, range(1, r+1))
        return over * pow(under, mod - 2, mod) % mod

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

    count = pow(2, n, mod) - 1
    count -= modcmb(n, a, mod)
    count -= modcmb(n, b, mod)

    if count < 0:
        count += mod * (-count // mod + 1)
    print(count % mod)


main()

Submission status: Runtime Error

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
from operator import mul
from functools import reduce
# a, b = [int(v) for v in input().split()]


def main():

    mod = 1000000007

    def modpow(n, k, mod):
        if k == 0:
            return 1
        val = modpow(n, k // 2, mod)
        val = (val * val) % mod
        if k % 2 != 0:
            val *= n
        return val

    def modcmb(n, r, mod):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        over = reduce(lambda v1, v2: (v1 * v2) % mod, range(n, n-r, -1))
        under = reduce(lambda v1, v2: (v1 * v2) % mod, range(1, r+1))
        return over * modpow(under, mod - 2, mod) % mod

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

    count = modpow(2, n, mod) - 1
    count -= modcmb(n, a, mod)
    count -= modcmb(n, b, mod)

    if count < 0:
        count += mod * (-count // mod + 1)
    print(count % mod)


main()

Submission status: Runtime Error

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
from operator import mul
from functools import reduce
# a, b = [int(v) for v in input().split()]


def main():

    mod = 1000000007

    def modpow(n, k, mod):
        if k == 0:
            return 1
        val = modpow(n, k // 2, mod)
        val = (val * val) % mod
        if k % 2 != 0:
            val *= n
        return val

    def modcmb(n, r, mod):
        if (r < 0 or r > n):
            return 0
        r = min(r, n - r)
        over = reduce(lambda v1, v2: v1 * v2 % mod, range(n, n-r, -1))
        under = reduce(lambda v1, v2: v1 * v2 % mod, range(1, r+1))
        return over * modpow(under, mod - 2, mod) % mod

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

    count = modpow(2, n, mod) - 1
    count -= modcmb(n, a, mod)
    count -= modcmb(n, b, mod)

    while count < 0:
        count += mod

    print(count % mod)


main()

Submission status: Runtime Error

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
from functools import reduce
# a, b = [int(v) for v in input().split()]


def main():

    mod = 1000000007

    def modpow(n, k, mod):
        if k == 0:
            return 1
        val = modpow(n, k // 2, mod)
        val = (val * val) % mod
        if k % 2 != 0:
            val *= n
        return val

    def modcmb(n, r, mod):
        if (r < 0 or r > n):
            return 0
        r = min(r, n - r)
        over = reduce(lambda v1, v2: v1 * v2 % mod, range(n, n-r, -1))
        under = reduce(lambda v1, v2: v1 * v2 % mod, range(1, r+1))
        return over * modpow(under, mod - 2, mod) % mod

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

    count = modpow(2, n, mod)
    count -= modcmb(n, a, mod)
    count -= modcmb(n, b, mod)

    while count < 0:
        count += mod

    print(count % mod)


main()

Submission status: Runtime Error

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

max=pow(2,n)

a_num=math.factorial(n)/(math.factorial(n - a) * math.factorial(a))
b_num=math.factorial(n)/(math.factorial(n - b) * math.factorial(b))

print((max-a_num-b_num) % (pow(10,9)+7))

Submission status: Runtime Error

Solution code:
	mod = 10**9+7
N, A, B = [int(i) for i in input().split()]


def ncr(n, r):
    r = min(r, n-r)
    res = 1
    m = n
    for _ in range(r):
        res *= m
        res %= mod
        m -= 1
    m = r
    for _ in range(r):
        res *= pow(m, mod-2, mod)
        res %= mod
        m -= 1
    return res


print((pow(2, N, mod)-1-ncr(N, A)-ncr(N, B)) % mod)

Submission status: Runtime Error

Solution code:
from math import factorial
N, a, b = map(int, input().split())
m=0
for i in range(N):
    if i==a, or i==b
        k=0
        m=m+k
    if not i== a-1 or i==b-1:
        k=factorial(N) // (factorial(N - (i+1)) * factorial(i+1))
        m=m+k
    print(m)

Submission status: Runtime Error

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

from functools import reduce
mod = 10**9+7


def nCk(n, k):
    # c = reduce(lambda x, y: x*y % mod, range(n, n-k, -1))
    # m = reduce(lambda x, y: x*y % mod, range(1, k+1))
    c = reduce(lambda x, y: x*y % mod, range(n, n-k+1, -1))
    m = reduce(lambda x, y: x*y % mod, range(1, k))
    return c*pow(m, mod-2, mod) % mod


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

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

Submission status: Runtime Error

Solution code:

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


def II():
    return int(input())

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def cmb2(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])

    return int(result)

    return count


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 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 modpow(a, n, mod):
    res = 1
    while n > 0:
        #print(n)

        if n & 1:
            res = res*a % mod
        a = a*a % mod
            #n >>= 1
        n>>=1

    return res


n,a,b=acinput()




#print(combination(n,a))
c=combination(n,min(n,n-a))+combination(n,min(b,n-b))



print((modpow(2,n,mod)-c-1)%mod)

Submission status: Runtime Error

Solution code:


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


def II():
    return int(input())

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def cmb2(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])

    return int(result)

    return count


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 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 modpow(a, n, mod):
    res = 1
    while n > 0:
        #print(n)

        if n & 1:
            res = res*a % mod
        a = a*a % mod
            #n >>= 1
        n>>=1

    return res


n,a,b=acinput()




#print(combination(n,a))
c=combination(n,min(n,n-a))+combination(n,min(b,n-b))



print((modpow(2,n,mod)-c-1)%mod)

Submission status: Runtime Error

Solution code:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)



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


def II():
    return int(input())

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def cmb2(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])

    return int(result)

    return count


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 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 modpow(a, n, mod):
    res = 1
    while n > 0:
        #print(n)

        if n & 1:
            res = res*a % mod
        a = a*a % mod
            #n >>= 1
        n>>=1

    return res


n,a,b=acinput()




#print(combination(n,a))
c=combination(n,min(n,n-a))+combination(n,min(b,n-b))



print((modpow(2,n,mod)-c-1)%mod)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
read = sys.stdin.read
n,a,b = [int(i) for i in read().split()]
MOD = 10**9+7
ans = pow(2,n,MOD)-1

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

  ans -= choose(n,a)
ans -= choose(n,b)
print(ans%MOD)

Submission status: Runtime Error

Solution code:
import sys
import math

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()


def inv_mod(a, N):
    """
    ユークリッドの互除法より
    aの逆元 ax = 1 (mod N)を満たすxを返す。
    O(log a)
    """

    def extgcd(a, b):
        """
        Extended Great Common Divisor
        ax + by = gcd(a, b) = dを満たすx, y, dを返す。
        """
        d = math.gcd(a, b)
        if b == 0:
            return 1, 0, a
        else:
            q, r = divmod(a, b)
            x, y, d = extgcd(b, r)
            s, t = y, x - q * y
            return s, t, d

    return extgcd(a, N)[0]


def bpm(x, y, N):
    """
     Bisection power method : 二分累乗法
     O(log y)でx^(y) mod N を求める。
    """
    ans = 1
    x %= MOD
    digit = int((math.log2(y) // 1 + 1))  # yの２進数表示の桁数
    for i in range(digit):
        if (y >> i) & 1 == 1:
            ans *= x
            ans %= MOD
        x **= 2
        x %= MOD
    return ans


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

nCa = 1
nCb = 1

inv_list = []

for i in range(max(a, b)):
    inv_list.append(inv_mod(i + 1, MOD))

for i in range(a):
    nCa *= inv_list[i]
    nCa %= MOD
    nCa *= n - i
    nCa %= MOD

for i in range(b):
    nCb *= inv_list[i]
    nCb %= MOD
    nCb *= n - i
    nCb %= MOD

print((bpm(2, n, MOD) - 1 - nCa - nCb) % MOD)