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):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
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()))

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

co = Combination(200006)
n,m = inpl()
if m >= n:
    m = n-1
res = 1
if m == 1:
    print(co(n-1,n-2) * n)
    quit()
else:
    for i in range(m):
        tmp = i+1
        res += co(n-1,n-tmp-1) * co(n,tmp)
        res %= mod
        
print(res)

Solution (Python):
n,k=map(int,input().split())
mod=10**9+7
def inv(x):
    return pow(x,mod-2,mod)
N=2*10**5
Fact=[0 for i in range(N+1)]
Finv=[0 for i in range(N+1)]
Fact[0]=1
for i in range(N):
    Fact[i+1]=(Fact[i]*(i+1))%mod
Finv[N]=inv(Fact[N])
for i in range(N-1,-1,-1):
    Finv[i]=((i+1)*Finv[i+1])%mod
def C(a,b):
    return (Fact[a]*(Finv[b]*Finv[a-b])%mod)%mod
ans=0
for i in range(min(n,k+1)):
    ans+=(C(n,i)*C(n-1,i))%mod
    ans%=mod
print(ans)

Solution (Python):
MOD=10**9+7
class Fp(int):
    def __new__(self,x=0):return super().__new__(self,x%MOD)
    def inv(self):return self.__class__(super().__pow__(MOD-2,MOD))
    def __add__(self,value):return self.__class__(super().__add__(value))
    def __sub__(self,value):return self.__class__(super().__sub__(value))
    def __mul__(self,value):return self.__class__(super().__mul__(value))
    def __floordiv__(self,value):return self.__class__(self*self.__class__(value).inv())
    def __pow__(self,value):return self.__class__(super().__pow__(value%(MOD-1), MOD))
    __radd__=__add__
    __rmul__=__mul__
    def __rsub__(self,value):return self.__class__(-super().__sub__(value))
    def __rfloordiv__(self,value):return self.__class__(self.inv()*value)
    def __iadd__(self,value):self=self+value;return self
    def __isub__(self,value):self=self-value;return self
    def __imul__(self,value):self=self*value;return self
    def __ifloordiv__(self,value):self=self //value;return self
    def __ipow__(self,value):self=self**value;return self
    def __neg__(self):return self.__class__(super().__neg__())

class Combination:
    def __init__(self,max_n):
        self.max_n=0
        self.fact=[Fp(1)]
        self.ifact=[Fp(1)]
        self.make_fact_list(max_n)
    def C(self,n,k):return self.fact[n]*self.ifact[k]*self.ifact[n-k] if 0<=k<=n else 0
    def H(self,n,k):return self.C(n+k-1,k) if n or k else 1
    def P(self,n,k):return self.fact[n]*self.ifact[n-k] if 0<=k<=n else 0
    def make_fact_list(self,max_n):
        if max_n<=self.max_n: return
        self.fact+=[Fp(0)]*(max_n-self.max_n)
        self.ifact+=[Fp(0)]*(max_n-self.max_n)
        for i in range(self.max_n+1,max_n+1):
            self.fact[i]=self.fact[i-1]*i
            self.ifact[i]=self.ifact[i-1]//i
        self.max_n=max_n

N,K=map(int, input().split())
K=min(N-1,K)
C=Combination(N*2)
ans=Fp(1)
for i in range(1,K+1):
    ans+=C.C(N,i)*C.H(N-i,i)
print(ans)

Solution (Python):
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


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

max_empty = min(n - 1, k)
comb = Combination(10 ** 6, MOD)
ans = 0
for i in range(0, max_empty + 1):
    box = n - i
    ball = n
    ans += comb.combination(ball - 1, box - 1) * comb.combination(n, box)
    ans %= MOD
print(ans)

Solution (Python):
P = 10**9+7
N = 700000 
inv = [0] + [1] 
finv = [1] + [1] 
fac = [1] + [1] 
for i in range(2,N+1):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b):
    if a<b: return 0 
    return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P

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

ans = 0

num = min(n-1, k) + 1
for i in range(num):
    heya = n - i
    
    ret = comb(n, i)
    person = n - heya
    ret = (ret * comb(person+heya-1, person))%P
    ans += ret
print(ans%P)

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

MOD = 10**9+7

f = [1]*(n+1)
for i in range(n):
  f[i+1] = f[i]*(i+1)%MOD
  
inv = [1]*(n+1)
inv[n] = pow(f[n], MOD-2, MOD)
for i in range(n,0,-1):
  inv[i-1] = inv[i] * i % MOD
  
