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())
MOD = 10**9 + 7
MAX_N = 10**6 + 5
fact = [0]*(MAX_N)
fact_inv = [0]*(MAX_N)
fact[0] = 1
for i in range(MAX_N-1):
    fact[i+1] = fact[i]*(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 comb(n, k):
    return fact[n]*fact_inv[k] % MOD * fact_inv[n-k] % MOD


if K >= N:
    print(comb(2*N-1, N-1))
    exit()

ans = 1
for i in range(1, K+1):
    ans += comb(N, i)*comb(N-1, i) % MOD
    ans %= MOD
print(ans)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    n, k = map(int, readline().split())

    COM_MAX = n

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

    for i in range(2, COM_MAX + 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, r):
        if n < 0 or r < 0 or n < r:
            return 0
        return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD

    ans = 0
    for r in range(min(n, k + 1)):
        ans = (ans + com(n, r) * com(n - 1, r)) % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    n, k = map(int, readline().split())

    COM_MAX = n

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

    for i in range(2, COM_MAX + 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, r):
        if n < 0 or r < 0 or n < r:
            return 0
        return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD

    ans = 0
    for r in range(min(n, k + 1)):
        ans = (ans + com(n, r) * com(n - 1, r)) % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
n,k=map(int,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 f(n,k,mod):
  return fact[n]*fact_inv[k]%mod*fact_inv[n-k] %mod

ans=0

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

print(ans)

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

mod=10**9+7

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

ans=1
comb1=1
comb2=1

for i in range(1,min(n-1,k)+1):
    comb1*=(n-i+1)*modinv(i)
    comb2*=(n-i)*modinv(i)
    comb1%=mod
    comb2%=mod

    ans+=comb1*comb2
    ans%=mod

print(ans)

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

list_size = 4*10**5 + 1
 
f_list = [1] * list_size
f_r_list = [1] * list_size
 
for i in range(list_size-1):
	f_list[i+1] = (f_list[i] * (i+1)) % mod
 
f_r_list[-1] = pow(f_list[-1], mod - 2, mod)
 
for i in range(list_size-2, -1, -1):
	f_r_list[i] = (f_r_list[i+1] * (i+1)) % mod
 
def comb(n, r, mod):
	if n < r or r < 0:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (f_list[n] * f_r_list[n-r] * f_r_list[r]) % mod


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

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






lim = 10 ** 6 + 1
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, lim + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    
    factinv.append((factinv[-1] * inv[-1]) % mod)

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

N, K = getNM()

ans = 0
for i in range(min(K + 1, N)):
    
    cnt = cmb(N, i) * cmb(N - i + i - 1, i)
    ans += cnt
    ans %= mod
print(ans % mod)

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


mod = 10**9+7
N = 10**6  
fact = [1, 1]  
factinv = [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)
	factinv.append((factinv[-1]*inv[-1])%mod)

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

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

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


MOD = int(1e09) + 7



def solve():
    MAX = 2 * 10 ** 5 + 10
    fac = [0] * MAX
    inv = [0] * MAX
    finv = [0] * MAX
    fac[0] = fac[1] = finv[0] = finv[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 cmb(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
    N, K = Scanner.map_int()
    ans = 0
    for i in range(min(N - 1, K) + 1):
        ans += cmb(N, i) * cmb(N - 1, i)
        ans %= MOD
    print(ans)


def main():
    
    
    
    
    
    
    solve()


if __name__ == "__main__":
    main()

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

fact = [0] * (n+1)
inv_fact = [0] * (n+1)

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

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


def nCk(n, k):
    return fact[n] * inv_fact[k] * inv_fact[n-k] % MOD
  
ans = 1
for i in range(1, n):
    if i > k:
      break
    ans += nCk(n, i) * nCk(n-1, n-i-1) % MOD
print(ans % MOD)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class CmbMod:
    def __init__(self, n, p):
        """
        二項係数nCr(n個の区別できるものからr個のものを選ぶ組み合わせの数)をpで割った余りを求める
        """
        self.n = n
        self.p = p
        self.fact = [1, 1]
        self.factinv = [1, 1]
        self.inv = [0, 1]

    def cmb_mod(self, n, r):
        """
        二項係数nCr(mod p)をO(r)にて計算。nが大きいがrは小さい時に使用。
        """
        numer, denom = 1, 1
        for i in range(r):
            numer = (numer * (n - i)) % self.p
            denom = (denom * (i + 1)) % self.p
        return (numer * pow(denom, self.p - 2, self.p)) % self.p

    def prep(self):
        """
        二項係数nCr(mod p)をO(1)で求める為の前処理をO(N)にて実行。
        """
        for i in range(2, self.n + 1):
            self.fact.append((self.fact[-1] * i) % self.p)
            self.inv.append((-self.inv[self.p % i] * (self.p // i)) % self.p)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % self.p)

    def cmb_mod_with_prep(self, n, r):
        """
        二項係数nCr(mod p)をO(1)で求める。事前にprepを実行する事。
        """
        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.p


def resolve():
    n, k = map(int, input().split())
    k = min(k, n - 1)
    cb = CmbMod(n + 1, mod)
    cb.prep()
    res = 0
    for i in range(k + 1):
        res += (cb.cmb_mod_with_prep(n, i) * cb.cmb_mod_with_prep(n - 1, i)) % mod
        res %= mod
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
n, k = map(int, input().split())
mod = 10 ** 9 + 7
def comb(n, r):
    if n < r:return 0
    if n < 0 or k < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
fa = [1] * (n + 1)
fi = [1] * (n + 1)
for i in range(1, n + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
ans = 0
for i in range(min(k, n - 1) + 1):
    ans += comb(n, i) * comb(n - 1, i) % mod
print(ans % mod)

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

fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
Mod = 10**9+7
def COMinit():
  
  for i in range(2, n+10):
    fac.append(fac[-1]*i%Mod)
    inv.append((-inv[Mod%i] * (Mod//i)) % Mod)
    finv.append(finv[-1] * inv[-1] % Mod)


def COM(n, k):
  if n < 0 or k < 0 or n < k:
    return 0
  return fac[n] * (finv[k] * finv[n-k] % Mod) % Mod


COMinit()

ans = 0

for i in range(min(n, k)+1):
  ans += (COM(n, i) * COM(n-1, n-i-1))
  ans %= Mod

print(ans)

Solution (Python):

class Combination:
    def __init__(self, n_max, mod=10 ** 9 + 7):
        
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max + 1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod - 2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    
    

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

    def nCr(self, n, r):
        if not 0 <= r <= n:
            return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

    def nPr(self, n, r):
        if not 0 <= r <= n:
            return 0
        return self.fac[n] * self.facinv[n - r] % self.mod

    def nHr(self, n, r):
        if (n == 0 and r > 0) or r < 0:
            return 0
        return self.fac[n + r - 1] * self.facinv[r] % self.mod * self.facinv[n - 1] % self.mod


def resolve():
    MOD = 10**9+7
    N, K = map(int, input().split())

    r = min(N-1, K)
    cmb = Combination(N)

    ans = 0
    for i in range(r+1):
        ans += cmb.nCr(N, i) * cmb.nHr(N-i, i)
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):
class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def com(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def pom(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod


N, K = map(int, input().split())
mod = 10**9+7
c = Combi(4*10**5+100, mod)
if N <= K:
    print(c.com(2*N-1, N-1))
else:
    ans = c.com(2*N-1, N-1)
    for i in range(K+1, N):
        ans -= c.com(N-1, N-i-1)*c.com(N, i)
    print(ans % mod)

Solution (Python):
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, K = map(int, input().split())
n = N*2
r = min(N, K+1)
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)

ans = 0
for i in range(r):
    ans += cmb(N, i, mod) * cmb(N-1, i, mod)
if K == 1:
    ans -= 1
print(ans % mod)

Solution (Python):
n,k = map(int,input().split())
mod = 1000000007
def comb(n,k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return fac[n]*finv[k]%mod*finv[n-k]%mod
fac = [1]*(n+1)
finv = [1]*(n+1)
for i in range(1,n+1):
    fac[i] = fac[i-1]*i%mod
    finv[i] = pow(fac[i],mod-2,mod)

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



M = 10**9+7
N = 4*10**5+3 

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

g1 = [None] * (N+1) 
g2 = [None] * (N+1) 
inverse = [None] * (N+1) 
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

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

n,k = map(int, input().split())
M = 10**9+7
if k<n:
    ans = 0
    for p in range(k+1):
        ans += cmb(n,p,M) * cmb(n-1, p, M)
        ans %= M
else:
    ans = cmb(2*n-1,n,M)
print(ans)

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


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


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

def com(n, r, mod):
    r = min(r, n - r)
    if r == 0:
        return 1
    res = ilist[n] * iinvlist[n-r] * iinvlist[r] % mod
    return res


mod = 10**9+7

ilist = [0]
iinvlist = [1]
tmp = 1
for i in range(1, n+1):
    tmp *= i
    tmp %= mod
    ilist.append(tmp)
    iinvlist.append(modinv(tmp, mod))

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


print(ans)

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

mod = 10**9 + 7
l = 10**7
fac = [1]*l
facr = [1]*l

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

def combi(N,K):
    return fac[N]*facr[N-K]%mod*facr[K]%mod

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

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))



def main():
    
    def prepare(n, MOD):
        
        f = 1
        factorials = [1]  
        for m in range(1, n + 1):
            f *= m
            f %= MOD
            factorials.append(f)
        
        inv = pow(f, MOD - 2, MOD)
        
        invs = [1] * (n + 1)
        invs[n] = inv
        for m in range(n, 1, -1):
            inv *= m
            inv %= MOD
            invs[m - 1] = inv

        return factorials, invs

    n, k = ns()
    facts, invs = prepare(n, MOD)

    ans = 0
    for ki in range(min(n, k + 1)):
        zero_comb = facts[n] * invs[ki] * invs[n - ki] % MOD
        nonzero_comb = facts[n - 1] * invs[ki] * invs[n - 1 - ki] % MOD
        ans += zero_comb * nonzero_comb % MOD
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

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

def prepare():
    fact = []
    f = 1
    for m in range(1, n):
        f *= m
        f %= mod
    fact.append(f)
    f *= n
    f %= mod
    fact.append(f)
    
    factinv = [1, 1]
    inv = [0, 1]

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

    return fact, factinv

def cmb(a, r, p):
    if (r < 0) or (n < r):
        return 0
    if a == 1:
        return f[a] * v[r] * v[n - r] % mod
    else:
        return f[a] * v[r] * v[n - r - 1] % mod

f,v = prepare()

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

print(ans)

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

import sys
sys.setrecursionlimit(2147483647)

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*n+1  
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)

ans=1

if k>n:
    ans=cmb(n+n-1,n,p)

else:

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

print(ans%p)

Solution (Python):
def main():
    N, k = map(int, input().split())

    MAX_N = 3 * 10 ** 5
    MOD = 10 ** 9 + 7
    fac = [0]*MAX_N
    inv = [0]*MAX_N
    finv = [0]*MAX_N
    fac[0] = 1; fac[1] = 1
    inv[1] = 1
    finv[0] = 1; finv[1] = 1

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

    def com(n, k):
        if n < 0:return 0
        elif k > n: return 0
        
        return (fac[n]*finv[n-k]%MOD)*finv[k]%MOD
    
    k = min(k, N-1)
    ans = 1
    com_init()
    for i in range(1, k+1):
        ans += com(N, i)*com(N-1, N-i-1)
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()

mod = 10**9 + 7


class Mod:
    """
    comb = Mod(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 comb(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

    def factorial(self, n):
        return self.fac[n]

    def factorial_inv(self, n):
        return self.facinv[n]

    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


def solve():

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

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

    print(ans)


if __name__ == '__main__':
    solve()

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

mod = 10**9+7
def cmb(n,r,mod):
    r = min(r, n-r)
    return (fact[n] * factinv[r] * factinv[n-r]) % mod
def h(n,r,mod):
    return cmb(n+r-1,r,mod)
def makefact(n,mod):
    fact = [1,1]
    factinv = [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)
        factinv.append((factinv[-1]*inv[-1])%mod)
    return fact,factinv
fact,factinv = makefact(n,mod)


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

Solution (Python):
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

MOD = 10 ** 9 + 7




class Combination:
    def __init__(self, mod=10**9+7, n=202020):
        self.f = [0] * n
        self.rf = [0] * n
        self.inv = [0] * n
        self.f[0], self.f[1] = 1, 1
        self.rf[0], self.rf[1] = 1, 1
        self.inv[1] = 1
        self.MOD = mod
        for i in range(2, n):
            self.f[i] = (self.f[i - 1] * i) % self.MOD
            self.inv[i] = (-self.inv[self.MOD % i] * (self.MOD // i)) % self.MOD
            self.rf[i] = (self.rf[i - 1] * self.inv[i]) % self.MOD

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


C = Combination()
n, k = map(int, input().split())
ans = 1
for i in range(1, min(k, n-1)+1):
    tmp = (C(n, i) * C(n-1, i)) % MOD
    ans = (ans + tmp) % MOD

print(ans)

Solution (Python):
n,k = map(int,input().split())
p = pow(10,9)+7
li = [1]*(n+2)

counter = 0
k = min(k,n-1)

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

def comb(a,b):
    if b<1:
        return 1
    return li[a]*pow(li[b],p-2,p)*pow(li[a-b],p-2,p)


for i in range(k+1):
    counter += comb(n,i)*comb(n-1,i)%p
    


    

print(counter%p)

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

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

ans = 0


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

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

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

ans = 0


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

Solution (Python):
N,K=map(int, input().split())
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  
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)



zeros=min(K, N-1)
ans=1
for i in range(1,zeros+1):
    ans+=(cmb(N,i,p)*cmb(i+N-i-1, i, p))%p
    
    ans%=p

print(ans)

Solution (Python):
"""
https://www.planeta.tokyo/entry/5195/
"""
def cmb(n, r, p=10**9+7):
    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+1  
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)


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



ans = 0
mod = 10**9 + 7
for i in range(1,min(N,k)+1):
    ans += cmb(N,i)*cmb(N-1,i)

print(ans%mod+1)

Solution (Python):
n,k=map(int,input().split())
factorial=[1]
for i in range(1,2*n):
  factorial.append((factorial[i-1]*(i+1))%(10**9+7))
inv=[]
for i in range(n):
  inv.append(pow(factorial[i],10**9+5,10**9+7))
if k>=n-1:
  print((factorial[2*n-2]*inv[n-1]*inv[n-2])%(10**9+7))
else:
  ans=1
  for i in range (k):
    ans=(ans+factorial[n-1]*inv[i]*inv[n-i-2]*factorial[n-2]*inv[i]*inv[n-i-3])%(10**9+7)
  if k==1:
    ans-=1
  print(ans)

Solution (Python):
n,k=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*n):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
ans=comb(2*n-1,n-1)
for i in range(n-1,k,-1):ans=(ans-comb(n,n-i)*comb(n-1,i))%mod
print(ans)

Solution (Python):
mod = 10 ** 9 + 7
n, k = map(int, input().split())
binomial = [1]
cum = 1
for i in range(1, n + 2):
    cum *= i
    cum = cum % mod
    binomial.append(cum)
inv = []
tmp = pow(cum, mod - 2, mod)
inv.append(tmp)
for j in range(n + 1, 0, -1):
    tmp = j * tmp % mod
    inv.append(tmp)
inv.reverse()

def comb(n, k):
    return binomial[n] * inv[n - k] % mod * inv[k] % mod if n >= k else 0
k = min(k, n - 1)
ans = 0
for m in range(k + 1):
        tmp = comb(n, m) * binomial[n - 1] * inv[n - 1 - m] * inv[m]
        ans += tmp % mod
ans %= mod
print(ans)

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

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0


N, K = map(int, input().split())

K = min(K, N - 1)

F = Factorial(N + 1, MOD)

ans = 0
for k in range(K + 1):
    tmp = F.comb(N, k) * F.factorial(N - 1) * F.ifactorial(N - 1 - k) * F.ifactorial(k)
    ans += (tmp % MOD)
    ans %= MOD

print (ans)

Solution (Python):
N, K = map(int, input().split())

MOD = 10 ** 9 + 7
MAX = 4 * 10 ** 5 + 10
modinv = lambda a, mod=MOD: pow(a, mod - 2, mod)
fac, inv = [1] * MAX, [1] * MAX
for i in range(1, MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = modinv(fac[i])
comb = lambda n, k: fac[n] * inv[k] * inv[n - k] % MOD

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

Solution (Python):
def memfact(a,m):
    temp = 1
    yield temp
    for i in range(1,a+1):
        temp = temp * i % m
        yield temp
def comb(n,r,m):
    if r == 0: return 1
    return memf[n]*pow(memf[r],m-2,m)*pow(memf[n-r],m-2,m)

n,k = map(int, open(0).read().split())
dp = [0] * n
dp[0] = 1
m = 1000000007
dp[1] = (n * (n-1)) % m
memf = []
mfappend = memf.append
for x in memfact(n,m):
    mfappend(x)
for i in range(2,min(k+1,n)):
    dp[i] = (dp[i-1]+comb(n,i,m)*comb(n-1,i,m)) % m
print((dp[min(n-1,k)]+1)%m)

Solution (Python):
class Cmb:
    def __init__(self, N, mod=10**9+7):
        self.fact = [1,1]
        self.fact_inv = [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.fact_inv.append((self.fact_inv[-1]*self.inv[i])%mod)
    
    """ 関数として使えるように、callで定義 """
    def __call__(self, n, r, mod=10**9+7):
        if (r<0) or (n<r):
            return 0
        r = min(r, n-r)
        return self.fact[n] * self.fact_inv[r] * self.fact_inv[n-r] % mod

n,k = map(int,input().split())
mod = 10**9+7
c = Cmb(N=n)
ans = 0
for l in range(min(k+1, n)):
    tmp = c(n,l)*c(n-1, n-l-1)
    ans += tmp%mod
print(ans%mod)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
input=sys.stdin.readline
mod = 10 ** 9 + 7

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

fac = [1]*(n+1)
inv = [1]*(n+1)
for i in range(1,n+1):
  fac[i] = (fac[i-1]*i) % mod  
inv[n] = pow(fac[n], mod-2, mod)
for i in range(n, 0, -1):
  inv[i-1] = (inv[i]*i) % mod
    
def cmb(n, r):
  if r < 0 or r > n: return 0
  return (((fac[n] * inv[r])%mod) * inv[n-r]) % mod
 


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

print(ans%mod)

Solution (Python):
class Combination:
    def __init__(self, mod, max_num):
        self.mod = mod
        self.fac = [0] * max_num
        self.finv = [0] * max_num
        self.inv = [0] * max_num

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

        for i in range(2, max_num):
            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 calc(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return self.fac[n] * (
            self.finv[k] * self.finv[n - k] % self.mod) % self.mod


n, k = map(int, input().split())
com = Combination(1000000007, 500000)

ret = 1

min_val = min(n, k)

for i in range(1, min_val+1):
    if i != n:
        ret += com.calc(n, i) * com.calc(n-1, i)
        ret %= 10 ** 9 + 7
    else:
        ret += 0

print(ret)