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 math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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

def nPk(n,k):
    
    
    
    
    
    return kaijo[n] * inv(kaijo[n-k]) % MOD

def nCk(n,k):
    return nPk(n,k) * inv(kaijo[k])

MOD = 10**9+7

kaijo = [0] * 400020
kaijo[0] = 1
for i in range(1, len(kaijo)):
    kaijo[i] = kaijo[i-1] * i % MOD

n,k = get_nums_l()

if k >= n-1:
    print(nCk(n+n-1, n) % MOD)
    exit()








ans = 1
for z in range(1,k+1):
    ans += nCk(n,z) * nCk(n-1, z)

print(ans%MOD)

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

MOD = 10 ** 9 + 7
SIZE = 10 ** 6 + 1

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

def comb(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, SIZE + 1):
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD // i) ) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)

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

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

Solution (Python):

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret

def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max,mod=DIV):
    fac,finv,inv = [0]*max, [0]*max, [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
    class CONV:
        def __init__(self):
            pass
        def ncr(self,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
    return CONV()


def main():
    n,k = isRaw()
    if k >= n-1:
        return ncr(2*n-1,n-1)
    conv = CONV_TBL(n+1)
    ans = 0
    for j in range(0,k+1):
        tmp = (conv.ncr(n, j)*conv.ncr(n-1, j)+DIV) % DIV
        ans = (ans+tmp+DIV )% DIV

    return ans


if __name__ == "__main__":
    print(main())

Solution (Python):
mod = 10**9+7
rng = 400100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
n,k=map(int,input().split())
dp=[0 for i in range(n+1)]
dp[0]=1
for i in range(1,n+1):
  x=cmb(n,i)*cmb(n-1,i)%mod
  dp[i]=(dp[i-1]+x)%mod
print(dp[min(k,n-1)])

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

MOD = 1000000007

def pow_mod(x, y):
    if y == 0: return 1
    ans = 1
    while y > 1:
        if y % 2 != 0: 
            ans *= x
            ans %= MOD
        x *= x
        x %= MOD
        y //= 2
    return ans * x % MOD

mod_inv = lambda x: pow_mod(x, MOD - 2)

if k >= n-1:
  n2_1 = (n * 2 - 1) % MOD 
  nHr = {0:1}
  for i in range(1, n):
    nHr[i] = nHr[i-1] * (n2_1 - i + 1)
    nHr[i] %= MOD
    nHr[i] *= mod_inv(i)
    nHr[i] %= MOD
  print(nHr[n-1])
else:
  mod_inv_d = {i: mod_inv(i) for i in range(1, max(k+1, n-k+1))}
  nCr = {0:1}
  n_1Cr = {0:1}
  ans = nCr[0] * n_1Cr[0]
  for i in range(1, k+1):
    hoge = (n - i + 1)
    nCr[i] = nCr[i-1] * hoge
    nCr[i] %= MOD
    nCr[i] *= mod_inv_d[i]
    nCr[i] %= MOD
    n_1Cr[i] = n_1Cr[i-1] * (hoge - 1)
    n_1Cr[i] %= MOD
    n_1Cr[i] *= mod_inv_d[i]
    n_1Cr[i] %= MOD
    ans += (nCr[i] * n_1Cr[i]) % MOD
    ans %= MOD
  print(ans)

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

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

inv_mod = [pow(i,MOD-2,MOD) for i in range(zero_end)]

comb_mod1 = [1] * zero_end
comb_mod2 = [1] * zero_end
for i in range(1,zero_end):
    comb_mod1[i] = comb_mod1[i-1] * (n-i+1) * inv_mod[i] %MOD
    comb_mod2[i] = comb_mod2[i-1] * (n-i  ) * inv_mod[i] %MOD

ans = 0

for i in range(zero_end): 
    
    ans = ans + comb_mod1[i] *comb_mod2[i] %MOD
    
print(ans%MOD)

Solution (Python):
def examA():
    N, R = LI()
    ans = R+100*max(0,(10-N))
    print(ans)
    return

def examB():
    N, K = LI()
    ans = 1
    while(N>=K):
        N //=K
        ans += 1
    print(ans)
    return

def examC():
    N = I()
    X = LI()
    ans = inf
    for i in range(101):
        cur = 0
        for x in X:
            cur += (i-x)**2
        ans = min(ans,cur)
    print(ans)
    return

def examD():
    def cmb(n, r, mod):
        cur = 1
        for i in range(r):
            cur *= (n-i)
            cur %= mod
        for i in range(r):
            cur *= pow(i+1,mod-2,mod)
            cur %= mod
        return cur
    n, a, b = LI()
    ans = pow(2,n,mod) - cmb(n,a,mod) - cmb(n,b,mod) -1
    ans = (ans+mod*2)%mod
    print(ans)
    return

def examE():
    class combination():
        
        def __init__(self, n, mod):
            self.n = n
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

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

        def comb(self, n, r, mod):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % mod
    n, k = LI()
    C = combination(2*10**5+1,mod)
    if k>n:
        k = n
    ans = 0
    for i in range(k+1):
        cur = C.comb(n,i,mod) * C.comb(n-1,i,mod)
        ans += cur
        ans %= mod
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

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 = 2*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 )



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

if n <= k:
    k = n-1


while k >=0:
    if k == 0:
        ans += 1
        ans %= mod
    else:
        base = cmb(n,k,mod)
        
        base *= cmb(n-1,n-k-1,mod)
        base %= mod
        ans += base
        ans %= mod
    
    k-=1

print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n, k = LI()
    L = [[1]*n]
    ans = 1
    f = [1]
    N = 10**6
    for i in range(N):
        f.append(f[-1]*(i+1)%mod)
    inv = [None]*(N+1)
    inv[N] = pow(f[N],mod-2,mod)
    for i in range(N)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    def comb(a,b):
        return f[a]*inv[b]*inv[a-b]%mod
    ans = comb(2*n-1,n)
    if k + 1 >= n:
        print(ans)
    else:
        for t in range(k+1,n):
            ans -= comb(n,t)*comb(n-1,t)%mod
            ans %= mod
        print(ans)
    return


if __name__ == "__main__":
    solve()

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
N = 200000
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
if k >= n:
    for i in range(n):
        ans += cmb(n-1, i, mod) * cmb(n, i, mod)
        ans %= mod


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

print(ans)

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

"""
T = [0]*n
def f(a, b, c):
  if a==n-1:
    T[c+max(b-1, 0)] += 1
  else:
    for i in range(0, b+1):
      f(a+1, b-i, c+max(i-1, 0))
f(0, n, 0)
ans = sum(T[:k+1])
print ans
print T
"""

"""
[1]
[1, 2]
[1, 6, 3]
[1, 12, 18, 4]
[1, 20, 60, 40, 5]
[1, 30, 150, 200, 75, 6]
[1, 42, 315, 700, 525, 126, 7]
https://oeis.org/A132813
T(n,k) = (k+1)*binomial(n+1,k+1)*binomial(n+1,k)/(n+1), n>=k>=0.
"""

M = 10**9+7

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

def C(x, y):
  return F[x]*pow(F[y], M-2, M)*pow(F[x-y], M-2, M)%M

ans = 0
for i in range(min(k+1, n)):
  ans += (i+1)*C(n, i+1)*C(n, i)*pow(n, M-2, M)%M
print ans%M

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

mod = 10 ** 9 + 7

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

def comb(n, r) :
  if n < 1 or n < r : return 0
  return fac[n] * inv[r] * inv[n-r] % mod
  
ret = comb(n + n - 1, n)
for i in range(1, n - k) :
  ret -= comb(n - 1, k + i) * comb(n, k + i)
  ret %= mod
print(ret % mod)

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 mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

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

Solution (Python):
MOD = 10 ** 9 + 7
fac = [1] * (5 * 10 ** 5 + 1)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD


n, k = map(int, input().split())
if k >= n:
    print(fac[2 * n] * pow(2, MOD - 2, MOD) *
          pow(fac[n], MOD - 2, MOD) ** 2 % MOD)
else:
    ans = 0
    for i in range(k + 1):
        ans += fac[n - 1] * pow(fac[i], MOD - 2, MOD) * \
            pow(fac[n - i - 1], MOD - 2, MOD) * fac[n] * pow(fac[n - i],
                                                             MOD - 2, MOD) * pow(fac[i], MOD - 2, MOD) % MOD
    print(ans % MOD)

Solution (Python):
N,K=map(int,input().split())
MOD=10**9+7
max_n=2*10**5
fac=[1]*(max_n+1)
inv=[1]*(max_n+1)
ifac=[1]*(max_n+1)
for n in range(2,max_n+1):
    fac[n]=(fac[n-1]*n)%MOD
    inv[n]=MOD-inv[MOD%n]*(MOD//n)%MOD
    ifac[n]=(ifac[n-1]*inv[n])%MOD
def comb(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    return (fac[n]*ifac[k]*ifac[n-k])%MOD
print(sum([(comb(N,k)*comb(N-1,k))%MOD for k in range(min(N,K)+1)])%MOD)

Solution (Python):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
mod = 10 ** 9 + 7

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

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

'''
for N in range(n,n+1):
    for K in range(N):
        print(C(N,K)*C(N-1,K),end=" ")
    print("")
'''
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         
list_size = 1000000   

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+2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(-2, -list_size-1, -1):
	f_r_list[i] = ((f_r_list[i+1] * (list_size + 2 + i)) % MOD)

def comb(n,r):
    if n < r:
        return 0
    if n == 0 or r == 0 or n == r:
        return 1
    return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD

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

Solution (Python):
MOD = 1000000007

class Factorial():
    def __init__(self,n,mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n+1)]
        self.inv = [0 for _ in range(n+1)]
        self.factorial[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.factorial[i+1] = self.factorial[i]*(i+1)%mod
        self.inv[n] = pow(self.factorial[n],mod-2,mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i+1]*(i+1)%mod
    def fact(self,m): 
        return self.factorial[m]
    def invfact(self,m): 
        return self.inv[m]
    def perm(self,m,k): 
        if m < k: return 0
        return self.factorial[m]*self.inv[m-k]%self.mod
    def comb(self,m,k): 
        return self.factorial[m]*self.inv[k]*self.inv[m-k]%self.mod



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


F = Factorial(200010,MOD)
ans = 0

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

print(ans%MOD)

Solution (Python):
mod = 10**9+7
fact = [1]*(4*10**5+1)
for i in range(4*10**5):
    fact[i+1] = (i+1)*fact[i]%mod

factinv = [1]*(4*10**5+1)
for i in range(4*10**5+1):
    factinv[i] = pow(fact[i],mod-2,mod)

def comb(n,k):
    return fact[n]*factinv[k]*factinv[n-k]%mod
n,k = map(int,input().split())
ans = comb(2*n-1,n)
for i in range(k+1,n):
    ans -= comb(n-1,i)*comb(n,i)
    ans %= mod
print(ans)

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

def getFactorialInv(N):
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    ret = [1]*(N+1)
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
        ret[i] = ret[i-1]*inv[i] % Q
    return ret

def getFactorial(N):
    ret = [1]*(N+1)
    for i in range(2,N+1):
        ret[i] = ret[i-1]*i%Q
    return ret

def main():
    n, k = map( int, input().split())
    fact = getFactorial(n)
    invfact = getFactorialInv(n)
    if k >= n-1:
        ans = 1
        for i in range(1,n*2):
            ans *= i
            ans %= Q
        print( ans*invfact[n-1]%Q*invfact[n]%Q)
        return
    ans = 0
    for i in range(k+1):
        ans += fact[n]*invfact[i]%Q*invfact[n-i]%Q*fact[n-1]%Q*invfact[i]%Q*invfact[n-1-i]%Q
        ans %= Q
    print(ans)
if __name__ == '__main__':
    main()

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

K = min(K, N - 1)

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


def nCr(n, r):
    num = fact[n]
    div = fact[r] * fact[n - r] % mod
    return num * pow(div, mod - 2, mod) % mod


move = [0] * (N + 1)
move[0] = 1
for i in range(1, N + 1):
    x = nCr(N, i) * nCr(N - 1, N - i - 1) % mod
    move[i] = x

for i in range(1, N):
    move[i] = (move[i - 1] + move[i]) % mod

ans = move[K]
print(ans)

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


FACT=[1]
for i in range(1,5*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(5*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

ANS=0
for i in range(min(k+1,n)):
    ANS+=Combi(n-1,n-i-1)*Combi(n,i)
    

print(ANS%mod)

Solution (Python):
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD


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

com = comb(n * 2, MOD)

ans = com.com(n * 2 - 1, n)
for i in range(k + 1, n + 1):
  t = com.com(n, i) * com.com(n - 1, i) % MOD
  ans -= t
  while ans < 0:
    ans += MOD


print(ans)

Solution (Python):


import numpy as np

stdin = open(0)


N, K = map(int, stdin.read().split())


MOD = 10 ** 9 + 7




def cumprod(A, MOD=MOD):
    L = len(A); Lsq = int(L**.5 + 1)
    A = np.resize(A, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        A[:, n] *= A[:, n - 1]; A[:, n] %= MOD
    for n in range(1, Lsq):
        A[n] *= A[n - 1, -1]; A[n] %= MOD
    return A.ravel()[:L]


def make_fact(U, MOD=MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD - 2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    fact.flags.writeable = False
    fact_inv.flags.writeable = False
    return fact, fact_inv



fact, fact_inv = make_fact(N + 10)


if K >= N:
    K = N - 1
x = fact[N] * fact_inv[0:K + 1] % MOD * fact_inv[N - K:N + 1][::-1] % MOD
y = fact[N - 1] * fact_inv[0:K + 1] % MOD * fact_inv[N - K - 1:N][::-1] % MOD
answer = np.sum(x * y % MOD) % MOD


print(answer)

Solution (Python):
def main():
    mod=1000000007
    n,k=map(int,input().split())
    m=2*n
    Fact=[1] 
    for i in range(1,m+1):
        Fact.append(Fact[i-1]*i%mod)
    Finv=[0]*(m+1) 
    Finv[-1]=pow(Fact[-1],mod-2,mod)
    for i in range(m-1,-1,-1):
        Finv[i]=Finv[i+1]*(i+1)%mod
    def comb(n,r):
        if n<r:
            return 0
        return Fact[n]*Finv[r]*Finv[n-r]%mod
    
    if k>=n-1:
        return comb(2*n-1,n-1)
    ans=1
    for i in range(1,k+1):
        ans+=comb(n,i)*comb(n-1,n-i-1)
        ans%=mod
    return ans
    
if __name__=='__main__':
    print(main())

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


FACT=[1]
for i in range(1,5*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(5*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

ANS=0
for i in range(min(k+1,n)):
    ANS+=Combi(n-1,n-i-1)*Combi(n,i)
    

print(ANS%mod)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,K = inpl()

def comb(N,x):
    ret = 1
    for i in range(N-x+1,N+1):
        ret *= i
        ret %= mod

    for i in range(1, x+1):
        ret *= pow(i,mod-2,mod)
        ret %= mod

    return ret%mod

class Combination:
    def __init__(self,N):
        self.fac = [1]*(N+1)
        for i in range(1,N+1):
            self.fac[i] = (self.fac[i-1]*i)%mod
        self.invmod = [1]*(N+1)
        self.invmod[N] = pow(self.fac[N],mod-2,mod)
        for i in range(N,0,-1):
            self.invmod[i-1] = (self.invmod[i]*i)%mod

    def calc(self,n,k):
        return self.fac[n]*self.invmod[k]%mod *self.invmod[n-k] %mod




if N <= K:
    ans = comb(N*2-1, N)
    print(ans)
else:
    C = Combination(200000+3)
    ans = 0
    for z in range(K+1):
        r = N - z
        m = N - r
        ans += C.calc(N, z) * C.calc(r+m-1, m)
        ans %= mod

    print(ans)

Solution (Python):

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

NN = 10**6 
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

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

N, K = map(int, input().split())
if K >= N-1:
    ans = cmb(2*N-1, N)
else:
    ans = 0
    a = K
    while a >= 0:
        ans += cmb(N, a) * cmb(N-1, a) % mod
        ans %= mod
        a -= 1

print(ans)

Solution (Python):
n,k=map(int,input().split())
def find_power(n,mod):
    
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist

def find_inv_power(n):
    
    powlist=find_power(n,10**9+7)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist
mod=10**9+7
a=find_power(4*10**5+100,mod)
b=find_inv_power(4*10**5+100)
def combi(n,r,mod):
    if n<r:
        return 0
    elif n>=r:
        return (a[n]*b[r]*b[n-r])%(mod)
if n<=k:
    K=combi(2*n-1,n-1,mod)
    print(K)
    
else:
    K=combi(2*n-1,n-1,mod)
    for i in range(k+1,n):
        K-=combi(n-1,n-i-1,mod)*combi(n,i,mod)
    print(K%mod)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))


class BigCombination(object):

    def __init__(self, mod: int=10**9+7, max_n: int=10**6):
        fac, inv=[1], []
        fac_append, inv_append=fac.append, inv.append

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

        inv_append(pow(fac[-1], mod-2, mod))

        for i in range(max_n, 0, -1):
            inv_append(inv[-1] * i % mod)

        self.mod, self.factorial, self.inverse=mod, fac, inv[::-1]

    def get_combination(self, n, r):
        if n < r:
            return 0
        return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod

    def get_permutation(self, n, r):
        if n < r:
            return 0
        return self.factorial[n] * self.inverse[n-r] % self.mod

def main():
    B = BigCombination()
    N,K=MI()
    ans = ModInt(B.get_combination(N+N-1,N)) 
    
    if K>=N-1: 
        print(ans)
        return

    
    people = N
    for j in range(K+1, N):
        C = B.get_combination(N,j) 
        room = N-j
        ans -= C * B.get_combination(people-1, room-1)

    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
n, k = [int(i) for i in input().split()]
p = 10 ** 9 + 7

kk = [1]
for i in range(1, 2 * n + 1):
    kk.append(kk[i-1]*i % p)


def kai(x, p=p):
    if kk[x] != -1:
        return kk[x]
    a = 1
    for i in range(1, x + 1):
        a *= i
        a %= p
    kk[x] = a
    return a


def comb(a, b, p=p):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= kai(a, p)
    c *= pow(kai(b, p), p - 2, p)
    c *= pow(kai(a - b, p), p - 2, p)
    return c % p


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

        ans %= p
    print(ans)

Solution (Python):
MAX = 2*10**6+100
fact = [0]*MAX
inv = [0]*MAX
finv = [0]*MAX
 
def C_init():
    fact[0] = 1
    fact[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    
    for i in range(2, MAX):
        fact[i] = fact[i-1]*i%MOD
        inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
        finv[i] = finv[i-1]*inv[i]%MOD

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

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

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

Solution (Python):
n,k=map(int,input().split())
m=10**9+7
p=1
for i in range(1,n+1):p=(p*(2*n-i)*pow(i,m-2,m))%m
if k>=n:
    print(p)
else:
    c,d=1,1
    for i in range(1,k+1):c=(c*(n-i)*pow(i,m-2,m))%m
    for i in range(1,k+1):d=(d*(n-i+1)*pow(i,m-2,m))%m
    for i in range(k+1,n):
        c=(c*(n-i)*pow(i,m-2,m))%m
        d=(d*(n-i+1)*pow(i,m-2,m))%m
        p=(p-c*d)%m
    print(p)

Solution (Python):
n,k = map(int,input().split())
k = min(k,n-1)
mod = 10**9 + 7
ans = 1
z0 = 1
z1 = 1
def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    y %= mod
    x -= mod % x
  return y
for i in range(k):
  z0 *= n-i
  z0 %= mod
  z0 *= inv(i+1)
  z0 %= mod
  z1 *= n-1-i
  z1 %= mod
  z1 *= inv(i+1)
  z1 %= mod
  ans += z0 * z1
  
  ans %= mod
print(ans)