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

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


N = n  
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

fact = [ 0 for i in range(N+1)]
factinv = fact.copy()
inv = fact.copy()


fact[0], fact[1] = 1, 1
factinv[0], factinv[1] = 1, 1
inv[0], inv[1] = 0, 1
cmb_list = fact.copy()
cmb_list_sub1 = fact.copy()

for i in range(2, N + 1):
    fact[i] = (fact[i-1] * i) % p
    inv[i] = (-inv[p % i] * (p // i)) % p
    factinv[i] =(factinv[i-1] * inv[i]) % p
    

for r in range(1,N+1):
    cmb_list[r] = fact[N] * factinv[r] * factinv[N-r] % p

for r in range(1, n):
    cmb_list_sub1[r] =fact[n-1]*factinv[r]*factinv[n-1-r]%p

ans = 0
if k <= n-1:
    for i in range(0,k+1):
        ans = (ans + cmb_list[i] * cmb_list_sub1[n-1-i])%p
else:
    for i in range(0,n):
        ans = (ans + cmb_list[i] * cmb_list_sub1[n-1-i])%p
print(ans)

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

MOD = 10 ** 9 + 7

def factorial(n):
    global fct
    global invfct
    fct = [0] * (n + 1)
    fct[0] = 1
    for i in range(1, n+1):
        fct[i] = fct[i-1] * i % MOD
    invfct = [0] * (n + 1)
    invfct[n] = pow(fct[n], MOD - 2, MOD)
    for i in range(n-1, -1, -1):
        invfct[i] = invfct[i+1] * (i + 1) % MOD

def binomial(n, k):
    return fct[n] * invfct[n-k] % MOD * invfct[k] % MOD

factorial(2 * n)

if k >= n:
    print(binomial(2 * n - 1, n) % MOD)
else:
    answer = 0
    for i in range(k+1):
        answer += binomial(n, i) * binomial(n-1, i)
        answer %= MOD
    print(answer)

Solution (Python):
N,K=map(int, raw_input().split())
 
mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1,N+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod

can_zero_num=min(N-1,K)
ans=0
for zero_num in range(can_zero_num+1):
    ans+=ncr(N,zero_num)*ncr(N-1,N-zero_num-1)

print ans%mod

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

k=min(k,n-1)
t,c,h=1,1,1
for i in range(1,k+1):
  p=pow(i,m-2,m)
  c=(c*(n-i+1)* p)%m
  h=(h*(n-i)  * p)%m
  t=(t+c*h)%m

print(t%m)

Solution (Python):





MOD = 10 ** 9 + 7
MAX = 200010
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX
def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        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, k = map(int, input().split())

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

Solution (Python):
n,k=map(int,input().split())
mod=1000000007

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

def nCk(n,k):
    return fac[n]*inv[k]%mod*inv[n-k]%mod
ans = 0
for i in range(min(k+1,n)):
    ans += nCk(n,i)*nCk(n-1,i)%mod
    ans %=mod
print(ans)

Solution (Python):
n,k=map(int,input().split())
mod=10**9+7
U = 4*10**5+1
MOD = 10**9+7

fact = [1]*(U+1)
fact_inv = [1]*(U+1)

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

for i in range(U,0,-1):
	fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n,k):
  if k < 0 or k > n:
    return 0
  x = fact[n]
  x *= fact_inv[k]
  x %= MOD
  x *= fact_inv[n-k]
  x %= MOD
  return x

if n-1<=k:
    print(comb(2*n-1,n-1))
else:
    ans=0
    for i in range(1+k):
        ans+=comb(n,i)*comb(n-1,n-i-1)
        ans%=mod
    print(ans)

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






SIZE = 4 * 10 ** 5 + 1;
MOD = 10 ** 9 + 7  
SIZE += 1

inv = [0] * SIZE  
fac = [0] * SIZE  
finv = [0] * SIZE  

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

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

def choose(n, r):  
    if 0 <= r <= n:
        return (fac[n] * finv[r] % MOD) * finv[n - r] % MOD
    else:
        return 0
def chofuku(ball, box):  
    return choose(box + ball - 1, box)





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

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

def init_mod_c(lim=10**6, mod=10**9+7):
    fact = [1, 1] + [0] * (lim-1)
    fact_inv = [1, 1] + [0] * (lim-1)
    inv = [0, 1] + [0] * (lim-1)
    
    for i in range(2, lim+1):
        fact[i] = fact[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod

    def mod_c(n, m):
        if n < m or n < 0 or m < 0: return 0
        return fact[n] * (fact_inv[m] * fact_inv[n-m] % mod) % mod

    return mod_c

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

Solution (Python):
mod = 10**9+7
n,k = map(int,input().split())
ans = 0
mod = 10**9 + 7
inv_t = [0,1]
for i in range(2,n+2):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]
a = n
b = n-1
for i in range(1,min(n,k)+1):
    ans += a*b % mod
    a = a*(n-i)*inv_t[i+1] % mod
    b = b*(n-i-1)*inv_t[i+1] % mod
    ans %= mod
if k > 1:
    ans += 1
print(ans % mod)

Solution (Python):
MOD = 1000000007  
 
def solve(n: int, k: int):
    fact = [1] * (n+1)
    inv_fact = [1] * (n+1)
    for i in range(1, n+1):
        fact[i] = i*fact[i-1] % MOD
 
    inv_fact[-1] = pow(fact[-1], MOD-2, MOD)
    for i in range(n-1, 0, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
 
    def comb(n, r, MOD=MOD):
        return fact[n] * inv_fact[n-r] * inv_fact[r] % MOD
    
    ans = 0
    for i in range(min(k, n-1)+1):
        ans += comb(n, i) * comb(n-1, i) % MOD
        ans %= MOD
 
    return ans

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

print(solve(n, k))

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
n,k = mi()

mod = 10 ** 9 +7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

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

'''
ここは任意
'''

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


def combination2(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

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 )

def main():
    if k >= n -1:
        ans = combination2(2*n -1,n-1)
        print(ans)
    else:
        ans = 1
        for i in range(1,k+1):
            zero_comb = combination(n,i)
            cou = combination(n-1,n-i-1) * zero_comb % mod
            
            ans = (ans +cou) % mod
        print(ans)
main()

Solution (Python):
from sys import stdin



def prepare(n, p):
    fact = [1, 1]  
    factinv = [1, 1]  
    inv = [0, 1]  
    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)
    return fact, factinv


def cmb(n, r, p, fact, factinv):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p


def get_result(data):
    n, k = data
    mod = 10**9+7
    fact, factinv = prepare(n, mod)
    ans = 0
    for m in range(n):
        
        if m <= k:
            ans += (cmb(n, m, mod, fact, factinv) * cmb(n-1, n-m-1, mod, fact, factinv)) % mod
    ans %= mod
    return ans

if __name__ == '__main__':
    data = list(map(int, stdin.readline().split(' ')))
    result = get_result(data)
    print(result)

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

k = min([k, n-1])


ans = 0
key = 1

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def M(n): return ModInt(n)
def MI(): return M(I())

class ModInt():
    def __init__(self, n):
        self.n = n

    def __add__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n+x) % mod)

    def __sub__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n-x) % mod)

    def __mul__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n*x) % mod)

    def __truediv__(self, x):
        x = ModInt.xn(x)
        return ModInt(self.n * pow(x, mod-2, mod) % mod)

    @classmethod
    def xn(cls, x):
        if isinstance(x, ModInt):
            return x.n
        return x

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

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