def nCr(n, r):
  return f[n]*inv[n-r]*inv[r]%MOD

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def comb(n, k):
    if n < 0 or n < k or k < 0:
        return 0
    return fac[n] * ifac[k] * ifac[n - k] % mod


n, k = map(int, read().split())
mod = 10 ** 9 + 7
max_n = 2 * 10 ** 5 + 1
ans = 0
fac = [1] * max_n
inv = [1] * max_n
ifac = [1] * max_n
for i in range(2, max_n):
    fac[i] = fac[i - 1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    ifac[i] = ifac[i - 1] * inv[i] % mod

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

Solution (Python):

def prepare(n, mod):
    
    fac = [1]
    for i in range(1, n+1):
        fac.append((fac[-1] * i) % mod)

    
    rec = pow(fac[-1], mod-2, mod)

    
    den = [1 for _ in range(n+1)]
    den[n] = rec
    for i in range(n-1, 0, -1):
        rec = (rec * (i+1)) % mod
        den[i] = rec
    
    return fac, den

def comb_mod(n, r, mod, fac, den):
    return (fac[n] * den[r] * den[n - r]) % mod

n, k = map(int, input().split())
mod = 10**9 + 7
fac, den = prepare(2*n-1, mod)

if k >= n-1:
    print(comb_mod(2*n-1, n, mod, fac, den))
else:
    ans = 0
    for i in range(k+1):
        ans += comb_mod(n-1, i, mod, fac, den) * comb_mod(n, i, mod, fac, den)
        ans %= mod
    print(ans)

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

N,K=map(int,input().split())
MOD=10**9+7
com1=nCr_frL(N,N,MOD) 
com2=nCr_frL(N-1,N-1,MOD) 

if K>N-1:
    K=N-1
ans=0
for m in range(K+1):
    ans+=(com1[m]*com2[N-m-1])%MOD
print(ans%MOD)

Solution (Python):
N, K = map(int, open(0).read().split())

MAX = 5 * 10 ** 5
MOD = 10 ** 9 + 7


fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    

finv = [0] * (MAX + 1)
finv[MAX] = pow(fac[MAX], MOD - 2, MOD)
for i in reversed(range(1, MAX + 1)):
    finv[i - 1] = finv[i] * i % MOD

def comb(n, k):
    return fac[n] * finv[n - k] * finv[k]

def rep_perm(n, k):
    return comb(n + k - 1, k)

ans = 0
for k in range(0, min(N, K + 1)):
    ans += comb(N, k) * rep_perm(N - k, k)
    ans %= MOD
print(ans)

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

MOD = 10 ** 9 + 7

def main():
    N, K = (int(_) for _ in input().split())

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

    ret = 0
    for m in range(min(K, N-1) + 1):
        ret += (fact[N] * ifact[m] * ifact[N-m])%MOD * (fact[N-1] * ifact[N-m-1] * ifact[m])%MOD
        ret %= MOD
    print(ret%MOD)

    return

if __name__ == '__main__':
    main()

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

def main():
    N,K = map(int,input().split())
    MOD = 10**9+7
    
    fac = [0]*(N+1)
    invfac = [0]*(N+1)
    fac[0],fac[1] = 1,1
    invfac[0],invfac[1] = 1,1
    
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    invfac[-1] = pow(fac[-1],MOD-2,MOD)
    for i in range(N,0,-1):
        invfac[i-1] = (invfac[i]*i)%MOD
        
    def comb(x,y):
        return (fac[x]*invfac[y]*invfac[x-y])%MOD
        
    ans = 0
    for i in range(min(N,K+1)):
        a = comb(N,i)
        b = comb(N-1,N-i-1)
        ans += (a*b)%MOD
        
    print(ans%MOD)

if __name__ == "__main__":
    main()

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

def main():
    N,K = map(int,input().split())
    MOD = 10**9+7
    
    fac = [0]*(N+1)
    invfac = [0]*(N+1)
    fac[0],fac[1] = 1,1
    invfac[0],invfac[1] = 1,1
    
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    invfac[-1] = pow(fac[-1],MOD-2,MOD)
    for i in range(N,0,-1):
        invfac[i-1] = (invfac[i]*i)%MOD
        
    def comb(x,y):
        return (fac[x]*invfac[y]*invfac[x-y])%MOD
        
    ans = 0
    for i in range(min(N,K+1)):
        a = comb(N,i)
        b = comb(N-1,N-i-1)
        ans += (a*b)%MOD
        
    print(ans%MOD)

if __name__ == "__main__":
    main()

Solution (Python):



class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

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

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret
N,K = map(int,input().split())

ans=0
MOD=10**9+7

F= FactMod(N,MOD)

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

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

F = 200005
mod = 10**9+7
fact = [1]*F
inv = [1]*F
for i in range(2,F):
    fact[i]=(fact[i-1]*i)%mod
inv[F-1]=pow(fact[F-1],mod-2,mod)
for i in range(F-2,1,-1):
    inv[i] = (inv[i+1]*(i+1))%mod

ans=1
for i in range(1,min(n,k+1)):
    comb=(fact[n]*inv[i]*inv[n-i])%mod
    h=(fact[n-1]*inv[i]*inv[n-1-i])%mod
    ans=(ans+comb*h)%mod
print(ans)

Solution (Python):
n, k = map(int, input().split())
if n - 1 < k:
    k = n-1
mod = 10**9+7
cmb1 = [1]*(n+1)
cmb2 = [1]*n
x = [0]*(n+1)
def Pow(a, n):
    if n == 0: return 1
    if n%2 == 0:
        return (Pow(a, n//2))**2%mod
    else:
        return Pow(a, n-1)*a%mod
for i in range(1,n+1):
    x[i] = Pow(i, mod-2)
for i in range(1,n+1):
    cmb1[i] = cmb1[i-1]*(n+1-i)%mod*x[i]%mod
for i in range(1,n):
    cmb2[i] = cmb2[i-1]*(n-i)%mod*x[i]%mod
ans = 0    
for i in range(k+1):
    ans = ((cmb1[i]*cmb2[i])%mod + ans)%mod
print(ans)

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

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)

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

res = []
for i in range(n):
    res.append((cmb(n, i, p) * cmb(n - 1, i, p)) % p)

if n > k:
    print(sum(res[:k + 1]) % p)
else:
    print(sum(res) % p)

Solution (Python):

def prepare(n, mod):
    
    fac = [1]
    for i in range(1, n+1):
        fac.append((fac[-1] * i) % mod)

    
    rec = pow(fac[-1], mod-2, mod)

    
    den = [1 for _ in range(n+1)]
    den[n] = rec
    for i in range(n-1, 0, -1):
        rec = (rec * (i+1)) % mod
        den[i] = rec
    
    return fac, den

def comb_mod(n, r, mod, fac, den):
    return (fac[n] * den[r] * den[n - r]) % mod

n, k = map(int, input().split())
mod = 10**9 + 7
fac, den = prepare(2*n-1, mod)

if k >= n-1:
    print(comb_mod(2*n-1, n, mod, fac, den))
else:
    ans = 0
    for i in range(k+1):
        ans += comb_mod(n-1, i, mod, fac, den) * comb_mod(n, i, mod, fac, den)
        ans %= mod
    print(ans)

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

    fact = [0 for i in range(NMAX+5)]
    fact[0] = 1
    invfact = [0 for i in range(NMAX+5)]
    invfact[0] = 1

    for i in range(NMAX):
        fact[i+1] = (fact[i]*(i+1))%(MOD)

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

    ans = 0
    if k >= n:
        k = n-1
    for i in range(k+1):
        z = fact[n]*invfact[i]%MOD
        z = z*invfact[n-i]%MOD
        h = fact[n-1]*invfact[i]%MOD
        h = h*invfact[n-i-1]%MOD
        ans += z*h%MOD

    print(ans%MOD)

main()

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict

con = 10 ** 9 + 7

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

class Combination(object):
	def __init__(self, N, con):
		self.fac = [0] * (N + 1)
		self.inv = [0] * (N + 1)
		self.finv = [0] * (N + 1)
		self.fac[0], self.fac[1] = 1, 1
		self.inv[1] = 1
		self.finv[0], self.finv[1] = 1, 1

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

	def com(self, N, k):
		return (self.fac[N] * self.finv[k] * self.finv[N - k]) % con


def main():
	N, K = getlist()
	if K >= N:
		Com = Combination(2 * N - 1, con)
		ans = Com.com(2 * N - 1, N)
		print(ans)

	else:
		Com1 = Combination(N, con)
		Com2 = Combination(N - 1, con)
		ans = 0
		for i in range(1, K + 1):
			ans += Com1.com(N, i) * Com2.com(N - 1, i)
			ans %= con
		ans = (ans + 1) % con
		print(ans)
	
if __name__ == '__main__':
	main()

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


def modInv(x,m=10**9+7):
    return pow(x,m-2,m)

class combMod:
    def __init__(self,maxN,mod=10**9+7):
        self.maxN=maxN
        self.mod=mod
        self.fac=[None]*(maxN+1) 
        self.ifac=[None]*(maxN+1)
        
        
    def calc_fact(self): 
        self.fac[0]=1
        for i in range(1,self.maxN+1):
            self.fac[i] = self.fac[i-1]*i % self.mod
        self.ifac[-1] = modInv(self.fac[-1])
        for i in range(self.maxN,0,-1):
            self.ifac[i-1] = self.ifac[i]*i % self.mod
    def modnCr(self,n, r,mod=None):
        if mod is None:
            mod=self.mod
        denom = self.fac[n]
        numer = self.ifac[r] * self.ifac[n-r] % mod
        return  denom * numer % mod

combMod=combMod(2*n+1)
combMod.calc_fact()
ans=0
for ki in range(k+1):
    ans += combMod.modnCr(n, ki)*combMod.modnCr(n-ki-1+ki, ki)%MOD
print(ans%MOD)

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

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

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

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

if k >= n:
	k = n-1

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

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

print(ans)

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

FAC = [1]
INV = [1]
for i in range(1,2*n+1):
  FAC.append((FAC[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))

def nCr(n,r):
  return FAC[n]*INV[n-r]*INV[r]

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

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

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    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

comb=Combination(10**6)

if n-1<=k:
    print(comb(2*n-1,n)%mod)

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

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

mod = 10 ** 9 + 7 
MAX = 2 * (10 ** 5) + 1 

def com_init(MAX, mod):
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    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
    return fac, finv

fac, finv = com_init(MAX, mod)

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

def nHk(n, k):
    '''
    Duplicated Combination
    '''
    return nCr(n - 1 + k, n - 1)

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

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    comb1 = [0] * (n + 1)
    comb2 = [0] * (n + 1)

    comb1[0] = 1
    comb2[0] = 1

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

    r = min(k, n - 1)
    ans = 0
    for i in range(r + 1):
        ans += comb1[n - i] * comb2[n - 1 - i]
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def make_array_for_comb(N, mod=10**9+7):
    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[i]) % mod)
    return fact, fact_inv

def comb(n, r, mod=10**9+7):
  if (r < 0) or (n < r):
      return 0
  r = min(r, n - r)
  return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

n,k = [int(i) for i in input().split()]
mod = 10**9+7
fact, fact_inv = make_array_for_comb(n,mod)
ans = 0

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

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

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

mod = 10 ** 9 + 7 
MAX = 2 * 10 ** 5 + 1 

def com_init(MAX, mod):
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    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
    return fac, finv

fac, finv = com_init(MAX, mod)

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

def nHk(n, k):
    '''
    Duplicated Combination
    '''
    return nCr(n - 1 + k, n - 1)

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

Solution (Python):
class FastModComb:

    def __init__(self, n, mod=10 ** 9 + 7):
        f, self.mod = [1], mod
        for i in range(1, n + 1):
            f.append(f[-1] * i % mod)
        rf = [self.modpow(f[-1], mod - 2)]
        for i in range(1, n + 1):
            rf.append(rf[-1] * (n - i + 1) % mod)
        self.f, self.rf = f, list(reversed(rf))

    def modpow(self, a, b):
        ret = 1
        while b > 0:
            if b % 2 == 1:
                ret = ret * a % self.mod
            a = a * a % self.mod
            b //= 2
        return ret

    def modcomb(self, n, c):
        return self.f[n] * self.rf[c] * self.rf[n - c] % self.mod


n, k = map(int, input().split())
mod, mc = 10 ** 9 + 7, FastModComb(n)
print(sum([mc.modcomb(n, m) * mc.modcomb(n - 1, n - m - 1) % mod
           for m in range(min(n - 1, k) + 1)]) % mod)

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



M = 10**9+7


if k >= n-1:
    fac = [1]+[0]*(2*n-1)
    for i in range(1,2*n): fac[i] = fac[i-1]*i %M
    comb = lambda p,q:(fac[p]*pow(fac[q],M-2,M)*pow(fac[p-q],M-2,M))%M
    y = comb(2*n-1,n-1)
    
else:
    y = 1
    c1,c2=1,1
    for i in range(1,k+1):
        p = pow(i,M-2,M)
        c1 = c1*(n+1-i)*p%M
        c2 = c2*(n-i)*p%M
        y += c1*c2%M
        
print(y%M)

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

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

print(ans%mod)

Solution (Python):
mod=10**9+7
comb1=1
comb2=1
N,K=map(int,input().split())
k=min(K,N-1)
x=0
for i in range(k):
 comb1=(comb1*(N-i)*pow(i+1,mod-2,mod))%(mod)
 comb2=(comb2*(N-1-i)*pow(i+1,mod-2,mod))%(mod)
 x+=(comb1*comb2)%(mod)
print((x+1)%(mod))

Solution (Python):
class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    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):
        if n < r:
            return 0
        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

