Problem:


Score : 500 points

Problem Statement

There is a building with n rooms, numbered 1 to n.

We can move from any room to any other room in the building.

Let us call the following event a move: a person in some room i goes to another room j~ (i \neq j).

Initially, there was one person in each room in the building.

After that, we know that there were exactly k moves happened up to now.

We are interested in the number of people in each of the n rooms now. How many combinations of numbers of people in the n rooms are possible?

Find the count modulo (10^9 + 7).

Constraints

All values in input are integers.

3 \leq n \leq 2 \times 10^5

2 \leq k \leq 10^9

Input

Input is given from Standard Input in the following format:

n k

Output

Print the number of possible combinations of numbers of people in the n rooms now, modulo (10^9 + 7).

Sample Input 1

3 2

Sample Output 1

10

Let c_1, c_2, and c_3 be the number of people in Room 1, 2, and 3 now, respectively. There are 10 possible combination of (c_1, c_2, c_3):

(0, 0, 3)

(0, 1, 2)

(0, 2, 1)

(0, 3, 0)

(1, 0, 2)

(1, 1, 1)

(1, 2, 0)

(2, 0, 1)

(2, 1, 0)

(3, 0, 0)

For example, (c_1, c_2, c_3) will be (0, 1, 2) if the person in Room 1 goes to Room 2 and then one of the persons in Room 2 goes to Room 3.

Sample Input 2

200000 1000000000

Sample Output 2

607923868

Print the count modulo (10^9 + 7).

Sample Input 3

15 6

Sample Output 3

22583772



Sample input:
3 2


Sample output:
10

Submission status: Accepted

Solution code:
from itertools import accumulate


class Combination:
    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


if __name__ == "__main__":
    N, K = map(int, input().split())
    MOD = 10**9+7
    comb = Combination(2*10**5+5, MOD)

    ans = []
    for i in range(min(N - 1, K) + 1):
        val = comb(N, i) * comb(N - 1, i) % MOD
        ans.append(val)

    answer = 0
    while ans:
        answer = (answer + ans.pop()) % MOD
    print(answer)

Submission status: Accepted

Solution code:
def comb(n, r):
    if r<0 or r>n:
        return 0
    r=min(r, n-r)
    return g1[n]*g2[r]*g2[n-r]%MOD

MOD=10**9+7
MAXN=400000+10
g1=[1, 1]
g2=[1, 1]
inverse=[0, 1]

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

N, K=map(int, input().split())
if K>=N-1:
    print(comb(N*2-1, N))
else:
    ans=1
    for i in range(1, K+1):
        ans=(ans+(comb(N-1, i)*comb(N, i))%MOD)%MOD
    print(ans)

Submission status: Accepted

Solution code:
N=2*10**5+1
mod=10**9+7
f=[None]*N
fi=[None]*N
f[0]=1
for i in range(1,N):
  f[i]=i*f[i-1]%mod
for i in range(N):
  fi[i]=pow(f[i],mod-2,mod)
def com(n,k):
  return f[n]*fi[n-k]%mod*fi[k]%mod
def hcom(n,k):
  return com(n+k-1,n-1)
n,k=map(int,input().split())
ans=1
for i in range(1,min(k+1,n)):
  ans=(ans+com(n,i)*hcom(n-i,i)%mod)%mod
print(ans)

Submission status: Accepted

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

mod = 10**9+7
ans = 1%mod
left_combination = 1
right_combination = 1

for i in range(1,min(k,n-1)+1):
    left_combination = (left_combination*(n+1-i)*pow(i,mod-2,mod))%mod
    right_combination = (right_combination*(n-i)*pow(i,mod-2,mod))%mod
    ans = (ans + (left_combination*right_combination)%mod)%mod

print(ans)

Submission status: Accepted

Solution code:
import math
import sys

sys.setrecursionlimit(10**9)

MOD = 10**9+7

n, k = map(int, input().split())
k = min(k, n-1)

fact = [1]
for i in range(1, 10**6):
    fact.append((fact[i-1]*i)%MOD)

inv = [None]*10**6
def inv_fact(n):
    if inv[n] == None:
        inv[n] = pow(fact[n], MOD-2, MOD)
    return inv[n]

def comb(n, r):
    return (fact[n]*inv_fact(n-r)*inv_fact(r))%MOD

ans = 0
for i in range(k+1):
    ans = (ans + comb(n-1, i)*comb(n, i))%MOD
