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):
MOD = 1000000007
n,k = map(int,input().split())


fac = [0]*(n+1)
finv = [0]*(n+1)
inv = [0]*(n+1)
answer = 0

def COMinit(n, MOD):
    fac[0] = fac[1] = 1
    finv[0] = 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

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


COMinit(n, MOD)

fac = tuple(fac)
finv = tuple(finv)
inv = tuple(inv)

a = n if n < k else k + 1

for i in range(a):
    answer += COM(n,i) * COM(n-1, n-i-1)
    
print(answer%MOD)

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

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

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

ans = 0

if k >= n-1:
    print(cmb(2*n-1,n,p))
else:

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

    print(ans)

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

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

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

ans = 0

if k >= n-1:
    print(cmb(2*n-1,n,p))
else:

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

    print(ans)

Solution (Python):
class COM:
    def __init__(self, n: int, mod: int):
        self.n = n
        self.mod = mod
        self.fact = [0] * (n + 1)
        self.factinv = [0] * (n + 1)
        self.inv = [0] * (n + 1)
        
        self.fact[0] = self.fact[1] = 1
        self.factinv[0] = self.factinv[1] = 1
        self.inv[1] = 1
        for i in range(2, n + 1):
            self.fact[i] = (self.fact[i - 1] * i) % mod
            self.inv[i] = (-self.inv[mod % i] * (mod // i)) % mod
            self.factinv[i] = (self.factinv[i - 1] * self.inv[i]) % mod
    
    def get_cmb(self, n: int, k: int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] % self.mod * self.factinv[n - k] % self.mod


def solve():
    n, k = map(int, input().split())
    MOD = 10 ** 9 + 7
    
    com = COM(n, MOD)
    ans = 0
    for i in range(min(n, k + 1)):
        ans += com.get_cmb(n, i) * com.get_cmb(n - 1, i)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
class COM:
    def __init__(self, n: int, mod: int):
        self.n = n
        self.mod = mod
        self.fact = [0] * (n + 1)
        self.factinv = [0] * (n + 1)
        self.inv = [0] * (n + 1)
        
        self.fact[0] = self.fact[1] = 1
        self.factinv[0] = self.factinv[1] = 1
        self.inv[1] = 1
        for i in range(2, n + 1):
            self.fact[i] = (self.fact[i - 1] * i) % mod
            self.inv[i] = (-self.inv[mod % i] * (mod // i)) % mod
            self.factinv[i] = (self.factinv[i - 1] * self.inv[i]) % mod
    
    def get_cmb(self, n: int, k: int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] % self.mod * self.factinv[n - k] % self.mod


def solve():
    n, k = map(int, input().split())
    MOD = 10 ** 9 + 7
    
    com = COM(n, MOD)
    ans = 0
    for i in range(min(n, k + 1)):
        ans += com.get_cmb(n, i) * com.get_cmb(n - 1, i)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
x=input().split()
n=int(x[0])
k=int(x[1])
def fact_inverse(n,p):
    fact=[1]*(n+1)
    inv=[1]*(n+1)
    inv_fact=[1]*(n+1)
    inv[0]=0
    inv_fact[0]=0
    for i in range(2,n+1):
        fact[i]=(fact[i-1]*i)%p
        
        inv[i]=(-inv[p%i]*(p//i))%p
        inv_fact[i]=(inv_fact[i-1]*inv[i])%p
    return fact,inv_fact    
    

def combi2(n,p):
    f,inv=fact_inverse(n,p)
    combis=[1]*(n+1)
    for k in range(1,n+1):
        if k >=n//2+1:
            combis[k]=combis[n-k]
        else:
            combis[k]=(((f[n]*inv[n-k])%p)*inv[k])%p
    return combis    
      
    
p=10**9+7
combis1=combi2(n,p)
combis2=combi2(n-1,p)
s=0
L=min(n,k+1)
for i in range(L):
  s=(s+(combis1[i]*combis2[i])%p)%p
print(s)

Solution (Python):
class COM:
    def __init__(self, n: int, mod: int):
        self.n = n
        self.mod = mod
        self.fact = [1, 1]
        self.factinv = [1, 1]
        self.inv = [0, 1]
        
        for i in range(2, n + 1):
            self.fact.append((self.fact[-1] * i) % mod)
            self.inv.append((-self.inv[mod % i] * (mod // i)) % mod)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % mod)
    
    def get_cmb(self, n: int, k: int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] % self.mod * self.factinv[n - k] % self.mod


def solve():
    n, k = map(int, input().split())
    MOD = 10 ** 9 + 7
    
    com = COM(n, MOD)
    ans = 0
    for i in range(min(n, k + 1)):
        ans += com.get_cmb(n, i) * com.get_cmb(n - 1, i)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
from itertools import accumulate
import numpy as np
MOD = 10 ** 9 + 7


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


def make_fact_and_inv(U, mod=MOD):
    """
    0~Nまでのサイズ(N+1)の階乗およびその逆元の配列を返す
    """
    tmp = np.arange(U, dtype=np.int64)
    tmp[0] = 1
    fact = cumprod(tmp, mod)
    tmp = np.arange(U, 0, -1, dtype=np.int64)
    tmp[0] = pow(int(fact[-1]), mod - 2, mod)
    inv = cumprod(tmp, mod)[::-1]
    return fact, inv


fact, inv = make_fact_and_inv(2 * 10 ** 5 + 10)


def nCr(n, r, mod=MOD):
    if r < 0 or r > n or n < 0:
        return 0
    return fact[n] * inv[r] % mod * inv[n - r] % mod


if __name__ == "__main__":
    N, K = map(int, input().split())

    ans = []
    for i in range(min(N - 1, K) + 1):
        val = nCr(N, i) * nCr(N - 1, i) % MOD
        ans.append(val)

    answer = 0
    while ans:
        answer = (answer + ans.pop()) % MOD
    print(answer)

Solution (Python):
class Combination():
    def __init__(self, N:int, P:int):
        self.N = N
        self.P = P
        self.fact = [1, 1]   
        self.factinv = [1, 1]
        self.inv = [0, 1] 

        for i in range(2, N+1):
            self.fact.append((self.fact[-1] * i) % P)
            self.inv.append((-self.inv[P % i] * (P // i)) % P)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % P)
    def getComb(self, n:int, k:int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] % self.P * self.factinv[n-k] % self.P

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

    COMB = Combination(n,MOD)

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

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):


class Combination():
    
    def __init__(self, N:int, P:int):
        self.N = N
        self.P = P

        
        self.fact = [1, 1]   
        
        self.factinv = [1, 1]
        
        self.inv = [0, 1] 

        for i in range(2, N+1):
            self.fact.append((self.fact[-1] * i) % P)
            self.inv.append((-self.inv[P % i] * (P // i)) % P)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % P)
    
    
    def getComb(self, n:int, k:int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] % self.P * self.factinv[n-k] % self.P

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

COMB = Combination(n,MOD)

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

print(ans)

Solution (Python):
import numpy as np

MOD=1000000007

n,k=map(int,input().split())
k=min(k,n-1)
fac=np.zeros((n+1)).astype(np.int64)
invfac=np.zeros((n+1)).astype(np.int64)
inv=np.zeros((n+1)).astype(np.int64)

invfac[0]=fac[0]=invfac[1]=fac[1]=inv[1]=1
for i in range(2,n+1):
    fac[i]=(fac[i-1]*i)%MOD
    inv[i]=(-inv[MOD%i]*(MOD//i))%MOD
    invfac[i]=(invfac[i-1]*inv[i])%MOD
def nCr(n,r):
    return ((fac[n]*invfac[r]%MOD)*invfac[n-r])%MOD
def nHr(n,r):
    return nCr(n+r-1,r)
    
print(np.sum(nCr(n,np.arange(k+1))*nHr(n-np.arange(k+1), np.arange(k+1))%MOD)%MOD)

Solution (Python):
import numpy as np

MOD=1000000007

n,k=map(int,input().split())
k=min(k,n-1)
fac=np.zeros((n+1)).astype(np.int64)
invfac=np.zeros((n+1)).astype(np.int64)
inv=np.zeros((n+1)).astype(np.int64)

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

ret = 0
x = nCr(n, np.arange(k+1))
y = nHr(n-np.arange(k+1), np.arange(k+1))
ret = np.sum(x*y%MOD)%MOD

print(ret)

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

ans = 1
nCl = 1
n1Cl = 1
for l in range(1,min(k+1,n)):
    nCl = nCl*(n+1-l)*pow(l,P-2,P)%P
    n1Cl = n1Cl*(n-l)*pow(l,P-2,P)%P
    ans = (ans+nCl*n1Cl)%P

print(ans)

Solution (Python):

import sys
INF = 1<<32
MOD = 1000000007  










def solve(n: int, k: int):
    fact = [1] * (n+1)
    ifact = [1] * (n+1)
    for i in range(1, n+1):
        fact[i] = i*fact[i-1] % MOD

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

    def comb(n, r, MOD=10**9+7):
        return fact[n] * ifact[n-r] * ifact[r] % MOD
    
    
    ans = 0
    for i in range(min(k, n-1)+1):
        ans += comb(n, i) * comb(n-1, i) % MOD
        ans %= MOD
    
    print(ans)

    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 main():
    import sys
    input = sys.stdin.readline

    
    mod = 1000000007
    nmax = 4 * 10 ** 5 + 10  
    fac = [0] * nmax
    finv = [0] * nmax
    inv = [0] * nmax
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2, nmax):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod

    def comb(n, r):
        if n < r:
            return 0
        else:
            return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod

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

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


if __name__ == '__main__':
    main()

Solution (Python):

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


mod = pow(10, 9) + 7

n_ = 4*10**5 + 5
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

if n <= k-1:
    print(cmb(2*n-1, n))
else:
    answer = 0
    for m in range(k+1):
        answer += cmb(n, m)*cmb(n-1, m) % mod
        answer %= mod
    print(answer)

Solution (Python):


MOD = 10**9 + 7

def getModInv(a, b):
    return 1 if (a == 1) else (1-b*getModInv(b%a, a))//a%b


N, K = map(int, input().split())
t1, t2 = 1,1
s1, s2 = 1,1

for m in range(1, min(K, N-1)+1):
    t1 = t1*(N-m)*(N-m+1)%MOD
    t2 = t2*m**2%MOD

    s1 = (s1*t2 + s2*t1)%MOD
    s2 = s2*t2%MOD

print(s1*getModInv(s2, MOD)%MOD)

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


N=4*10**5+10
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)

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

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

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


def solve(n, k):
    
    if k == 0:
        return 1
    elif k == 1:
        return n * (n - 1)

    
    pow_mod = [1] * (n + 1)
    for i in range(n):
        pow_mod[i + 1] = pow_mod[i] * (i + 1) % LARGE
    pow_mod_inv = [1] * (n + 1)
    pow_mod_inv[-1] = pow(pow_mod[-1], LARGE - 2, LARGE)
    for i in range(n - 1, 0, -1):
        pow_mod_inv[i] = pow_mod_inv[i + 1] * (i + 1) % LARGE

    res = 0
    for i in range(min(k, n - 1) + 1):
        
        pick_zeros = pow_mod[n] * pow_mod_inv[i] * pow_mod_inv[n - i] % LARGE
        
        assign_ones = pow_mod[n - 1] * pow_mod_inv[i] * pow_mod_inv[n - 1 - i] % LARGE
        res += pick_zeros * assign_ones
        res %= LARGE
    return res


def main():
    n, k = map(int, input().split())
    res = solve(n, k)
    print(res)


def test():
    assert solve(3, 2) == 10
    assert solve(200000, 1000000000) == 607923868
    assert solve(15, 6) == 22583772


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

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

MOD = 1000000007

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

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

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

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

mod = 10 ** 9 + 7
N = 10 ** 6


inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]


kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
	kai.append(kai[-1] * i % mod)
	rev_kai.append(rev_kai[-1] * inv_t[i] % mod)


def cmb(n, r):
	return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

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

Solution (Python):
from itertools import accumulate


class Combination:
    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


if __name__ == "__main__":
    N, K = map(int, input().split())
    MOD = 10**9+7
    comb = Combination(2*10**5+5, MOD)

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

    answer = 0
    while ans:
        answer = (answer + ans.pop()) % MOD
    print(answer)

Solution (Python):
def comb(n, r):
    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
MAXN=400000+10
g1=[1, 1]
g2=[1, 1]
inverse=[0, 1]

for i in range(2, MAXN+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:
    print(comb(N*2-1, N))
else:
    ans=1
    for i in range(1, K+1):
        ans=(ans+(comb(N-1, i)*comb(N, i))%MOD)%MOD
    print(ans)

Solution (Python):
N=2*10**5+1
mod=10**9+7
f=[None]*N
fi=[None]*N
f[0]=1
for i in range(1,N):
  f[i]=i*f[i-1]%mod
for i in range(N):
  fi[i]=pow(f[i],mod-2,mod)
def com(n,k):
  return f[n]*fi[n-k]%mod*fi[k]%mod
def hcom(n,k):
  return com(n+k-1,n-1)
n,k=map(int,input().split())
ans=1
for i in range(1,min(k+1,n)):
  ans=(ans+com(n,i)*hcom(n-i,i)%mod)%mod
print(ans)

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

mod = 10**9+7
ans = 1%mod
left_combination = 1
right_combination = 1

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

print(ans)

Solution (Python):
import math
import sys

sys.setrecursionlimit(10**9)

MOD = 10**9+7

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

fact = [1]
for i in range(1, 10**6):
    fact.append((fact[i-1]*i)%MOD)

inv = [None]*10**6
def inv_fact(n):
    if inv[n] == None:
        inv[n] = pow(fact[n], MOD-2, MOD)
    return inv[n]

def comb(n, r):
    return (fact[n]*inv_fact(n-r)*inv_fact(r))%MOD

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

Solution (Python):
MAX = 1000005
MOD = 10**9+7
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX



def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD



def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD



COMinit()


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

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

fact = [0] * (N+1)
finv = [0] * len(fact)
inv  = [0] * len(fact)

fact[0] = fact[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, len(fact)):
    fact[i] = fact[i-1] * i % MOD

    inv[i] = - inv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD

nCr = lambda n, r: fact[n] * finv[n-r] * finv[r] % MOD
nHr = lambda n, r: nCr(n+r-1, r)





ans = sum(nCr(N, i) * nCr(N-1, i) for i in range(min(N-1, K) + 1))
print(ans % MOD)

Solution (Python):



from functools import reduce

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








class Combination:
    def __init__(self):
        self.fac = [None for _ in range(table_size)]
        self.finv = [None for _ in range(table_size)]
        self.inv = [None for _ in range(table_size)]

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

        for i in range(2, table_size):
            self.fac[i] = self.fac[i - 1] * i % mod
            
            
            self.inv[i] = pow(i, mod - 2, mod)
            self.finv[i] = self.finv[i - 1] * self.inv[i] % mod

    def nCr(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0

        return self.fac[n] * (self.finv[r] * self.finv[n - r] % mod) % mod


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




c = Combination()

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

print(total)

Solution (Python):
import sys
input = sys.stdin.readline
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 2* 10 ** 5+2  
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 solve():
  n,k = (int(i) for i in input().split())
  mod = 10**9+7
  if n-k <= 1:
    
    comba = 1
    inva = 1
    for i in range(1,n+1):
      comba *= (n+i-1)
      inva *= i
      comba %= mod
      inva %= mod
    comba *= pow(inva,10**9+5,mod)
    comba %= mod
    print(comba)
  else:
    
    
    ans = 0
    
    
    
    for i in range(0,k+1):
      ans += cmb(n,i,mod)*cmb(n-1,i,mod)
      ans %= mod
    
    print(ans)
  
solve()

Solution (Python):



from functools import reduce

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








class Combination:
    def __init__(self):
        self.fac = [None for _ in range(table_size)]
        self.finv = [None for _ in range(table_size)]
        self.inv = [None for _ in range(table_size)]

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

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

    def nCr(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0

        return self.fac[n] * (self.finv[r] * self.finv[n - r] % mod) % mod


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




c = Combination()

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

print(total)

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

MOD = 10 ** 9 + 7

class ModCmb:
    def __init__(self, size):
        self.inv = [1] * (size + 1)
        self.fact = [1] * (size + 1)
        temp_inv = [1] * (size + 1)
        for i in range(2, size + 1):
            temp_inv[i] = ( -(MOD // i) * temp_inv[MOD%i] ) % MOD
        for i in range(2, size + 1):
            self.fact[i] = self.fact[i-1] * i % MOD
            self.inv[i] = self.inv[i-1] * temp_inv[i] % MOD

    def cmb(self, n, r):
        if n <= 1 or n == r:
            return 1
        elif r == 1:
            return n
        else:
            return  (self.fact[n] * self.inv[r] % MOD ) * self.inv[n-r] % MOD

mc = ModCmb(n)

ans = n * (n-1) + 1

for m in range(2, min(n, k+1)):
    ans = ( ans + ((mc.cmb(n, m) % MOD) * mc.cmb(n-1, m)) % MOD ) % MOD

print(ans)

Solution (Python):



from functools import reduce
table_size = 510000

mod = 10**9+7








class Combination:
    def __init__(self):
        self.fac = [None for _ in range(table_size)]
        self.finv = [None for _ in range(table_size)]
        self.inv = [None for _ in range(table_size)]

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

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

    def nCr(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0

        return self.fac[n] * (self.finv[r] * self.finv[n - r] % mod) % mod


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




c = Combination()


if n < k:
    print(c.nCr(2 * n - 1, n))
else:
    total = 0
    for i in range(k + 1):
        total += c.nCr(n - 1, i) * c.nCr(n, i)
        total %= mod

    print(total)

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

def modcomb(n,a,mod):
    cnt = 1
    for i in range(a):
        cnt *= (n-i)
        cnt *= pow(i+1,mod-2,mod)
        cnt %= mod
    
    return cnt

def modconb(n,mod):
    
    fac = [0]*(n+1)
    finv = [0]*(n+1)
    inv = [0]*(n+1)  

    fac[0] = fac[1] = 1
    finv[0] = 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
    


cnt = 0
if n-1 >= K:
    fac1,finv1 = modconb(n,mod)
    for k in range(K+1):
        c1 = fac1[n]*(finv1[k]*finv1[n-k]%mod)%mod
        c2 = fac1[n-1]*(finv1[k]*finv1[n-1-k]%mod)%mod
        cnt += c1*c2
        cnt %= mod
    print(cnt%mod)
else:
    cnt1 = modcomb(2*(n-1),n-1,mod)
    cnt2 = modcomb(2*(n-1),n,mod)
    ans = (cnt1+cnt2)%mod
    print(ans)

Solution (Python):


import sys


def read_int_list(sep=" "):
    return [int(s) for s in sys.stdin.readline().rstrip().split(sep)]


def dprint(*args, **kwargs):
    return
    print(*args, **kwargs)


facto = None
ifacto = None

def precompute_facto(n, mod):
    global facto, ifacto
    facto = [1] * (n + 1)
    for i in range(1, n + 1):
        facto[i] = (facto[i - 1] * i) % mod
    ifacto = [1] * (n + 1)
    ifacto[n] = mod_inv(1, facto[n], mod)
    for i in range(0, n):
        p = n - i
        ifacto[p - 1] = ifacto[p] * p % mod


def mod_inv(a, b, mod):
    return (a * pow(b, mod - 2, mod)) % mod


def choose(a, b, mod):
    return facto[a] * ifacto[a - b] % mod * ifacto[b] % mod


def multi_choose(a, b, mod):
    return choose(a + b - 1, b, mod)


def main():
    mod = 1000000007
    n, k = read_int_list()
    precompute_facto(n, mod)
    ans = 0
    for i in range(0, min(k, n - 1) + 1):
        ans = (ans + choose(n, i, mod) * multi_choose(n - i, i, mod)) % mod
    print(ans)


if __name__ == "__main__":
    main()

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

p = 10 ** 9 + 7
N = 10 ** 5 *5  
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 3):
    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 (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

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

print(ans)

Solution (Python):

def exp_by_sq(a, n, p):
    if n == 0:
        exp = 1
    elif n == 1:
        exp = a % p
    elif  n % 2 == 0:
        exp = exp_by_sq(a * a % p, n // 2, p)
    else:
        exp = a * exp_by_sq(a * a % p, (n - 1) // 2, p) % p
    return exp % p


n, k = [int(x) for x in input().split()]

p = 10 ** 9 + 7

m = min(n, k)

binom = n 
ans = n * ((n * n - n + 1) % p) % p  
inv = [0, 1]
inv_n = exp_by_sq(n, p - 2, p)  

for i in range(2, m + 1):
    inv_i = ( inv[p % i] * (p - p//i) ) % p  
    inv.append(inv_i)
    binom = (binom * (n - i + 1) % p) * inv_i % p
    ans = (ans + (binom * binom % p) * (n - i)) % p

ans = ans * inv_n % p
print(ans)

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 = 10**6+100
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

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

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

Solution (Python):
def comb(n, k, MOD):
    if n < k:
        return 0
    if n - k < k:
        k = n - k
    comb = 1
    for x in range(n - k + 1, n + 1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, k + 1):
        d = (d * x) % MOD
    comb *= pow(d, MOD - 2, MOD)
    return comb % MOD

n, k = map(int, input().split())
ans = 0
v = n
w = n - 1

ans = 1 + v * w
mod = 10 ** 9 + 7

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



print(ans)

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

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


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


INV = dict()
def inv(a, mod):
    if a in INV:
        return INV[a]
    i = pow(a, mod - 2, mod)
    INV[a] = i
    return i 


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


def main():
    N, K = read_values()
    mod = 10 ** 9 + 7
    F = functional(5 * 10 ** 5, mod)
    res = 0
    if N <= K:
        res = C(F, 2 * N - 1, N - 1, mod)
    else:
        for k in range(K + 1):
            res += C(F, N, k, mod) * C(F, N - 1 , k, mod) % mod
    
    print(res % mod)


if __name__ == "__main__":
    main()