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

Solution (Python):


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


class Combination(): 
    """
    O(n+log(mod))の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    C = Combination(10**6)
    print(C.combi_mod(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7): 
        self.mod = mod
        self.fac, self.facinv = self.prepare(n_max)
        
        
    def prepare(self,n): 
        
        
        factorials = [1]  
        for m in range(1, n+1):
            factorials.append(factorials[m-1]*m%self.mod)
        
        invs = [1] * (n+1)
        invs[n] = pow(factorials[n], self.mod-2, self.mod)
        for m in range(n, 1, -1):
            invs[m-1] = invs[m]*m%self.mod
        return factorials, invs 
    
    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 perm_mod(self,n,r): 
        if n < r:
            return 0
        if (n < 0 or r < 0):
            return 0
        return (self.fac[n] * self.facinv[n-r]) % self.mod

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

    def repeated_permutation(self,n,deno): 
        
        
        if n < max(deno):
            return 0
        if (n < 0 or min(deno) < 0):
            return 0
        D = 1
        for i in range(len(deno)):
            D = D*self.facinv[deno[i]] % self.mod
        return self.fac*D % self.mod 
    
    def H(self,n,r): 
        now_n = len(self.fac)
        if now_n < n+r-1: 
            for i in range(now_n+1, n+r-1+1):
                self.fac.append(self.fac[i-1]*i%self.mod)
        return self.combi_mod(n+r-1,r)


mod = 10**9+7
C = Combination(n,mod)
ans = 0
for i in range(min(k+1,n+1)):
    ans += C.combi_mod(n,i)*C.H(n-i,i)
    ans %= mod
print(ans)

Solution (Python):












DIV = 10 ** 9 + 7
n = 10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

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

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

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






ans = 0
for i in range(min(K,N-1) + 1):
  a = nCr(N,i,DIV)
  
  
  
  
  
  
  b = nCr(N-1,i,DIV)
  
  ans += (a * b) % DIV
  ans %= DIV
  
print(ans)

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


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

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

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


MAX=min(n-1,k)

dp=[0]*(MAX+1)
dp[0]=1
ans=1
for i in range(1,MAX+1):
    ans+=cmb(n,i,p)*cmb(n-i+i-1,i,p)
    ans%=p
    

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self, n):
        fact, invfact = [1] * (n + 1), [1] * (n + 1)
        for i in range(1, n + 1): fact[i] = i * fact[i - 1] % MOD
        invfact[n] = pow(fact[n], MOD - 2, MOD)
        for i in range(n - 1, -1, -1): invfact[i] = invfact[i + 1] * (i + 1) % MOD
        self._fact, self._invfact = fact, invfact

    def inv(self, n):
        return self._fact[n - 1] * self._invfact[n] % MOD

    def fact(self, n):
        return self._fact[n]

    def invfact(self, n):
        return self._invfact[n]

    def comb(self, n, k):
        if k < 0 or n < k: return 0
        return self._fact[n] * self._invfact[k] % MOD * self._invfact[n - k] % MOD

    def perm(self, n, k):
        if k < 0 or n < k: return 0
        return self._fact[n] * self._invfact[n - k] % MOD

def resolve():
    n, k = map(int, input().split())
    mf = modfact(n)
    res = 0
    for i in range(min(k + 1, n)):
        res += mf.comb(n, i) * mf.comb(n - 1, i) % MOD
        res %= MOD
    print(res)
resolve()

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
size = 4*10**5
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

k = min(k, n-1)

ans = 0

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

ans %= mod

print(ans)

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

MOD = int(1e+9+7)

max_zero_num = min(n-1, k)
kai = [1]*(n+1)
gyaku_kai = [1]*(n+1)

for i in range(n):
    kai[i+1] = kai[i]*(i+1) % MOD
    gyaku_kai[i+1] = pow(kai[i+1], MOD-2, MOD)%MOD
        
answer = 0
for zero_num in range(max_zero_num+1):
    answer = (answer + kai[n]*gyaku_kai[n-zero_num]*gyaku_kai[zero_num]*\
    kai[n-1]*gyaku_kai[n-1-zero_num]*gyaku_kai[zero_num]) %MOD

print(answer)

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

def prepare(n, MOD):
    facts = [1]*(n+1)
    for i in range(1, n+1):
        facts[i] = facts[i-1]*i%MOD
    invs = [1]*(n+1)
    _invs = [1]*(n+1)
    invs[n] = pow(facts[n], MOD-2, MOD)
    for i in range(0, n)[::-1]:
        invs[i] = invs[i+1] * (i+1) % MOD
    return facts, invs

ans = 0
facts, invs = prepare(n, MOD)

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

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**5)*2+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 )

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

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

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

MOD = 10**9+7
fac = [1]*(N+1)
rev = [1]*(N+1)
 
for i in range(1, N+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)

comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD
ans = 0

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

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

MOD = 10**9+7
fac = [1]*(N+1)
rev = [1]*(N+1)
 
for i in range(1, N+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)

comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD
ans = 0

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

Solution (Python):

import sys

sysread = sys.stdin.readline


sys.setrecursionlimit(10**7)
import math

def run():
    n,k = map(int, input().split())
    mod = 10 ** 9 + 7
    ret = 0
    inv = generate_inv(n, mod)

    if k >= n-1:
        k = n-1
    left = 1
    right = 1
    ret = 1
    for h in range(1, k+1):
        right *= (n - h) * inv[h]
        right %= mod
        left *= (n - h + 1) * inv[h]
        left %= mod
        ret += right * left
        ret %= mod
    print(ret)


def generate_inv(n,mod):
    """
    逆元行列
    n >= 2
    """
    ret = [0, 1]
    for i in range(2,n+1):
        next = -ret[mod%i] * (mod // i)
        next %= mod
        ret.append(next)
    return ret


def comb_mod(n, a, mod):
    """
    return: [n, a] % mod
    Note: mod must be a prime number
    """
    up = 1
    down = 1
    for i in range(a):
        up *= n - i
        up %= mod
        down *= i + 1
        down %= mod
    down = pow_mod(down, mod - 2, mod)
    return (up * down) % mod

def pow_mod(n, k, mod):
    res = 1
    while True:
        if k // 2 >= 1:
            if k % 2 == 1:
                res = (res * n) % mod
            n = (n ** 2) % mod
            k = k // 2
        else:
            break
    return (n * res) % mod


if __name__ == "__main__":
    run()

Solution (Python):
M=10**9+7
n,k=map(int,input().split())
from functools import lru_cache
@lru_cache(None)
def f(x):
  if x: return x*f(x-1)%M
  return 1
l=[f(i) for i in range(n+1)]
a=0
for i in range(min(n,k+1)):
  c=l[n]*l[n-1]%M
  p=l[i]**2*l[n-i]*l[n-i-1]%M
  a+=c*pow(p,M-2,M)
print(a%M)

Solution (Python):
M=10**9+7;n,k=map(int,input().split());a=c=1
for i in range(1,min(n,k+1)):m=n-i;c=c*-~m*m*pow(i,M-2,M)**2%M;a+=c
print(a%M)

Solution (Python):
M=10**9+7;n,k=map(int,input().split());a=c=1
for i in range(1,min(n,k+1)):m=n-i;c=c*-~m*m*pow(i,M-2,M)**2%M;a+=c
print(a%M)

Solution (Python):
M=10**9+7;n,k=map(int,input().split());a=c=p=1
for i in range(1,min(n,k+1)):c=c*(n-i+1)*(n-i)%M;p=p*i*i%M;a+=c*pow(p,M-2,M)
print(a%M)

Solution (Python):
M=10**9+7
n,k=map(int,input().split())
a=c=p=1
for i in range(1,min(n,k+1)):
  c=c*(n-i+1)*(n-i)%M
  p=p*i*i%M
  a+=c*pow(p,M-2,M)
print(a%M)

Solution (Python):
M=10**9+7
n,k=map(int,input().split())
l=[1]
f=1
for i in range(n):
  f=f*(i+1)%M
  l+=[f]
a=0
for i in range(min(n,k+1)):
  c=l[n]*l[n-1]%M
  p=l[i]**2*l[n-i]*l[n-i-1]%M
  a+=c*pow(p,M-2,M)
print(a%M)

Solution (Python):
M=10**9+7
n,k=map(int,input().split())
l=[1]
f=1
for i in range(n):
  f=f*(i+1)%M
  l+=[f]
a=0
for i in range(min(n,k+1)):
  c=p=1
  c=c*l[n]*l[n-1]%M
  p=p*l[i]**2*l[n-i]*l[n-i-1]%M
  a+=c*pow(p,M-2,M)
print(a%M)

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

S = [0]*(2*10**5+1)
S[1] = 1
for i in range(2, 2*10**5+1):
    S[i] = S[MOD%i]*(MOD-int(MOD/i))%MOD

if N-1 <= K:
    ans = 1
    num = 2*N - 1
    for i in range(N-1):
        ans *= (num-i)*S[i+1]
        ans %= MOD
    print(ans%MOD)
else:
    S1 = [1]*N
    S2 = [1]*N
    for i in range(1, N):
        S1[i] = (S1[i-1]*(N+1-i)*S[i])%MOD
        S2[i] = (S2[i-1]*(N-i)*S[i])%MOD
    ans = 0
    for i in range(K+1):
        ans += S1[i]*S2[N-1-i]
        ans %= MOD
    print(ans)

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

A = [0]*(m+1)
B = [0]*(m+1)

for i in range(m+1):
    if i == 0:
        A[0] = 1
        B[0] = 1
    else:
        A[i] = ((A[i-1]*(n-i+1))*pow(i,mod-2,mod)) % mod
        B[i] = ((B[i-1]*(n-i))*pow(i,mod-2,mod)) % mod

ans = 0
for i in range(m+1):
    ans = (ans+A[i]*B[i]) % mod

print(ans % mod)

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

nCk = 1
ans = 1

if k > n-1:
    k = n-1

for i in range(1,k+1,1):
    nCk = (((nCk*(n-i+1))%MOD)*pow(i,1000000005,1000000007))%MOD
    ans = (ans%MOD + ((((nCk*nCk)%MOD)*(n-i)%MOD)*pow(n,1000000005,1000000007)%MOD)%MOD)%MOD

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 = 2 * 10 ** 5  
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

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

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

Solution (Python):

nmax = 3*10**5
mod = 10**9+7

fac = [1]*nmax
finv = [1]*nmax
inv = [1]*nmax
def ncr_pre():
    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 ncr(n,r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fac[n]* (finv[r] * finv[n-r] %mod) %mod


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

Solution (Python):


import sys





















def main():
    mod = 1000000007                
    inf = float('inf')              
    inf = 2 ** 64 - 1               
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, k = mi()
    factorial = [1] * (n + 1)
    for i in range(1, n + 1):
        factorial[i] = (factorial[i - 1] * i) % mod
    

    def combination(n, r, mod):
        
        
        numerator = factorial[n]
        denominator = (factorial[r] * factorial[n - r]) % mod
        return (numerator * pow(denominator, mod - 2, mod)) % mod
    
    ans = 0
    for empty_room_num in range(min(n - 1, k) + 1):
        ans = (ans + combination(n, empty_room_num, mod) * combination(n - 1, empty_room_num, mod)) % mod
        
    print(ans)
        

if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin

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

mod=10**9+7
fact=[1]*(2*N)
finv=[1]*(2*N)
inv=[1]*(2*N)
inv[0]=0
for i in range(2,2*N):
    fact[i]=(fact[i-1]*i%mod)
    inv[i]=(-inv[mod%i]*(mod//i))%mod
    finv[i]=(finv[i-1]*inv[i])%mod

def com(N,K,mod):
    if (K<0) or (N<K):
        return 0
    return fact[N]*finv[K]*finv[N-K]%mod

if N-1<=K:
    print(com(2*N-1,N,mod))

else:
    res=0
    for m in range(K+1):
        res+=com(N,m,mod)*com(N-1,m,mod)
        res%=mod
    print(res)

Solution (Python):

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

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

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

def make_fact(U, 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]
    return fact, fact_inv

U = 10 ** 6  
fact, fact_inv = make_fact(U, MOD)

N, K = lr()
K = min(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 = (x * y % MOD).sum()
print(answer % MOD)

Solution (Python):

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7


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

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

def make_fact(U, 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]
    return fact, fact_inv

U = 10 ** 6  
fact, fact_inv = make_fact(U, MOD)

N, K = lr()
answer = 0
for x in range(N, max(0, N-K-1), -1):
    
    can_move = N - x
    
    answer += cmb(N, x) * cmb(x - 1 + can_move, can_move)
    answer %= MOD
    
print(answer % MOD)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    
    mod = 10**9 + 7

    max_n = 2*(10**5)
    fac, inv = [1]*(max_n+1), [0]*(max_n+1)
    for i in range(2, max_n+1):
        fac[i] = fac[i-1] * i % mod
    inv[-1] = pow(fac[-1], mod-2, mod)
    for i in range(max_n, 0, -1):
        inv[i-1] = inv[i] * i % mod

    
    def ncr(n, r):
        return fac[n]*inv[r]*inv[n-r]%mod

    n, k = map(int, input().split())
    res = 0
    
    for i in range(n):
        if i > k:
            continue
        res += ncr(n, i) * ncr(n-1, i)
        res %= mod
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    
    mod = 10**9 + 7

    max_n = 2*(10**5)
    fac, inv = [1]*(max_n+1), [0]*(max_n+1)
    for i in range(2, max_n+1):
        fac[i] = fac[i-1] * i % mod
    inv[-1] = pow(fac[-1], mod-2, mod)
    for i in range(max_n, 0, -1):
        inv[i-1] = inv[i] * i % mod

    
    def ncr(n, r):
        return fac[n]*inv[r]*inv[n-r]%mod

    n, k = map(int, input().split())
    res = 0
    
    for i in range(n):
        if i > k:
            continue
        res += ncr(n, i) * ncr(n-1, i)
        res %= mod
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, kk = map(int, input().split())

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

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r] % mod, mod-2, mod)*fact[n] % mod

    ans = [1]

    for k in range(1, n):
        ans.append(nCr(n-1, k)*nCr(n, k) % mod)

    print(sum(ans[:min(kk+1, n)]) % mod)


main()

Solution (Python):
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

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


def main():
    MOD = 10 ** 9 + 7

    N, K = map(int, input().split())
    K = min(K, N - 1)  

    calc = Calc(max_value=N * 2, mod=MOD)

    ans = 0
    for v in range(K + 1):  
        ans = (ans + (calc.combination(N, v) * calc.combination(v + (N - v) - 1, v)) % MOD) % MOD

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

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


def main():
    MOD = 10 ** 9 + 7

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

    calc = Calc(max_value=N * 2, mod=MOD)

    ans = 0
    for v in range(K + 1):  
        ans = (ans + calc.combination(N, v) * calc.combination(v + (N - v) - 1, v)) % MOD

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  


def combination_mod(n, r, mod):
    
    
    r = min(r, n - r)
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i) % mod
        rf = rf * (i + 1) % mod
    return nf * pow(rf, mod - 2, mod) % mod


def ret_list_combination_mod(n, r, mod):
    ret = [1]
    if r > n:
        return 0  
    
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i) % mod
        rf = rf * (i + 1) % mod
        ret.append(nf * pow(rf, mod - 2, mod) % mod)
    return ret




MOD = 10**9 + 7
n, k = read_ints()

if n <= k:
    print(combination_mod(n + n - 1, n, MOD))
    exit()


ans = 1
nCa = ret_list_combination_mod(n, k, MOD)
n_1Ca = ret_list_combination_mod(n - 1, k, MOD)
for a in range(1, k + 1):
    ans += nCa[a] * n_1Ca[a]  
    ans %= MOD
print(ans)

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

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            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 npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  
        return self.ncr(n + r - 1, n - 1)

N, K = map(int, input().split())
K = min(K, N)
MOD = 10**9 + 7
comb = Combination(N + 100)

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

print(ans)

Solution (Python):
class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def nhr(self, n, r):  
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

N, K = map(int, input().split())
K = min(K, N)
MOD = 10**9 + 7
comb = Combination(N + 100)

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

print(ans)

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

fact = [1]*(n+1)
ans = 0
for i in range(1,n+1):
    fact[i] = fact[i-1]*i
    fact[i] %= mod
invfact = [1] * (n+1)
invfact[-1] = pow(fact[-1],mod-2,mod)
for i in range(n-1,0,-1):
    invfact[i] = (invfact[i+1]*(i+1))%mod
def C(x,y):
    if x<=y:return 1
    return fact[x]*invfact[y]*invfact[x-y]%mod


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

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

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

MOD = 10**9 + 7
fac = [1 for k in range(200010)]
inv = [1 for k in range(200010)]
finv = [1 for k in range(200010)]
for k in range(2,200010):
    fac[k] = (fac[k-1]*k)%MOD
    inv[k] = (MOD - inv[MOD%k] * (MOD // k))%MOD
    finv[k] = (finv[k - 1] * inv[k]) % MOD;
def nCr(n,r):
    return (fac[n]*finv[r]*finv[n-r])%MOD

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

print(ans)

Solution (Python):
mod = int(10 ** 9) + 7

def modinv(x, m = mod):
    b = m
    u = 1
    v = 0
    while b:
        t = x // b
        x -= t * b
        x, b = b, x
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u

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

    if k > n-1:
        k = n-1

    factorial = [None for _ in range(200001)]
    factorial[0] = 1
    factorial[1] = 1
    for i in range(2, 200001):
        factorial[i] = (factorial[i-1] * i) % mod

    posCount = [None for _ in range(n+1)]
    for i in range(n+1):
        posCount[i] = (factorial[n] * modinv((factorial[i] * factorial[n-i]) % mod)) % mod

    placeCount = [None for _ in range(n+1)]
    placeCount[0] = 0
    for i in range(1, n+1):
        placeCount[i] = (factorial[n-1] * modinv((factorial[i-1] * factorial[(n-1)-(i-1)]) % mod)) % mod

    ans = 0
    for i in range(-1, -k-2, -1):
        ans = (ans + (posCount[i] * placeCount[i])) % mod
    if k == 1:
        ans -= 1
        if ans < 0:
            ans += mod

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict as dd
N,k = map(int, input().split())




res = 0
fact = [0]*(N+1)
ifact = [0]*(N+1)
inv = [0]*(N+1)
p=10**9+7

dic = dd(int)

def combination(n,fact,ifact):
    fact[0] = 1
    fact[1] = 1
    ifact[0] = 1
    ifact[1] = 1
    inv[1] = 1
    for i in range(2,n+1):
        fact[i] = (fact[i-1]*i)%p
        inv[i] = p - inv[p%i]*(p//i)%p
        ifact[i] = (ifact[i-1]*inv[i])%p
def op(n,k):
    if (n,k) in dic.keys():
        return dic[(n,k)]
    if k<0 or k>n or n<0:
        return 0
    dic[(n,k)] = (fact[n]*ifact[k]*ifact[n-k])%(10**9+7)
    return dic[(n,k)]

combination(N,fact,ifact)
for t in range(0, min(k, N-1)+1):
    
    
    
    res += (op(N-1, N-t-1) * op(N, t))%p
print(res%p)

Solution (Python):
U = 2 * 10 ** 5
mod = 10 ** 9 + 7


class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    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())
    comb = Combination(U + 5, mod)

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