print(ans)

Submission status: Accepted

Solution code:
MAX = 1000005
MOD = 10**9+7
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()


N, K = map(int, input().split())
ans = 0
for i in range(min(K, N)+1):  # 空にできるのはK部屋または、N-1部屋までのみ。
    ans += COM(N, i) * COM(N-1, i)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
MOD = 1000000007

fact = [0] * (N+1)
finv = [0] * len(fact)
inv  = [0] * len(fact)

fact[0] = fact[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, len(fact)):
    fact[i] = fact[i-1] * i % MOD
#    inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
    inv[i] = - inv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD

nCr = lambda n, r: fact[n] * finv[n-r] * finv[r] % MOD
nHr = lambda n, r: nCr(n+r-1, r)

# ans = 0
# for i in range(min(N-1, K) + 1):
#     ans += nCr(N, i) * nHr(N-i, i)
# ans = sum(nCr(N, i) * nHr(N-i, i) for i in range(min(N-1, K) + 1))
ans = sum(nCr(N, i) * nCr(N-1, i) for i in range(min(N-1, K) + 1))
print(ans % MOD)

Submission status: Accepted

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

from functools import reduce
# table_size = 510000
table_size = 2*10**5+1  # 200001
mod = 10**9+7


# Combination の計算を最適化する必要がある?
# def nCr(n, r):
#     numerator = reduce(lambda x, y: x * y % mod, range(n, n - r, -1), 1)
#     denominator = reduce(lambda x, y: x * y % mod, range(1, r + 1), 1)
#     return numerator * pow(denominator, mod-2, mod) % mod

