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):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush


from functools import lru_cache


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 10**9+7
    

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

    

    fac1=1
    fac2=1
    facs=[1,1]
    for i in range(2,2*N):
        facs.append(facs[-1]*i%mod)

    
    
    
    
    
    def comb(N,r):
        fac1=pow(facs[r],mod-2,mod)
        fac2=pow(facs[N-r],mod-2,mod)
        tot=(facs[N]*fac1%mod)*fac2%mod
        return tot
    tot=comb(2*N-1,N)
    if N-1<=K:
        print(tot)
    
    
    else:
        r=0
        for i in range(1,N-(K+1)+1):
            n=N-i
            r+=comb(N,i)*comb(n+i-1,i-1)%mod
            r%=mod
        print((tot-r)%mod)





if __name__ == "__main__":
    main()

Solution (Python):

def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

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

    mod = 1000000007
    def make_fact(n):
        fact = [1]*(n+1)
        ifact = [1]*(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
        return fact, ifact
    fact, ifact = make_fact(n)

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

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

    print(ans)

main()

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 < 1:
        return 1
  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):
n,k=map(int,input().split())
mod=10**9+7
lim=n
fcl=[1]*(lim+1)
for i in range(1,lim+1):
  fcl[i]=(fcl[i-1]*i)%mod
def comb(x,y,p):
  return ((fcl[x]*pow(fcl[y],p-2,p))%p*pow(fcl[x-y],p-2,p))%p
ans=0
for i in range(min(n,k+1)):
  ans+=comb(n-1,n-i-1,mod)*comb(n,i,mod)
  ans%=mod
print(ans)

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

f = [ 1 ] * ( n + 1 ) 
inv = [ 1 ] * ( n + 1 )

for i in range( 1, n + 1 ):
  f[ i ] = ( f[ i - 1 ] * i ) % mod
  
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 ):
  if r < 1:
    return 1
  return ( f[ n ] * inv[ r ] % mod ) * inv[ n - r ] % mod

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

Solution (Python):
n, k = map( int, input().split() )
mod = 10 ** 9 + 7
 
numer = [ 1 ] * ( n + 1 )
demon = [ 1 ] * ( n + 1 )
 
for i in range( 1, n + 1 ):
  numer[ i ] = numer[ i - 1 ] * i % mod

demon[ n ] = pow( numer[ n ], mod - 2, mod )
for i in range( n, 0, -1 ):
  demon[ i - 1 ] = ( demon[ i ] * i ) % mod

def nCr( n, r ):
  if r < 1:
    return 1
  return ( numer[ n ] * demon[ r ] % mod ) * demon[ n - r ] % mod
 
ans = 0
for i in range( min( k, n - 1) + 1 ):
  ans = ( ans + nCr( n, i ) * nCr( n - 1, i )) % mod
print( ans )

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