cms = 10**6
cm = [0] * cms

def comb_init():
    cm[0] = 1
    for i in range(1, cms):
        cm[i] = cm[i-1] * i % mod

def comb(a, b):
    return (cm[a] * inv(cm[a-b]) % mod) * inv(cm[b]) % mod

def h(a,b):
    return comb(a+b-1, b)

def main():
    n,k = LI()
    comb_init()
    r = M(1)
    t = M(1)
    for i in range(1, min(n-1,k)+1):
        t *= n-i+1
        t /= i
        r += t * h(n-i,i)

    return r


print(main())

Solution (Python):
MAX = 4*10**5
bikkuri=[1]
mod = 10**9+7
for i in range(1,MAX+1):
    bikkuri.append((bikkuri[-1]*i)%mod)

def Comb(n,k):
    ans = bikkuri[n]*pow(bikkuri[k],mod-2,mod)*pow(bikkuri[n-k],mod-2,mod)
    ans %=mod
    return ans
    
n,k = map(int,input().split())
if n-1 <= k:
    ans = Comb(2*n-1,n)
    print(ans)
else:
    tmp = 0
    for i in range(k+1):
        tmp += Comb(n,i)*Comb(n-1,i)
        tmp %= mod
    print(tmp)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
n,k = map(int,readline().split())
mod = 10**9+7
def pow(n,p,mod=10**9+7): 
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod
def factrial_memo(n=10**6+1,mod=10**9+7):
    fact = [1, 1]
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % mod)
    return fact