class Combination:
    def __init__(self):
        self.fac = [None for _ in range(table_size)]
        self.finv = [None for _ in range(table_size)]
        self.inv = [None for _ in range(table_size)]

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

        for i in range(2, table_size):
            self.fac[i] = self.fac[i - 1] * i % mod
            # この逆元 (inv[i]) の計算は拡張ユークリッドの互除法をもとにしている
            # self.inv[i] = mod - self.inv[mod % i] * (mod // i) % mod
            self.inv[i] = pow(i, mod - 2, mod)
            self.finv[i] = self.finv[i - 1] * self.inv[i] % mod

    def nCr(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0

        return self.fac[n] * (self.finv[r] * self.finv[n - r] % mod) % mod


n, k = map(int, input().split())
# n, k = 3, 2  # Expected: 10
# n, k = 200000, 1000000000  # Expected: 607923868
# n, k = 15, 6  # Expected: 22583772

c = Combination()

k = min(k, n - 1)
total = 0
for i in range(k + 1):
    total += c.nCr(n - 1, i) * c.nCr(n, i)
    total %= mod

print(total)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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

p = 10 ** 9 + 7
N = 2* 10 ** 5+2  # N は必要分だけ用意する
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 solve():
  n,k = (int(i) for i in input().split())
  mod = 10**9+7
  if n-k <= 1:
    #任意の部屋に移動可能
    comba = 1
    inva = 1
    for i in range(1,n+1):
      comba *= (n+i-1)
      inva *= i
      comba %= mod
      inva %= mod
    comba *= pow(inva,10**9+5,mod)
    comba %= mod
    print(comba)
  else:
    #n <= 2**10^5
    #k <= 2**10^5
    ans = 0
    
    
    
    for i in range(0,k+1):
      ans += cmb(n,i,mod)*cmb(n-1,i,mod)
      ans %= mod
    
    print(ans)
  
solve()

Submission status: Accepted

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

from functools import reduce
# table_size = 510000
table_size = 2*10**5+1  # 200001
mod = 10**9+7


# Combination の計算を最適化する必要がある?
# def nCr(n, r):
#     numerator = reduce(lambda x, y: x * y % mod, range(n, n - r, -1), 1)
#     denominator = reduce(lambda x, y: x * y % mod, range(1, r + 1), 1)
#     return numerator * pow(denominator, mod-2, mod) % mod

class Combination:
    def __init__(self):
        self.fac = [None for _ in range(table_size)]
        self.finv = [None for _ in range(table_size)]
        self.inv = [None for _ in range(table_size)]

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

        for i in range(2, table_size):
            self.fac[i] = self.fac[i - 1] * i % mod
            self.inv[i] = mod - self.inv[mod % i] * (mod // i) % mod
            self.finv[i] = self.finv[i - 1] * self.inv[i] % mod

    def nCr(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0

        return self.fac[n] * (self.finv[r] * self.finv[n - r] % mod) % mod


n, k = map(int, input().split())
# n, k = 3, 2  # Expected: 10
# n, k = 200000, 1000000000  # Expected: 607923868
# n, k = 15, 6  # Expected: 22583772

c = Combination()

k = min(k, n - 1)
total = 0
for i in range(k + 1):
    total += c.nCr(n - 1, i) * c.nCr(n, i)
    total %= mod

print(total)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

class ModCmb:
    def __init__(self, size):
        self.inv = [1] * (size + 1)
        self.fact = [1] * (size + 1)
        temp_inv = [1] * (size + 1)
        for i in range(2, size + 1):
            temp_inv[i] = ( -(MOD // i) * temp_inv[MOD%i] ) % MOD
        for i in range(2, size + 1):
            self.fact[i] = self.fact[i-1] * i % MOD
            self.inv[i] = self.inv[i-1] * temp_inv[i] % MOD

    def cmb(self, n, r):
        if n <= 1 or n == r:
            return 1
        elif r == 1:
            return n
        else:
            return  (self.fact[n] * self.inv[r] % MOD ) * self.inv[n-r] % MOD

mc = ModCmb(n)

ans = n * (n-1) + 1

for m in range(2, min(n, k+1)):
    ans = ( ans + ((mc.cmb(n, m) % MOD) * mc.cmb(n-1, m)) % MOD ) % MOD

print(ans)

Submission status: Accepted

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

from functools import reduce
table_size = 510000
# table_size = 5100000
mod = 10**9+7


# Combination の計算を最適化する必要がある?
# def nCr(n, r):
#     numerator = reduce(lambda x, y: x * y % mod, range(n, n - r, -1), 1)
#     denominator = reduce(lambda x, y: x * y % mod, range(1, r + 1), 1)
#     return numerator * pow(denominator, mod-2, mod) % mod

class Combination:
    def __init__(self):
        self.fac = [None for _ in range(table_size)]
        self.finv = [None for _ in range(table_size)]
        self.inv = [None for _ in range(table_size)]

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

        for i in range(2, table_size):
            self.fac[i] = self.fac[i - 1] * i % mod
            self.inv[i] = mod - self.inv[mod % i] * (mod // i) % mod
            self.finv[i] = self.finv[i - 1] * self.inv[i] % mod

    def nCr(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0

        return self.fac[n] * (self.finv[r] * self.finv[n - r] % mod) % mod


n, k = map(int, input().split())
# n, k = 3, 2  # Expected: 10
# n, k = 200000, 1000000000  # Expected: 607923868
# n, k = 15, 6  # Expected: 22583772

c = Combination()

# この分岐がよくわかっていない
if n < k:
    print(c.nCr(2 * n - 1, n))
else:
    total = 0
    for i in range(k + 1):
        total += c.nCr(n - 1, i) * c.nCr(n, i)
        total %= mod

    print(total)

Submission status: Accepted

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

def modcomb(n,a,mod):
    cnt = 1
    for i in range(a):
        cnt *= (n-i)
        cnt *= pow(i+1,mod-2,mod)
        cnt %= mod
    # print(cnt)
    return cnt

def modconb(n,mod):
    # テーブルを作る
    fac = [0]*(n+1)
    finv = [0]*(n+1)
    inv = [0]*(n+1)  

    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
    return fac,finv
    # return(fac[n]*(finv[k]*finv[n-k]%mod)%mod)


cnt = 0
if n-1 >= K:
    fac1,finv1 = modconb(n,mod)
    for k in range(K+1):
        c1 = fac1[n]*(finv1[k]*finv1[n-k]%mod)%mod
        c2 = fac1[n-1]*(finv1[k]*finv1[n-1-k]%mod)%mod
        cnt += c1*c2
        cnt %= mod
    print(cnt%mod)
else:
    cnt1 = modcomb(2*(n-1),n-1,mod)
    cnt2 = modcomb(2*(n-1),n,mod)
    ans = (cnt1+cnt2)%mod
    print(ans)

Submission status: Accepted

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)


facto = None
ifacto = None

def precompute_facto(n, mod):
    global facto, ifacto
    facto = [1] * (n + 1)
    for i in range(1, n + 1):
        facto[i] = (facto[i - 1] * i) % mod
    ifacto = [1] * (n + 1)
    ifacto[n] = mod_inv(1, facto[n], mod)
    for i in range(0, n):
        p = n - i
        ifacto[p - 1] = ifacto[p] * p % mod


def mod_inv(a, b, mod):
    return (a * pow(b, mod - 2, mod)) % mod


def choose(a, b, mod):
    return facto[a] * ifacto[a - b] % mod * ifacto[b] % mod


def multi_choose(a, b, mod):
    return choose(a + b - 1, b, mod)


def main():
    mod = 1000000007
    n, k = read_int_list()
    precompute_facto(n, mod)
    ans = 0
    for i in range(0, min(k, n - 1) + 1):
        ans = (ans + choose(n, i, mod) * multi_choose(n - i, i, mod)) % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

p = 10 ** 9 + 7
N = 10 ** 5 *5  # N は必要分だけ用意する
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 + 3):
    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

ans = 0
if k < n:
    for i in range(k+1):
        ans += cmb(n,i,p)*cmb(n-1,n-i-1,p)
        ans %= p
else:
    for i in range(n):
        ans += cmb(n,i,p)*cmb(n-1,n-i-1,p)
        ans %= p

print(ans)

Submission status: Accepted

Solution code:
# a^n mod p
def exp_by_sq(a, n, p):
    if n == 0:
        exp = 1
    elif n == 1:
        exp = a % p
    elif  n % 2 == 0:
        exp = exp_by_sq(a * a % p, n // 2, p)
    else:
        exp = a * exp_by_sq(a * a % p, (n - 1) // 2, p) % p
    return exp % p

# 入力
n, k = [int(x) for x in input().split()]

p = 10 ** 9 + 7
# Find n * sum_{j = 0..m}{(n choose j)^2 * (n - j)}
m = min(n, k)
# 最初の2項
binom = n # n choose 1  mod p
ans = n * ((n * n - n + 1) % p) % p  # (n choose 0)^2 * (n - 0) + (n choose 1)^2 * (n - 1)
inv = [0, 1]
inv_n = exp_by_sq(n, p - 2, p)  # n^(-1) mod p

for i in range(2, m + 1):
    inv_i = ( inv[p % i] * (p - p//i) ) % p  # inverse of i
    inv.append(inv_i)
    binom = (binom * (n - i + 1) % p) * inv_i % p
    ans = (ans + (binom * binom % p) * (n - i)) % p

ans = ans * inv_n % p
print(ans)

Submission status: Accepted

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

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

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

n,k=map(int,input().split())
k=min(n,k)
ans=0
for i in range(k+1):
  ans+=(cmb(n,i,mod)*cmb(n-1 ,i,mod))%mod
ans=ans%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, k = map(int, input().split())
ans = 0
v = n
w = n - 1

ans = 1 + v * w
mod = 10 ** 9 + 7

for i in range(2, min(n,k) + 1):
    #print(f'v={v} n={n} i={i}')
    v = ((n - i + 1) * v)  * pow(i, mod - 2, mod)
    v %= mod
    w = ((n - i) * w) * pow(i, mod - 2, mod)
    w %= mod
    #print(v, w)
    ans += (v * w) % mod
    ans %= mod



print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
n,k=map(int,input().split())
ans=0
comb1=1 #初期値はNC0=1
comb2=1 #初期値は(N-1)C0=1
for i in range(min(k+1,n)): #0人の部屋は高々N-1個しか
 # 存在しないので操作回数は高々min(K,N-1)回となる
 ans+=comb1*comb2 #0人の部屋がi個のときの場合の数は
 # NCi*(N-1)Ci
 ans%=mod
 comb1*=(n-i)*pow(i+1,mod-2,mod) #NC(i+1)はNC
 # i*(N-i)/(i+1)で求められる
 comb1%=mod
 comb2*=(n-1-i)*pow(i+1,mod-2,mod) #(N-1)C(i+1
 # )は(N-1)Ci*((N-1)-i)/(i+1)で求められる
 comb2%=mod
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


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


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


INV = dict()
def inv(a, mod):
    if a in INV:
        return INV[a]
    i = pow(a, mod - 2, mod)
    INV[a] = i
    return i 


def C(F, a, b, mod):
    return F[a] * inv(F[a - b], mod) * inv(F[b], mod) % mod 


def main():
    N, K = read_values()
    mod = 10 ** 9 + 7
    F = functional(5 * 10 ** 5, mod)
    res = 0
    if N <= K:
        res = C(F, 2 * N - 1, N - 1, mod)
    else:
        for k in range(K + 1):
            res += C(F, N, k, mod) * C(F, N - 1 , k, mod) % mod
    
    print(res % mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


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


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


INV = dict()
def inv(a, mod):
    if a in INV:
        return INV[a]
    i = pow(a, mod - 2, mod)
    INV[a] = i
    return i 


def C(F, a, b, mod):
    return F[a] * inv(F[a - b], mod) * inv(F[b], mod) % mod 


def main():
    N, K = read_values()
    mod = 10 ** 9 + 7
    F = functional(5 * 10 ** 5, mod)
    res = 0
    if N <= K:
        res = C(F, 2 * N - 1, N - 1, mod)
    else:
        c = C(F, N - 1, 0, mod)
        for k in range(K + 1):
            res += pow(c, 2, mod) * N * inv(N - k, mod) % mod
            c *= ((N - k - 1) * inv(k + 1, mod)) % mod
            c %= mod
    
    print(res % mod)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


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


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


def inv(a, mod):
    return pow(a, mod - 2, mod)


def C(F, a, b, mod):
    return F[a] * inv(F[a - b], mod) * inv(F[b], mod) % mod 


def main():
    N, K = read_values()
    mod = 10 ** 9 + 7
    F = functional(5 * 10 ** 5, mod)
    res = 0
    if N <= K:
        res = C(F, 2 * N - 1, N - 1, mod)
    else:
        c = C(F, N - 1, 0, mod)
        for k in range(K + 1):
            res += pow(c, 2, mod) * N * inv(N - k, mod) % mod
            c *= ((N - k - 1) * inv(k + 1, mod)) % mod
            c %= mod
    
    print(res % mod)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

def cmap(n,k):
    x = [1]
    y = [1]
    c = [1]
    for i in range(k+1):
        x.append((x[i]*(n-i))%mod)
        y.append((y[i]*(i+1))%mod)
        c.append((x[i+1]*pow(y[i+1],mod-2,mod))%mod)
    return c
    
#print(cmap(n,n))
nc=cmap(n,n-1)
n1c=cmap(n-1,n-2)

ans = 0
for i in range(min(n-1,k)+1):
    ans = (ans+(nc[i]*n1c[i]))%mod

print(ans)

Submission status: Accepted

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

max_len = 2 * n - 1  # 適宜変更する
mod = 10**9 + 7


def modinv(x):
    '''
    xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
    Python標準のpowは割った余りを出すことも可能。
    '''
    return pow(x, mod-2, mod)


# 二項係数の左側の数字の最大値を max_len　とする。nとかだと他の変数と被りそうなので。
# factori_table = [1, 1, 2, 6, 24, 120, ...] 要は factori_table[n] = n!
# 計算時間はO(max_len * log(mod))
modinv_table = [-1] * (max_len + 1)
modinv_table[0] = None  # 万が一使っていたときにできるだけ早期に原因特定できるようにしたいので、Noneにしておく。
factori_table = [1] * (max_len + 1)
factori_inv_table = [1] * (max_len + 1)
for i in range(1, max_len + 1):
    factori_table[i] = factori_table[i-1] * (i) % mod

modinv_table[1] = 1

for i in range(2, max_len + 1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod
    factori_inv_table[i] = factori_inv_table[i-1] * modinv_table[i] % mod


def binomial_coefficients(n, k):
    '''
    n! / (k! * (n-k)! )
    0 <= k <= nを満たさないときは変な値を返してしまうので、先にNoneを返すことにする。
    場合によっては0のほうが適切かもしれない。
    '''
    if not 0 <= k <= n:
        return None
    return (factori_table[n] * factori_inv_table[k] * factori_inv_table[n-k]) % mod


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



if k >= n-1:
    # nHn = 2n-1 C n
    print(binomial_coefficients(2 * n - 1, n))
else:
    # 移動がk回←→ 人数0の部屋がk個以下
    # 人数0の部屋がちょうどj個のものは
    # nCj(人数0の部屋の選び方) * jH(n-j) (余剰のj人を残りの部屋に入れる)
    ans = 0
    for j in range(k+1):
        if j == 0:
            ans += 1
        else:
            ans += binomial_coefficients(n, j) * binomial_coefficients(n-1, j) 
            ans %= mod
    print(ans)

Submission status: Accepted

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

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


def nCr(n, r):
    if n < 0 or r < 0 or n < r:
        return 0
    return fact[n] * (finv[r] * finv[n - r] % mod) % mod


ans = 1
limit = min(k+1, n)
for i in range(1, limit):
    vacant = i
    fill = n-i
    add = i
    pattern = nCr(n, vacant) * nCr(add+fill-1, add)
    ans = (ans + pattern) % mod

print(ans)

Submission status: Accepted

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
    n, k = map(int, input().split())

    fact1 = [0] * (n + 1)  # 1/P!
    fact1[0] = 1

    for i in range(1, n + 1):
        fact1[i] = (fact1[i - 1] * i) % mod

    fact2 = [0] * (n + 1)  # P!
    fact2[n] = pow(fact1[n], mod-2, mod)

    for i in range(n, 0, -1):
        fact2[i - 1] = (fact2[i] * i) % mod

    def cmb2(n, r, mod):
        if r < 0 or r > n:
            return 0
        return fact1[n] * fact2[n - r] * fact2[r] % mod

    ans = 0
    for i in range(min(n - 1, k) + 1):
        ans += cmb2(n, i, mod) * cmb2(n - 1, i, mod)
        ans %= mod
    print(ans)


main()

Submission status: Accepted

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

mod = 10**9 + 7

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

# 二項係数の左側の数字の最大値を max_len　とする。nとかだと他の変数と被りそうなので。
# factori_table = [1, 1, 2, 6, 24, 120, ...] 要は factori_table[n] = n!
# 計算時間はO(max_len * log(mod))

max_len = 2 * n - 1 #適宜変更する

factori_table = [1] * (max_len + 1)
factori_inv_table = [1] * (max_len + 1)
for i in range(1, max_len + 1):
    factori_table[i] = factori_table[i-1] * (i) % mod
    factori_inv_table[i] = modinv(factori_table[i])

def binomial_coefficients(n, k):
    # n! / (k! * (n-k)! )
    if k <= 0 or k >= n:
        return 1
    return (factori_table[n] * factori_inv_table[k] * factori_inv_table[n-k]) % mod

if k >= n-1:
    # nHn = 2n-1 C n
    print(binomial_coefficients(2 * n - 1, n))
else:
    # 移動がk回←→ 人数0の部屋がk個以下
    # 人数0の部屋がちょうどj個のものは
    # nCj(人数0の部屋の選び方) * jH(n-j) (余剰のj人を残りの部屋に入れる)
    ans = 0
    for j in range(k+1):
        if j == 0:
            ans += 1
        else:
            ans += binomial_coefficients(n, j) * binomial_coefficients(n-1, j) 
            ans %= mod
    print(ans)

Submission status: Accepted

Solution code:
class Factorial:
    def __init__(self,n,mod):
        self.f=f=[0]*(n+1)
        f[0]=b=1
        self.mod=mod
        for i in range(1,n+1):f[i]=b=b*i%mod
        self.inv=inv=[0]*(n+1)
        inv[n]=b=pow(self.f[n],mod-2,mod)
        for i in range(n,0,-1):inv[i-1]=b=b*i%mod
    def factorial(self,i):
        return self.f[i]
    def ifactorial(self,i):
        return self.inv[i]
    def comb(self,n,k):
        if n>=k:
            return self.f[n]*self.inv[n-k]%self.mod*self.inv[k]%self.mod
        else:
            return 0
    def homp(self,n,k):
        return self.comb(n+k-1,n-1)
M=10**9+7
n,k=map(int,input().split())
f=Factorial(n*2,M)
c=f.comb
h=f.homp
a=0
for i in range(min(k+1,n)):
    a+=c(n,i)*h(n-i,i)%M
print(a%M)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
max_N = 2 * 10**5

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)

fac = [1] * (max_N + 1)
for i in range(1, max_N + 1):
	fac[i] = (i * fac[i - 1]) % mod

fac_inv = [1] * (max_N + 1)
fac_inv[max_N] = mod_inv(fac[max_N])
for i in range(max_N - 1, -1, -1):
	fac_inv[i] = (fac_inv[i + 1] * (i + 1)) % mod

def choose(n, k):
	return (((fac[n] * fac_inv[k]) % mod) * fac_inv[n - k]) % mod


if __name__ == "__main__":
	line = input().split(" ")
	N, K = int(line[0]), int(line[1])
	K = min(K, N - 1)

	ans = 0
	for i in range(K + 1):
		ans = (ans + (choose(N, i) * choose(N - i - 1 + i, i)) % mod) % mod

	print(ans)

Submission status: Accepted

Solution code:
def comb_list(n, r, mod):
    ret = [1]
    for i in range(1, r+1):
        ret.append(ret[-1] * (n+1-i) * pow(i, mod-2, mod) % mod)
    return ret

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

r = min(k,n-1)
ans = 0
nCl = comb_list(n, r, mod)
n1Cl = comb_list(n-1, r, mod)

for i in range(r+1):
    ans = (ans + nCl[i] * n1Cl[i]) % mod

print(ans)

Submission status: Accepted

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

n,k = map(int,input().split())
P = 10**9+7

ans = 1
nCl = 1
n1Cl = 1
for l in range(1,min(k+1,n)):
    nCl = nCl*(n+1-l)*modinv(l,P)%P
    n1Cl = n1Cl*(n-l)*modinv(l,P)%P
    ans = (ans+nCl*n1Cl)%P

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
k = min(k, n - 1)
p = 10 ** 9 + 7
size = n + 100
f_list = [1] * size
if_list = [1] * size
for i in range(1, size):
    f_list[i] = (f_list[i - 1] * i) % p
    if_list[i] = pow(f_list[i], p-2, p)

def cmb(n, r):
    return f_list[n] * if_list[r] * if_list[n-r] % p

# 初期値は0人の部屋が0個の場合
ans = 1
for i in range(1, k + 1):
    ans += cmb(n, i) * cmb(n - 1, i)
    ans = ans % p
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def combination(a, b):
    if b > a - b:
        return combination(a, a - b)
    return fact[a] * ifact[b] * ifact[a-b]


MOD = 10**9+7
n, k = map(int, input().split())
k = min(k, n-1)
# 階乗を前処理
fact = defaultdict(int)
fact[0] = 1
for i in range(1, n+1):
    fact[i] = fact[i-1] * i
    fact[i] %= MOD
# 階乗の逆元を前処理
ifact = defaultdict(int)
ifact[n] = pow(fact[n], MOD-2, MOD)
for i in reversed(range(1, n + 1)):
    ifact[i-1] = ifact[i] * i
    ifact[i-1] %= MOD

ans = 0
for i in range(k+1):
    ans += combination(n, i) * combination((n-i-1)+i, i)
    ans %= MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict


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 = fact[a] * ifact[b] * ifact[a-b]
    return ans


MOD = 10**9+7
n, k = map(int, input().split())
k = min(k, n-1)

fact = defaultdict(int)
fact[0] = 1
for i in range(1, n+1):
    fact[i] = fact[i-1] * i
    fact[i] %= MOD

ifact = defaultdict(int)
ifact[n] = mod_inv(fact[n], MOD)
for i in reversed(range(1, n + 1)):
    ifact[i-1] = ifact[i] * i
    ifact[i-1] %= MOD

ans = 0
for i in range(k+1):
    ans += combination(n, i) * combination((n-i-1)+i, i)
    ans %= MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict


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 = fact[a] * ifact[b] * ifact[a-b]
    return ans


MOD = 10**9+7
n, k = map(int, input().split())
k = min(k, n-1)

fact = defaultdict(int)
fact[0] = 1
ifact = defaultdict(int)
ifact[0] = 1
for i in range(1, n+1):
    fact[i] = fact[i-1] * i
    fact[i] %= MOD
    ifact[i] = mod_inv(fact[i], MOD)
    ifact[i] %= MOD

ans = 0
for i in range(k+1):
    ans += combination(n, i) * combination((n-i-1)+i, i)
    ans %= MOD

print(ans % MOD)

Submission status: Accepted

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


def pow(x, t):
    if t == 0:
        return 1
    a = pow(x, t >> 1)
    return a * a * (x ** (t & 1)) % MOD


fact = [0] * (n + 1)
fact[0] = 1
for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD
ifact = [0] * (n + 1)
ifact[n] = pow(fact[n], MOD - 2)
for i in range(n, 0, -1):
    ifact[i - 1] = ifact[i] * i
    ifact[i - 1] %= MOD


def nCr(x, y):
    if y < 0 or y > x:
        return 0
    return fact[x] * ifact[y] * ifact[x - y] % MOD


ans = 0
for i in range(min(n - 1, k) + 1):
    ans += nCr(n, i) * nCr(n - 1, i)
    ans %= MOD
print(ans)