mod = 10 ** 9 + 7
N = n + 1

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y // 2) ** 2 % mod
    else            : return power(x, y // 2) ** 2 * x % mod

factorial = [1]
for i in range(1, N):
    factorial.append(factorial[i - 1] * i % mod)

inverseFactorial = [0] * N
inverseFactorial[N - 1] = power(factorial[N - 1], mod - 2)
for i in range(N - 2, -1, -1):
    inverseFactorial[i] = inverseFactorial[i + 1] * (i + 1) % mod

def comb(x, y):
    return factorial[x] * inverseFactorial[y] * inverseFactorial[x - y] % mod

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

Solution (Python):
n,k = map(int,input().split())
mod = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

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

def combi(n,r,mod=10**9+7):
    return( ( fac[n] * modinv(fac[r]) )%mod * modinv(fac[n-r]) % mod)

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

Solution (Python):
def power(a,n):
    x=1
    L=list(format(n,'b'))
    l=len(L)
    for i in range(l):
        if int(L[l-i-1])==1:        
            x=(x*a)%(10**9+7)
        a=(a*a)%(10**9+7)
    return x
n,k=map(int,input().split())
a=1
b=1
y=0
for i in range(n):
    a=(a*(i+1))%(10**9+7)
    b=(b*(2*n-i-1))%(10**9+7)
aa=power(a,10**9+5)
x=(b*aa)%(10**9+7)
if k<n-1:
    c=1
    d=1
    e=1
    f=1
    for i in range(k+1):
        c=(c*(n-i))%(10**9+7)
        d=(d*(i+1))%(10**9+7)
    d=power(d,10**9+5)
    c=(c*d)%(10**9+7)
    for i in range(n-k-2):
        e=(e*(n-1-i))%(10**9+7)
        f=(f*(i+1))%(10**9+7)
    f=power(f,10**9+5)
    e=(e*f)%(10**9+7)
    y=(c*e)%(10**9+7)
    if k+2<=n-1:
        for i in range(k+2,n):
            c=(c*(n-i+1))%(10**9+7)
            d=power(i,10**9+5)
            c=(c*d)%(10**9+7)
            e=(e*(n-i))%(10**9+7)
            f=power(i,10**9+5)
            e=(e*f)%(10**9+7)
            y+=(c*e)%(10**9+7)
            y=y%(10**9+7)
x=x-y
if x<0:
    x=10**9+7+x
print(x)

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

def createFacArr(n, mod):
    '''
    二項係数計算用の配列の作成

    Parameters
    n : int
        配列のサイズ
    mod : int
        あまり

    Returns
    fac : list
        階乗のリスト
    finv : list
        modの逆元のリスト
    ivn : list
    '''
    fac = [0] * n
    finv = [0] * n
    inv = [0] * n
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, n):
        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

def comb(n ,k, mod, fac, finv):
    '''
    二項係数の計算

    Parameters
    n : int
        元集合
    k : int
        元集合から選択する数
    mod : int
        あまり
    fac : list
        階乗のリスト
    finv : list
        逆元のリスト
    
    Returns
    c : int
        nCkの組み合わせの数
    '''
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

K = min(N-1, K)
ans = 0
MOD = 10 ** 9 + 7
fac, finv = createFacArr(N+100, MOD)

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

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

    
    
    
    
    
    
    ans = 0
    k1 = 1
    k2 = 1
    for i in range(min(k+1,n)):
        ans += k1*k2
        ans %= MOD
        k1 *= (n-i)*pow(i+1,MOD-2,MOD)
        k1 %= MOD
        k2 *= (n-1-i)*pow(i+1,MOD-2,MOD)
        k2 %= MOD
    print(int(ans))

main()

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

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(5*10**5)

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

print(ans)

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]

def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]

def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

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 = MOD 
N = 5*10**5
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 = MI()
ans = cmb(2*N-1,N-1,MOD)
if K<N-1:
    for i in range(K+1,N):
        ans -= cmb(N,i,MOD)*cmb(N-1,i,MOD)
print(ans%MOD)

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]

def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]

def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

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 = MOD 
N = 5*10**5
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 = MI()
ans = cmb(2*N-1,N-1,MOD)
if K<N-1:
    for i in range(K+1,N):
        ans -= cmb(N,i,MOD)*cmb(N-1,i,MOD)
print(ans%MOD)

Solution (Python):
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 nCr(n,r):  
  if r < 1:
    return 1
  return (((fac[n] * inv[r])%mod) * inv[n-r]) % mod

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

print(ans)

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


N = n
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 
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
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(n-1,k)+1):
    di = cmb(n,i,mod)*cmb(n-1,i,mod)%mod
    ans = (ans+di)%mod

print(ans)

Solution (Python):
n,k=map(int,input().split())
mi = min(n-1,k)
di = 10**9+7
def pow_k(x,i):
    if i==0:
        return 0
    K=1
    while i>1:
        if i % 2 != 0:
            K = (K*x)%di
        x = (x*x)%di
        i //= 2

    return (K * x)%di

lis = [i for i in range(n+1)]
lisr = [i for i in range(n+1)]
lis[0]=1
for i in range(1,n+1):
    lis[i]=(lis[i-1]*lis[i])%di
    lisr[i] = pow_k(lisr[i],di-2)

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