def main():
    n, k = map(int,input().split())
    MOD = 10 ** 9 + 7
    comb = Combination(10 ** 6)
    ans = 0
    if n - 1 <= k:
        ans = comb(n + n - 1, n)
    else:
        ans = 1
        for i in range(1,k+1):
            ans += comb(n,i) * comb(n - 1, i)
            ans %= MOD
    
    print(ans)


    




if __name__ == "__main__":
    main()

Solution (Python):

import sys

MOD = 1000000007  

class Factorial:
    def __init__(self,MOD):
        self.MOD = MOD
        self.factorials = [1,1] 
        self.invModulos = [0,1] 
        self.invFactorial_ = [1,1] 

    def calc(self,n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0]*(n+1-len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI,n+1):
            prev = nextArr[i-initialI] = prev * i%m
        self.factorials += nextArr
        return self.factorials[n]
    
    def inv(self,n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit() 
        p = self.MOD
        pi = n%p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0]*(n+1-len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI,min(p,n+1)):
            next = -self.invModulos[p%i]*(p//i)%p
            self.invModulos.append(next)
        return self.invModulos[pi]
    
    def invFactorial(self,n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit() 
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n) 
        nextArr = [0]*(n+1-len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI,n+1):
            prev = nextArr[i-initialI] = (prev * self.invModulos[i%p])%p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]