def fermat_cmb(n, r, mod=10**9+7): 
    return fact[n] * pow(fact[r],mod-2) * pow(fact[n-r],mod-2) %mod
fact = factrial_memo()

if k > n-1: 
    ans = fermat_cmb(2*n-1,n)
else: 
    ans = 1
    for i in range(1,k+1): 
        ans += fermat_cmb(n,i)*fermat_cmb(n-1,i)
        
        
        
        ans %= mod

print(ans)

Solution (Python):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
mod=10**9+7
def bp(a,n):
        r=1
        while(n):
           if n%2:
              r=r*a%mod
           a=a*a%mod
           n>>=1
        return r
[n,k]=i2()
if n<=k:
   x=1
   for i in range(n-1):
      x*=2*n-1-i
      x%=mod
   y=1
   for i in range(n-1):
      y*=i+1
      y%=mod
   print((x*bp(y,10**9+5))%mod)   
   
else:
   x=1
   y=1
   t=1
   for i in range(k):
      t*=i+1
      t%=mod
      y*=n-1-i
      y%=mod
      y*=n-i
      y%=mod
      c=bp(t,10**9+5)
      x+=y*c*c
      x%=mod
   print(x)

Solution (Python):

import numpy as np

class Combination : 
    def __init__ (self, N=10**6, mod=10**9+7) :
        self.mod = mod
        self.fact = [1, 1]
        self.factinv = [1, 1]
        self.inv = [0, 1]
        for i in range(2, N+1) :
            self.fact.append( (self.fact[-1]  * i) % mod )
            self.inv .append( (-self.inv[mod%i] * (mod//i) ) % mod )
            self.factinv.append( (self.factinv[-1] * self.inv[-1]) % mod )

    def nCr(self, n, r) :
        if ( r < 0 ) or ( n < r ) : return 0
        r = min(r, n-r)
        return self.fact[n]*self.factinv[r]*self.factinv[n-r] % self.mod

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


n, k = map(int, input().split())

mod = 10**9+7
comb = Combination(2*10**5+100)
ans = 0
for m in range(min(n+1,k+1)) :
    ans = ans%mod + (comb.nCr(n,m) * comb.nCr(n-1, n-m-1))%mod
print(ans%mod)

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

class Combination:
    def __init__(self, N=10**6, mod=10**9 + 7):
        self.mod = mod
        self.N = N
        self.fact = [1, 1]  
        self.factinv = [1, 1]  
        self.inv = [0, 1]  
        for i in range(2, N + 1):
            self.fact.append((self.fact[-1] * i) % mod)
            self.inv.append((-self.inv[mod % i] * (mod // i)) % mod)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % mod)

    def nCr(self, n, r):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] * self.factinv[n-r] % self.mod

comb = Combination(2 * 10**5+100)
ans = 0
mod = 10**9 + 7
for ki in range(min(n+1, k+1)):
    ans = ans % mod + (comb.nCr(n, ki) * comb.nCr(n-1, n-ki-1)) % mod
print(ans%mod)

Solution (Python):
n,k = [int(x) for x in input().split()]
mod = 10**9+7
MAX_N = 10**6
 
fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1] = pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
    fact_inv[i] = fact_inv[i+1]*(i+1)%mod
 
 
def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod
if k>=n:
  print(mod_comb_k(2*n-1,n,mod))
else:
  res=1
  for i in range(1,k+1):
    res = (res+mod_comb_k(n,i,mod)*mod_comb_k(n-1,n-i-1,mod))%mod
  print(res)

Solution (Python):
MOD = 10**9 + 7
MOD_t_MAX = 2*(10**5)+1

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_MAX):
        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 MOD_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
def MOD_pow(a, n):
    res = 1
    while n > 0:
        if (n & 1):
            res = res * a % MOD
        a = a * a % MOD
        n = n // 2
    return res

def main():
    n, k = map(int, input().split())
    MOD_COM_init()
    ans = 0
    for i in range(n):
        if k-i < 0:
            continue
        x = MOD_COM(n, i) * MOD_COM(n-1, n-i-1) % MOD
        ans += x
        ans %= MOD
    print(ans)
if __name__ == "__main__":
    main()

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

class Combination:
    """
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv
n,k = inpl()
m = min(n-1,k)
res = 1
if m == 1:
    print((n-1)*n%mod)
    quit()
comb = Combination(n+10)
for i in range(m):
    res += comb(n,i+1) * comb(n-1,n-i-2)
    res %= mod
print(res)

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

MOD = 10**9 + 7
MAX = 2 * n + 1
fact = [1] * (MAX + 1)  
finv = [1] * (MAX + 1)  
iinv = [1] * (MAX + 1)  

for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * iinv[i] % MOD


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD


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

print(ans)

Solution (Python):

import sys
from itertools import count, islice

MOD = 1000000007  

def mod_factorial_iter():
    acc = 1
    yield 1
    for i in count(1):
        acc = acc * i % MOD
        yield acc

def solve(n: int, k: int):
    mod_factorials = tuple(islice(mod_factorial_iter(), n+2))
    def comb(a, b):
        return (mod_factorials[a] * (pow(mod_factorials[a-b], MOD-2, MOD) * pow(mod_factorials[b], MOD-2, MOD)) % MOD) % MOD
    ans = 1
    for i in range(1, min(n-1, k)+1):
        t = (comb(n-1, i) * comb(n, i)) % MOD
        ans = (ans + t) % MOD
    return ans



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  
    k = int(next(tokens))  
    print(solve(n, k))

if __name__ == '__main__':
    main()

Solution (Python):
def comb(p,q,A,fact = None,factinv = None): 
  if (q < 0) or (p < q):
    return 0
  q = min(q, p - q)
  return fact[p] * factinv[q] * factinv[p-q] % A
def main():
  mod = 10 ** 9 + 7
  n, k = map(int, input().split())
  
  fact = [1] 
  factinv = [1,1] 
  inv = [0,1] 
  
  for a in range(2, n + 1):
    inv.append((-inv[mod % a] * (mod // a)) % mod)
  for i in range(1, n + 1):
    fact.append((fact[-1] * i) % mod)
  for j in range(2, n + 1):
    factinv.append((factinv[-1] * inv[j]) % mod)
  ans = 0
  for i in range(min(n,k+1)): 
    ans = (ans + comb(n,i,mod,fact,factinv)*comb(n-1,i,mod,fact,factinv)) % mod
  print(ans)
main()

Solution (Python):
MOD = 10**9 + 7
MAX = int(2e5)


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


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD


def main():
    n, k = map(int, input().split())
    ans = 0
    for i in range(min(n-1, k)+1):
        
        
        tmp = FACT[n] * INV[i] * INV[n-i] % MOD
        tmp = (tmp * FACT[n-1] * INV[n-i-1] * INV[i]) % MOD
        ans = (ans + tmp) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def pow_mod(a, b, p):
    res = 1
    mul = a
    for i in range(len(bin(b)) - 2):
        if (1 << i) & b:
            res = (res * mul) % p
        mul = (mul ** 2) % p
    return res


def comb_mod(n, r, p, factorial, invert_factorial):
    return (factorial[n] * invert_factorial[r] * invert_factorial[n - r]) % p


def main():
    p = 10 ** 9 + 7
    n, k = map(int, input().split())

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

    invert_factorial = [0] * (n + 1)
    invert_factorial[n] = pow_mod(factorial[n], p - 2, p)
    for i in range(n - 1, -1, -1):
        invert_factorial[i] = (invert_factorial[i + 1] * (i + 1)) % p

    res = 0
    for i in range(min(k + 1, n)):
        res = (res + comb_mod(n, i, p, factorial, invert_factorial)
               * comb_mod(n - 1, i, p, factorial, invert_factorial)) % p
    print(res)


main()

Solution (Python):
def pow_mod(a, b, p):
    res = 1
    mul = a
    for i in range(len(bin(b)) - 2):
        if (1 << i) & b:
            res = (res * mul) % p
        mul = (mul ** 2) % p
    return res


def comb_mod(n, r, p, factorial=None, invert_factorial=None):
    return (factorial[n] * invert_factorial[r] * invert_factorial[n - r]) % p


def main():
    p = 10 ** 9 + 7
    n, k = map(int, input().split())

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

    invert_factorial = [0] * (n + 1)
    invert_factorial[n] = pow_mod(factorial[n], p - 2, p)
    for i in range(n - 1, -1, -1):
        invert_factorial[i] = (invert_factorial[i + 1] * (i + 1)) % p

    res = 0
    for i in range(min(k + 1, n)):
        res = (res + comb_mod(n, i, p, factorial, invert_factorial)
               * comb_mod(n - 1, i, p, factorial, invert_factorial)) % p
    print(res)


main()

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

R = 200010
f = [1]*R
p = 1
for i in range(1, R):
    p = f[i] = p*i%mod

finv = [1]*R
p = finv[-1] = pow(f[-1], mod-2, mod)
for i in range(R-2, 0, -1):
    p = finv[i] = p*(i+1)%mod

def comb(n, k):
    return f[n]*finv[n-k]*finv[k]%mod

ans = 0
for m in range(min(k, n-1)+1):
    x = comb(n, m)
    y = comb(n-1, m)
    ans += x*y%mod

print(ans%mod)

Solution (Python):
U = 5*10**5
MOD = 10**9+7
 
def main():
  fact = [1]*(U+1)
  fact_inv = [1]*(U+1)

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

  for i in range(U,0,-1):
      fact_inv[i-1] = (fact_inv[i]*i)%MOD

  def comb(n, k):
      if k < 0 or k > n:
          return 0
      z = fact[n]
      z *= fact_inv[k]
      z *= fact_inv[n-k]
      z %= MOD
      return z

  n, k = map(int, input().split())
  if k+1 < n:
    ans = 0
    for i in range(k+1, n):
      ans += comb(n, i) * comb(n-1, i)
      ans %= MOD
    ans = comb(2*n-1, n) - ans
    ans %= MOD
  else:
    ans = comb(2*n-1, n)
  print(ans)
  
if __name__ == "__main__":
  main()

Solution (Python):

def cmb1(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
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())
mod = 10**9+7
ans = 0
k_ = min(n-1, k)
for i in range(k_+1):
    ans += cmb1(n, i, mod) * cmb1(n-i-1+i, i, mod)
    ans %= mod
print(ans)

Solution (Python):

def cmb1(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
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())
mod = 10**9+7
ans = 0
k_ = min(n-1, k)
for i in range(k_+1):
    ans += cmb1(n, i, mod) * cmb1(n-i-1+i, i, mod)
    ans %= mod
print(ans)

Solution (Python):
class Combinatorics:
    def __init__(self, N, mod):
        '''
        Preprocess for calculating binomial coefficients nCr (0 <= r <= n, 0 <= n <= N)
        over the finite field Z/(mod)Z.
        Input:
            N (int): maximum n
            mod (int): a prime number. The order of the field Z/(mod)Z over which nCr is calculated.
        '''
        self.mod = mod
        self.fact = {i: None for i in range(N+1)}         
        self.inverse = {i: None for i in range(1, N+1)}   
        self.fact_inverse = {i: None for i in range(N+1)} 
        
        
        self.fact[0] = self.fact[1] = 1
        self.fact_inverse[0] = self.fact_inverse[1] = 1
        self.inverse[1] = 1
        for i in range(2, N+1):
            self.fact[i] = i * self.fact[i-1] % self.mod
            q, r = divmod(self.mod, i)
            self.inverse[i] = (- (q % self.mod) * self.inverse[r]) % self.mod
            self.fact_inverse[i] = self.inverse[i] * self.fact_inverse[i-1] % self.mod
    
    def perm(self, n, r):
        '''
        Calculate nPr = n! / (n-r)! % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return (self.fact[n] * self.fact_inverse[n-r]) % self.mod
    
    def binom(self, n, r):
        '''
        Calculate nCr = n! /(r! (n-r)!) % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return self.fact[n] * (self.fact_inverse[r] * self.fact_inverse[n-r] % self.mod) % self.mod
        
    def hom(self, n, r):
        '''
        Calculate nHr = {n+r-1}Cr % mod.
        Assign r objects to one of n classes.
        Arrangement of r circles and n-1 partitions:
            o o o | o o | | | o | | | o o | | o
        '''
        if n == 0 and r > 0:
            return 0
        if n >= 0 and r == 0:
            return 1
        return self.binom(n + r - 1, r)
    
MOD = 10**9 + 7
N, K = map(int, input().split())
com = Combinatorics(N, MOD)
ans = 0
for i in range(min(K, N-1) + 1):
    ans += (com.binom(N, i) * com.hom(N-i, i)) % MOD
    ans %= MOD
print(ans)

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


def combinations(n, r, MOD):
    if (r < 0) or (n < r):
        return 0

    r = min(r, n - r)
    return fact[n] * fact_inv[r] * fact_inv[n - r] % MOD


fact = [1, 1]
fact_inv = [1, 1]
inv = [0, 1]

for i in range(2, n + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    fact_inv.append((fact_inv[-1] * inv[-1]) % MOD)


s = 0
for num_zero in range(min(k + 1, n)):
    
    x = combinations(n, num_zero, MOD)

    
    y = combinations(n - 1, n - num_zero - 1, MOD)

    s += (x * y) % MOD


print(s % MOD)

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

up = [1] * (n + 1)
down = [0] * (n + 1)
for i in range(1, n + 1):
  up[i] = (up[i - 1] * i) % D
down[n] = pow(up[n], D - 2, D)
for i in range(n, 0, -1):
  down[i - 1] = (down[i] * i) % D
  
def cmd(n, r, D):
  if r < 0 or r > n:
    return 0
  else:
    return (up[n] * down[r] * down[n - r]) % D

A = 0
k = min(k, n-1)
t = 0
while t <=k:
  A = (A + cmd(n-1, t, D) * cmd(n, t, D)) % D
  t = t+1
print (A)

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

MOD = 1000000007

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

def comb(n, k):
    if k < 0 or k > n:
        return 0
    return fact[n] * ifact[k] * ifact[n - k] % MOD

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

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


def make_cmb_table(n):
    fact = [1]
    for i in range(1, n+1):
        fact.append(fact[i-1] * i % MOD)

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


def cmb(n, r, table):
    if r > n:
        return 0
    return table[0][n] * table[1][n - r] * table[1][r] % MOD


def main():
    n, k = map(int, input().split())
    k = min(k, n-1)
    table = make_cmb_table(n)
    ans = 0
    for i in range(k+1):
        ans += cmb(n, i, table) * cmb((n-i-1)+i, i, table) % MOD
        ans %= MOD
    print(ans)


main()

Solution (Python):
n, k = map(int, input().split())
mod = 10**9+7
m = min(n-1,k)
ans = 0

f = [1]
fi = [1]
for i in range(n):
    f.append(f[i]*(i+1) % mod)
    fi.append(pow(f[i+1], mod-2, mod))

def comb_mod(n, r, mod):
    return f[n] * fi[r] * fi[n-r] % mod

for m in range(m+1):
    ans += comb_mod(n, m, mod) * comb_mod(n-1, m, mod) % mod

print(ans%mod)

Solution (Python):
MAX = 10 ** 5 * 2
mod = 10 ** 9 + 7
frac = [1]
inv_frac=[1]
def pow(a, n):
    if n == 0 : return  1
    elif n == 1 : return a
    tmp = pow(a, n//2)
    tmp = (tmp * tmp) % mod
    if n % 2 == 1 :
        tmp = (tmp * a) % mod
    return tmp
def inv(x):
    return pow(x, mod - 2 )
for i in range(1,MAX + 1 ):
    frac.append( (frac[-1] * i) % mod )
    inv_frac.append(inv(frac[-1])%mod)
def comb(n, k):
    if k >= n or k < 0 : return 1
    return (frac[n]*inv_frac[n-k] * inv_frac[k]) %mod
n,k = map(int,input().split())
count=0
b=inv(n)
for i in range(min(n,k+1)):
    a=comb(n,i)
    count=(count+a*a*(n-i)*b)%mod
print(count)

Solution (Python):
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
SIZE=4*10**5+1; MOD=10**9+7 
 
SIZE += 1
inv = [0]*SIZE  
fac = [0]*SIZE  
finv = [0]*SIZE 
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD
 
def choose(n,r): 
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0
def resolve():
    n, k = lr()
    ans = choose(2*n-1, n)
    if n-1 > k:
        for i in range(1, n-k):
            ans -= choose(n, i)*choose(n-1, n-i)
            ans %= MOD
    print(ans)
resolve()