su = 1
for i in range(1,mi+1):
    pl = ((((lis[n-1]*lisr[i])%di)*lisr[n-1-i])%di)
    plu = (pl*((((lis[n]*lisr[i])%di)*lisr[n-i])%di))%di
    su+=plu
    su%=di
print(su)

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

mod = 10 ** 9 + 7

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

ans = 0
for i in range(min(n-1, k) + 1):
    com1 = fact[n] * fact_inv[i] * fact_inv[n-i] % mod
    com2 = fact[n-1] * fact_inv[i] * fact_inv[n-i-1] % mod
    mul = com1 * com2 % mod
    ans = (ans + mul) % mod

print(ans)

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

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

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

ans = 0
for i in range(min(n-1, k) + 1):
    com1 = fac[n] * finv[i] * finv[n-i] % mod
    com2 = fac[n-1] * finv[i] * finv[n-i-1] % mod
    mul = com1 * com2 % mod
    ans = (ans + mul) % mod

print(ans)

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

mod = 10 ** 9 + 7

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

ans = 0
for i in range(min(n-1, k) + 1):
    com1 = fac[n] * finv[i] * finv[n-i] % mod
    com2 = fac[n-1] * finv[i] * finv[n-i-1] % mod
    mul = com1 * com2 % mod
    ans = (ans + mul) % mod

print(ans)

Solution (Python):
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)



N,K=map(int,input().split())
ans=0
for i in range(min(N,K+1)):
    ans+=choose(N,i)*chofuku(N-i,i)%MOD

print(ans%MOD)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,K = LI()
    f = [1]
    r = [1]

    s = 1
    for i in range(1,N+2):
        s = (s * i) % MOD
        f.append(s)
        r.append(pow(s,MOD-2,MOD))


    def comb(a,b):
        return f[a] * r[b] * r[a-b]

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