class Combination:
    def __init__(self,MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)
    
    def choose_k_from_n(self,n,k):
        if k < 0 or n < k:
            return 0
        k = min(k,n-k)
        f = self.factorial
        return f.calc(n)*f.invFactorial(max(n-k,k))*f.invFactorial(min(k,n-k))%self.MOD


def solve(n: int, k: int):
    c = Combination(MOD)
    sum = 0
    for i in range(min(n,k+1)-1,-1,-1):
        c1 = c.choose_k_from_n(n,i)
        c2 = c.choose_k_from_n(n-1,i)
        sum = (sum + c1*c2)%MOD
    print(sum)
    return



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))  
    solve(n, k)

if __name__ == '__main__':
    main()

Solution (Python):
def inv(a,m=10**9+7):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

mod=10**9+7
n,k=map(int,input().split())
k=min(k,n-1)
frac=[1]
for i in range(1,n+1):
    frac.append(frac[-1]*i%mod)

ans=0
for i in range(k+1):
    tmp=inv(frac[i]**2%mod*frac[n-i]*frac[n-1-i]%mod)
    ans+=tmp
    ans%=mod
ans=ans*frac[n]*frac[n-1]%mod
print(ans)

Solution (Python):
n, k = map(int, input().split())
mod = 10**9+7
g1 = [1, 1]
g2 = [1, 1]
inv = [0, 1]
for i in range(2, n+1):
    g1.append((g1[-1] * i) % mod)
    inv.append((-inv[mod%i] * (mod//i)) % mod)
    g2.append((g2[-1] * inv[-1]) % mod)

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

li = []
for i in range(min(k, n-1)+1):
    li.append(comb(n-1, i))
ans = 0
pre = 0
for cur in li:
    ans += (pre+cur)*cur
    pre = cur
print(ans%mod)

Solution (Python):
n, k = map(int, input().split())
mod = 10 ** 9 + 7
ans = 0
coma = 1
comb = 1
for i in range(min(k+1, n)):
    ans += coma * comb
    ans %= mod
    coma *= (n-i) * pow(i+1, mod-2, mod)
    coma %= mod
    comb *= (n-i-1) * pow(i+1, mod-2, mod)
    comb %= mod

print(ans)

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

mod = 10**9+7
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 c(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD


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

if k == 1:
    print(ans % mod)

else:
    print((ans+1) % mod)

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

    def pre(n,MOD):
        a=1
        for i in range(1,n+1):
            a=(a*i)%MOD
        an=a
        b=pow(a,MOD-2,MOD)
        bs=[1]*(n+1)
        bs[n]=b
        for i in range(n,1,-1):
            b=b*i%MOD
            bs[i-1]=b
        return an,bs

    a,b=pre(n-1,MOD)
    ans=1
    for i in range(1,min(n-1,k)+1):
        s=(a*n*b[i])%MOD
        s=(s*b[n-i])%MOD
        s=(s*a*b[n-i-1])%MOD
        s=(s*b[i])%MOD
        ans+=s
        ans%=MOD
    print(ans)
    
if __name__ == '__main__':
    main()