if __name__ == '__main__':
    main()

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


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
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1]
for i in range( 2, 2*n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

Solution (Python):
n, k = map(int, input().split())
mod = 10**9 + 7
def setFact(n, mod):
    global fact
    fact = [1]
    global ifact
    ifact = [1] * (n+1)
    for i in range(1, n+1):
        fact.append(fact[i-1]*i%mod)
    ifact[-1] = pow(fact[-1], mod-2, mod)
    for i in range(2, n+2):
        ifact[-i] = ifact[-i+1]*(n-i+2) %mod
def combination(n, k , mod):
    global fact
    global ifact
    if k < 0 or k > n:
        return 0
    else:
        return fact[n] * ifact[n-k] * ifact[k] % mod
setFact(n, mod)
ans = 0
for i in range(min(n+1, k+1)):
    ans += combination(n,i,mod) *combination(n-1,i, mod) %mod
    ans %= mod
print(ans)

Solution (Python):
n, k = map(int, input().split())
mod = 10**9 + 7
def setFact(n, mod):
    global fact
    fact = [1]
    global ifact
    ifact = [1] * (n+1)
    for i in range(1, n+1):
        fact.append(fact[i-1]*i%mod)
    ifact[-1] = pow(fact[-1], mod-2, mod)
    for i in range(2, n+2):
        ifact[-i] = ifact[-i+1]*(n-i+2) %mod
def combination(n, k , mod):
    global fact
    global ifact
    if k < 0 or k > n:
        return 0
    else:
        return fact[n] * ifact[n-k] * ifact[k] % mod
setFact(n, mod)
ans = 0
for i in range(min(n+1, k+1)):
    ans += combination(n,i,mod) *combination(n-1,i, mod) %mod
    ans %= mod
print(ans)

Solution (Python):
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7

@lru_cache(None)
def combination(n, k):
    if k == 0:
        return 1
    else:
        return ((combination(n, k-1) * (n-k+1) % MOD) * pow(k, MOD-2, MOD)) % MOD

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

s = 0
for m in range(0, min(k+1, n)):
    s += combination(n, min(m, n - m)) * combination(n - 1, min(m, n - m - 1))
    s %= MOD

print(s)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")











n,k = map(int,input().split())
MOD = 10**9 + 7
def comb(n, k, mod):
    if n<0 or k<0 or n<k:
        return 0
    if n==0 or k==0:
        return 1
    k=k if k<=n-k else n-k
    x = 1
    y = 1
    for i in range(k):
        x=x*(n-i)%mod
        y=y*(i+1)%mod
    return (x*pow(y,mod-2,mod))%mod

fac = [1, 1]
inv = [0, 1]
finv = [1, 1]
for i in range(2, 2*n+1):
    fac.append(fac[-1] * i % MOD)
    inv.append(MOD - inv[MOD%i] * (MOD//i) % MOD)
    finv.append(finv[-1] * inv[-1] % MOD) 
def comb_mod(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m
if k >= n-1:
    ans = comb_mod(2*n-1,n,MOD)
    print(ans%MOD)
elif k == 1:
    print(n*(n-1)%MOD)
else:
    ans = 0
    for i in range(k+1):
        ans += comb_mod(n-1,i,MOD)*comb_mod(n,i,MOD)
    print(ans%MOD)

Solution (Python):
n,k=map(int,input().split())
P=10**9+7
class FactInv:
    def __init__(self,N,P):
        fact=[];ifact=[];fact=[1]*(N+1);ifact=[0]*(N+1)
        for i in range(1,N):
            fact[i+1]=(fact[i]*(i+1))%P
        ifact[-1]=pow(fact[-1],P-2,P)
        for i in range(N,0,-1):
            ifact[i-1]=(ifact[i]*i)%P
        self.fact=fact;self.ifact=ifact;self.P=P
    def comb(self,n,k):
        return (self.fact[n]*self.ifact[k]*self.ifact[n-k])%self.P
C=FactInv(2*n+10,P)
ans=0
for i in range(0,min(k+1,n)):
    ans+=(C.comb(n,i)*C.comb(n-1,n-i-1))%P
    ans%=P
print(ans)

Solution (Python):
MOD=10**9+7
def facinv(N):
    fac,finv,inv=[0]*(N+1),[0]*(N+1),[0]*(N+1)
    fac[0]=1;fac[1]=1;finv[0]=1;finv[1]=1;inv[1]=1
    for i in range(2,N+1):
        fac[i]=fac[i-1]*i%MOD
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        finv[i]=finv[i-1]*inv[i]%MOD
    return fac,finv,inv


def COM(n,r):
    if n<r or r<0:
        return 0
    else:
        return ((fac[n]*finv[r])%MOD*finv[n-r])%MOD
        
n,k=map(int,input().split())
fac,finv,inv=facinv(2*n)

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

Solution (Python):
from sys import stdin, setrecursionlimit


def initialize_cmb(m, mod=10 ** 9 + 7):
    fac = [1]
    finv = [1]
    inv = [0] * (m + 1)
    if m > 1:
        fac.append(1)
        finv.append(1)
        inv[1] = 1
        pre_fac = 1
        pre_finv = 1
        for i in range(2, m + 1):
            pre_fac = pre_fac * i % mod
            fac.append(pre_fac)
            inv[i] = mod - inv[mod % i] * (mod // i) % mod
            pre_finv = pre_finv * inv[i] % mod
            finv.append(pre_finv)
    return fac, finv


def cmb(n, k, fac, finv, mod=10 ** 9 + 7):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


def main():
    input = stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, k = map(int, input().split())

    fac, finv = initialize_cmb(n, mod)

    c_n = []
    for i in range(n + 1):
        c_n.append(cmb(n, i, fac, finv))
    c_n_1 = []
    for i in range(n):
        c_n_1.append(cmb(n - 1, i, fac, finv))

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


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

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

MOD = 10**9+7

class Comb:
    def __init__(self, N):
        self.fac = [1] * (N+1)
        for i in range(2, N+1): self.fac[i] = self.fac[i-1] * i % MOD

    def pow(self, a, b):
        res = 1
        while b:
            if b & 1: res = res * a % MOD
            a = a**2 % MOD
            b >>= 1
        return res

    def pow2(self, a, b):
        return pow(a, b, MOD)

    def comb(self, n, r):
        if r < 0 or r > n: return 0
        return (self.fac[n] * self.pow2(self.fac[r], MOD-2)) % MOD * self.pow2(self.fac[n-r], MOD-2) % MOD

    def permutation(self, n, r):
        if r == 0: return 1
        return self.fac[n] * self.pow2(self.fac[n-r], MOD-2) % MOD

def main():
  N, K = list(map(int, input().split()))

  comb = Comb(N)
  ans = 0

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

  print(ans) 

if __name__ == '__main__':
  main()

Solution (Python):
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter

from functools import lru_cache

sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


class combination():
    def __init__(self, mod):
        '''
        modを指定して初期化
        '''
        self.mod = mod
        self.fac = [1, 1]  
        self.ifac = [1, 1]  
        self.inv = [0, 1]  

    def calc(self, n, k):
        '''
        nCk%modを計算する
        '''
        if k < 0 or n < k:
            return 0
        self.make_tables(n)  
        k = min(k, n - k)
        return self.fac[n] * (self.ifac[k] * self.ifac[n - k] %
                              self.mod) % self.mod

    def make_tables(self, n):
        '''
        階乗テーブル・階乗の逆元テーブルを作成
        '''
        for i in range(len(self.fac), n + 1):
            self.fac.append((self.fac[-1] * i) % self.mod)
            self.inv.append(
                (-self.inv[self.mod % i] * (self.mod // i)) % self.mod)
            self.ifac.append((self.ifac[-1] * self.inv[-1]) % self.mod)


comb = combination(mod)

n, k = inpl()
ans = 0

for m in range(min(n, k + 1)):
    
    a = comb.calc(n, m) % mod
    
    b = comb.calc(n - 1, n - m - 1) % mod
    ans += a * b % mod
print(ans % mod)

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


MOD = 10 ** 9 + 7
sys.setrecursionlimit(20000000)


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())
    answer = 0
    if K >= N - 1:
        cmb = Combination(2 * N + 1)
        answer = cmb(N * 2 - 1, N - 1)

    else:
        cmb = Combination(N)
        for i in range(K + 1):
            answer += cmb(N, i) * cmb(N - 1, N - 1 - i)
    print(answer % MOD)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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())
    comb = Combination(n_max=10 ** 5 * 4 + 10)

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

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def solve():
    mod = 10**9+7
    n, k = map(int, input().split())
    m = min(n-1,k)
    ans = 1
    dp0 = [1]*(m+1)
    dp1 = [1]*(m+1)
    for i in range(1,m+1):
        dp0[i] = dp0[i-1]*(n-i+1)*pow(i,mod-2,mod)%mod
        dp1[i] = dp1[i-1]*(n-i)*pow(i,mod-2,mod)%mod
        ans += dp0[i]*dp1[i]%mod
        ans %= mod
    return ans
print(solve())

Solution (Python):
class Facts:

  def __init__(self, mod=10**9+7, n_max=1):
    self.mod     = mod
    self.n_max   = n_max
    self.fact    = [1, 1]
    self.inv     = [0, 1]
    self.factinv = [1, 1]
    if 1 < n_max:
      self.setup_table(n_max)

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

  def factorial(self, n):
    if self.n_max < n:
      self.setup_table(n)
    return self.fact[n]
    
  def hom(self, n, k):
    return self.cmb(n+k-1, k)

  def prm(self, n, k):
    if self.n_max < n:
      self.setup_table(n)
    return self.fact[n] * self.factinv[n-k] % self.mod

  def setup_table(self, t):
    for i in range(self.n_max+1,t+1):
      self.fact.append( self.fact[-1] * i % self.mod )
      self.inv.append( -self.inv[mod % i] * (self.mod // i) % self.mod )
      self.factinv.append( self.factinv[-1] * self.inv[-1] % self.mod )
    self.n_max = t


mod = 10 ** 9 + 7

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

ans = 0
f = Facts(mod)

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

print(ans)