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):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7







lim = 10 ** 6 + 1
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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

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

N, K = getNM()














if K >= 2:
    ans = 1 
else:
    ans = 0

for k in range(1, min(K + 1, N)):
    
    
    
    
    ans += cmb(N, k) * cmb(N - 1, N - k - 1)
    ans %= mod
print(ans % mod)

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))




def main():
	n,k=MI()
	mod=10**9+7

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

	ans=0
	for i in range(k+1):
		if n-i-1>=0:
			ans+=f[n]*finv[i]*finv[n-i]*f[n-1]*finv[i]*finv[n-i-1]
			ans%=mod
		else:
			break
	print(ans%mod)








if __name__ == "__main__":
	main()

Solution (Python):
N, K = map(int, input().split())
K = min(N-1, K)
fact = [1 for _ in range(200001)]
inv = [1 for _ in range(200001)]
fact_inv = [1 for _ in range(200001)]
mod = 10**9+7
for i in range(2, 200001):
    fact[i] = (fact[i-1]*i) % mod
    inv[i] = mod - (inv[mod % i] * (mod // i)) % mod
    fact_inv[i] = (fact_inv[i-1] * inv[i]) % mod

dp = [0] * N
for i in range(N):
    f1 = (fact[N] * fact_inv[N-i] * fact_inv[i]) % mod  
    f2 = (fact[N-1] * fact_inv[N-i-1] * fact_inv[i]) % mod 
    f = (f1*f2)%mod
    if i == 0:
        dp[i] = f
    else:
        dp[i] = (dp[i-1] + f) % mod
print(dp[K])

Solution (Python):
import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N, K = map(int, input().split())
MAX = 10 ** 6 + 5
MOD = 10 ** 9 + 7

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

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


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

def p(n, r, mod):
    return fac[n] * finv[n - r] % mod
    
comInit(MOD)

ans = 0
if K + 1 >= N:
    ans = com(N + N - 1, N - 1, MOD)
else:
    for i in range(K + 1):
        ans += com(N, i, MOD) * com(i + N - i - 1, i, MOD) % MOD
        ans %= MOD
print(ans % MOD)

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

m = 4*10**5 + 500

fac = [1] * (m + 1)
facinv = [1] * (m + 1)
for i in range(1, m+1):
    fac[i] = (fac[i-1] * i) % mod
    facinv[i] = (facinv[i-1] * pow(i, -1, mod)) % mod

def nCk(n, k):
    return (fac[n] * facinv[k] * facinv[n-k]) % mod

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

Solution (Python):
n, k = list(map(int, input().split()))
mod = 1000000007
fac = [1]
inv = [1]
for i in range(n * 2):
    fac.append(fac[-1] * (i + 1) % mod)
    inv.append(pow(fac[-1], mod - 2, mod))


def cmb(n, k):
    if k < 0 or k > n:
        return 0
    return ((fac[n] * inv[k]) % mod * inv[n - k]) % mod


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

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


def main():
    mod=10**9+7
    N,K=MI()
    
    def cmb(n, r, mod):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return (fact[n] * factinv[r] * factinv[n-r])%mod

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

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

    ans=0
    
    
    for i in range(min(K+1,N)):
        a=i
        b=N-i
        temp=cmb(a+b-1,a,mod)
        
        
        temp2=cmb(N,i,mod)
        temp*=temp2
        
        ans=(ans+temp)%mod
        
    print(ans)
        
    

main()

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

mod = 1000000007

def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

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

def cmb(n, k):
    if k < 0 or k > n:
        return 0
    return (fac[n] * inv[k] * inv[n - k]) % mod

x = max(0, n - k - 1)
ret = cmb(n * 2 - 1, n - 1)
for i in range(x):
    ret = (ret - cmb(n, i + 1) * cmb(n - 1, i)) % mod
print(ret)

Solution (Python):
mod_val = 10**9+7
n, k = map(int, input().split())
factorials = [1]*(n+1)  
for i in range(2, n+1):
  factorials[i] = (factorials[i-1]*i)%mod_val
def mod_binomial(a, b):
  numerator = factorials[a]
  denominator = (factorials[b]*factorials[a-b])%mod_val
  invert = pow(denominator, mod_val-2, mod_val)
  return (numerator*invert)%mod_val
partial = 0

for m in range(min(k+1, n)):
  
  
  partial = (partial + (mod_binomial(n, m) * mod_binomial(n-1, m))%mod_val)%mod_val
print(partial)

Solution (Python):
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
mod = 10**9+7 
N = 5*10**5 
g1 = [0]*(N+1) 
g1[0] = g1[1] = 1
g2 = [0]*(N+1) 
g2[0] = g2[1] = 1
inverse = [0]*(N+1) 
inverse[0],inverse[1] = 0,1
for i in range(2,N+1):
    g1[i] = (g1[i-1] * i) % mod
    inverse[i] = (-inverse[mod % i] * (mod//i)) % mod
    g2[i] = (g2[i-1] * inverse[i]) % mod

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


dp = [0]*(n+1)

for i in range(n+1):
    dp[i] = cmb(n-1,i) * cmb(n,i) % mod

if k == 1:
    ans = dp[1]
else:
    k = min(n,k)
    ans = 0
    for i in range(k+1):
        ans += dp[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
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())


M = min(N - 1, K)

"""
m = 0,1,2,...,M

N部屋から、空き部屋をm個選ぶ
-> N_C_m

残りの(N-m)部屋に、N人を配置する（空き部屋が出来てはいけない）
まず、(N-m)部屋に1人ずつ配置し、残ったm人を(N-m)部屋に配置する
これは、m個のボールと(N-m-1)本の仕切りの並び替えに相当する
-> (m+N-m-1)_C_m = N-1_C_m
"""

ans = 0
for m in range(0, M + 1):
    ans += cmb(N, m, mod) * cmb(N - 1, m, mod)
    ans %= mod

print(ans)

Solution (Python):





def inverse(a, p):
    """逆元"""
    a_, p_ = a, p
    x, y = 1, 0
    while p_:
        t = a_ // p_
        a_ -= t * p_
        a_, p_ = p_, a_
        x -= t * y
        x, y = y, x
    x %= p
    return x






def solve(n, k):
    mod = 10 ** 9 + 7
    ans = 0
    p_mod = [1, 1]
    for i in range(2, n + 1):
        p_mod.append((p_mod[-1] * i) % mod)

    for i in range(min(n, k + 1)):
        if i == 0:
            ans += 1
        elif i == 1:
            ans += n * (n - 1)
        else:
            nCi = p_mod[n] * inverse(p_mod[n - i], mod) % mod * inverse(p_mod[i], mod) % mod
            nmHi = (p_mod[n - 1] * inverse(p_mod[n - i - 1], mod) % mod) * inverse(p_mod[i], mod) % mod
            
            ans += nCi * nmHi % mod
        ans %= mod
    print(ans)


if __name__ == '__main__':
    
    
    n, k = map(int, input().split())
    
    
    
    solve(n, k)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
import bisect
from functools import reduce
def main():
    def comb(n, r):
        numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
        denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
        return numerator * pow(denominator, mod - 2, mod) % mod
    mod = 10 ** 9 + 7
    N, K = MI()
    if K >= N - 1:
        ans = comb(2 * N - 1, N - 1)
        print(ans)
    else:
        N_r = pow(N, mod - 2, mod)
        ans = N * (N - 1) % mod
        add = N * (N - 1) % mod
        for i in range(2, K + 1):
            a = (N - i + 1) % mod
            b = (a - 1) % mod
            c = pow(i, mod - 2, mod)
            d = pow(c, 2, mod)
            add = ((((add * a) % mod * b) % mod) * d) % mod
            ans += add
            ans %= mod
        if K >= 2:
            ans += 1
            ans %= mod
        print(ans)

if __name__ == "__main__":
    main()

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

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

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

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

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

    def combination_large(self, k, r):
        """kCrを求める O(r) kが大きいが、r <= nを満たしているときに使用"""
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.mod
        return (res * self.inv_fact[r]) % self.mod

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

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

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys


readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Combination:
    def __init__(self, n, mod):

        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)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

    def __call__(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n-r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.MOD


@mt
def slv(N, K):
    ans = 0
    M = 10**9 + 7

    C = Combination(N*2+1, M)
    def H(n, r):
        return C(n+r-1, r)

    K = min(N-1, K)
    for k in range(K+1):
        m = N - k
        t = C(N, k) * H(m, k)
        ans += t
        ans %= M

    return ans


def main():
    N, K = read_int_n()
    print(slv(N, K))


if __name__ == '__main__':
    main()

Solution (Python):
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]
 
gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]
 
def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

def nPr(n,r):
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

N,K = map(int,input().split())
if K >= N:
    M = N
else:
    M = K

ans = 0
for i in range(1,M+1):
    ans += nCr(N,i) * nCr(N-1,i)
    ans %= MOD
print(ans+1)

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

frac=[1]
for i in range(1,max_n+1):
  frac.append((frac[-1]*i)%mod)

inv=[1,1]
inv_frac=[1,1]
for i in range(2,max_n):
  inv.append((mod-inv[mod%i]*(mod//i))%mod)
  inv_frac.append((inv_frac[-1]*inv[-1])%mod)
  
def perm(m,n):
  if m<n:
    return 0
  if m==1:
    return 1
  return (frac[m]*inv_frac[m-n])%mod

def comb(m,n):
  if m<n:
    return 0
  if m==1:
    return 1
  return (frac[m]*inv_frac[n]*inv_frac[m-n])%mod  

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6
mod = 10 ** 9 + 7 

from decimal import *



		

lim = 4*10**5   
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod


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

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod

n, k = MAP()

if n-1 <= k:
	print(C(2*n-1, n))
	exit()

ans = 0
for i in range(k+1):
	ans += C(n, i) * C(n-1, i) % mod
	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**6
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 )
a,b=map(int,input().split())
mod=(10**9)+7
if b>=a-1:
  print(cmb((2*a)-1, a,mod))
else:
  ans=0
  for i in range(1,b+1):
    ans+=cmb(a, i,mod)*cmb(a-1, a-i-1,mod)
  if b!=1:
    ans+=1
  print(ans%mod)

Solution (Python):
import sys

n, k = map(int, input().split())
P = int(1e9+7)


def cmb(n, r, P):
    r = min(r, n - r)
    inv_y = 1
    for i in range(1, r + 1):
        inv_y = (inv_y * i) % P
    inv_y = pow(inv_y, P - 2, P)
    x = 1
    for i in range(n - r + 1, n + 1):
        x = x * i % P
    return (x * inv_y) % P


if k >= n:
    print(cmb(2*n-1, n, P))
    sys.exit()
if k == 1:
    print((n * n - 1) % P)
    sys.exit()
ans = 1
comb1 = 1
comb2 = 1
for i in range(1, k + 1):
    iinv = pow(i, P-2, P)
    comb1 = ((comb1 * (n - i)) * (iinv)) % P
    comb2 = ((comb2 * (n - i + 1)) * (iinv)) % P
    ans = (ans + comb1*comb2) % P
print(ans)

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

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

if n-1 <= k:
    print((fact[2*n-1] * finv[n] * finv[n-1]) % mod)
    exit()

ans = 0
for i in range(k+1):
    ans += fact[n] * finv[n-i] * finv[i] * fact[n-1] * finv[n-1-i] * finv[i]
    ans %= mod

print(ans)

Solution (Python):
"""
一回の移動で移動する人間は一人なのか？＝＞質問みたらYESだった。

n=2の場合を除いて、
人がいる部屋の数はmax(n-k,1)以上となる。
人がいる部屋の数が1つの場合、2つの場合、、、と順番に場合の数を数えていく。
人がいる部屋の数がxの場合の場合の数の求め方：まず、n部屋の中から、x部屋を選ぶ場合の数でnCx。各部屋に一人は人がいるので、nからxを控除する。残りのn-xをx部屋でどう分けるかを考えればよい。
これは、重複組み合わせの公式で(n-x+x-1)C(x-1)。上記の二つをかけ合わせればよい。
あと、制約から考えて、combination関数は高速化が必要。
"""
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)




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

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

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


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


COMinit()
ans = 0
for i in range(min(n, k)+1):
  tmp = COM(n, i) % Mod
  tmp *= COM(i+n-i-1, i)
  tmp %= Mod
  ans += tmp
  ans %= Mod
print(ans)

Solution (Python):
N, K = list(map(int, input().split()))
p = 10**9+7
size = 2*2*10**5

def binom(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

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

res = 0

for i in range(min(K, N)+1):
        res += (binom(N, i, p) * binom(N-1, N-i-1, p)) % p

print(res % p)

Solution (Python):
class mod_comb_k():
  def __init__(self, MAX_N = 10**6, mod = 10**9+7):
    self.fact = [1]
    self.fact_inv = [0] * (MAX_N + 4)
    self.mod = mod
    for i in range(MAX_N + 3):
      self.fact.append(self.fact[-1] * (i + 1) % self.mod)
    self.fact_inv[-1] = pow(self.fact[-1], self.mod - 2, self.mod)
    for i in range(MAX_N + 2, -1, -1):
      self.fact_inv[i] = self.fact_inv[i + 1] * (i + 1) % self.mod
  def comb(self, n, k):
    if n < k:return 0
    else:return self.fact[n] * self.fact_inv[k] % self.mod * self.fact_inv[n - k] % self.mod
c=mod_comb_k()
n,k=map(int,input().split())
if k>=n:print(c.comb(2*n-1,n))
else:
  ans=0
  m=10**9+7
  for i in range(k+1):
    ans+=c.comb(n-1,i)*c.comb(n,i)%m
    ans%=m
  print(ans)

Solution (Python):
n,k = list(map(int, input().split()))
mod = int(1e9+7)



def init_cmb(Nmax):
    
    g1 = [1, 1] 
    g2 = [1, 1] 
    inverse = [0, 1] 

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

g1,g2 = init_cmb(n+10)

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



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

Solution (Python):
def build_combinations_counter(N=10**5, p=10**9+7):
    fact = [1, 1]  
    factinv = [1, 1]  
    inv = [0, 1]  
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % p)
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)
    
    def cmb(n, r, p, fact, factinv):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return fact[n] * factinv[r] * factinv[n-r] % p
    
    import functools
    return functools.partial(cmb, p=p, fact=fact, factinv=factinv)

def resolve():
    n, k = list(map(int, input().split()))
    MOD = 10**9+7
    counter = build_combinations_counter(2*10**5, 10**9+7)
    ans = 0
    for i in range(min(n, k+1)):
        ans += counter(n, i) * counter(n-1, n-i-1)
        ans %= MOD
    print(ans)
    
    
if __name__ == "__main__":
    resolve()

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

Solution (Python):
def prepare(n, MOD):
 
    
    f = 1
    factorials = [1]  
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    
    inv = pow(f, MOD - 2, MOD)
    
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs

MOD = 10**9+7
fact, fact_inv = prepare(3*10**5, MOD)

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

k = min(n-1, k)

ans = 1
for i in range(1,k+1):
    z = fact[n] * fact_inv[i] % MOD * fact_inv[n-i] % MOD
    p = fact[n-1] * fact_inv[n-i-1] % MOD * fact_inv[i] % MOD
    ans += z * p % MOD
    ans %= MOD
print(ans)

Solution (Python):
class Combination:
    def __init__(self, n_max, mod=10**9+7):
        
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    
    

    def __call__(self, n, r):  
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

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

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

    def H(self, n, r):
        if (n == 0 and r > 0) or r < 0: return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod

    def rising_factorial(self, n, r):  
        return self.fac[n+r-1] * self.facinv[n-1] % self.mod

    def stirling_first(self, n, k):  
        if n == k: return 1
        if k == 0: return 0
        return (self.stirling_first(n-1, k-1) + (n-1)*self.stirling_first(n-1, k)) % self.mod

    def stirling_second(self, n, k):  
        if n == k: return 1  
        return self.facinv[k] * sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def balls_and_boxes_3(self, n, k):  
        return sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def bernoulli(self, n):  
        if n == 0: return 1
        if n % 2 and n >= 3: return 0  
        return (- pow(n+1, self.mod-2, self.mod) * sum(self.C(n+1, k) * self.bernoulli(k) % self.mod for k in range(n))) % self.mod

    def faulhaber(self, k, n):  
        
        return pow(k+1, self.mod-2, self.mod) * sum(self.C(k+1, j) * self.bernoulli(j) % self.mod * pow(n, k-j+1, self.mod) % self.mod for j in range(k+1)) % self.mod

    def lah(self, n, k):  
        return self.C(n-1, k-1) * self.fac[n] % self.mod * self.facinv[k] % self.mod

    def bell(self, n, k):  
        return sum(self.stirling_second(n, j) for j in range(1, k+1)) % self.mod


def main():
    N, K = map(int, input().split())
    mod = 10**9+7
    sign = 1
    L = []
    comb = Combination(202020)
    ans = 0
    for n_zeroes in range(min(K+1, N)):
        a = comb.C(N, n_zeroes) * comb.H(N-n_zeroes, n_zeroes) % mod
        ans += a
    print(ans % mod)

main()

Solution (Python):
import sys

N_MAX = 200000 + 5
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7



fac = [1, 1]  
facinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N_MAX + 1):
    fac.append((fac[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    facinv.append((facinv[-1] * inv[-1]) % MOD)


def cmb(n, r):
    if (r < 0 or r > n):
        return 0
    
    return fac[n] * facinv[r] * facinv[n - r] % MOD


def main():
    n, k = map(int, sys.stdin.readline().rstrip().split())

    k = min(n, k)

    ans = 0
    for m in range(k+1):
        empty = cmb(n, m)
        member = cmb(n - 1, n - m - 1)
        ans += (empty * member) % MOD
        ans %= MOD

    print(ans)


main()

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


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

for i in range(2, 2*n):
  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

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

Solution (Python):
def factorial(n, mod):
    fac = [0] * (n + 1)
    inv = [0] * (n + 1)
    fac[0], inv[0] = 1, 1
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % mod
        inv[i] = inverse(fac[i], mod)
    return fac, inv

def inverse(a, mod):
    a %= mod
    p = mod
    x, y = 0, 1
    while a > 0:
        n = p // a
        p, a = a, p % a, 
        x, y = y, x - n * y
    return x % mod

n, k = map(int, input().split())
mod = 10 ** 9 + 7
fac, inv = factorial(n, mod)

if k == 1:
    print(n * (n - 1) // 2 % mod)
    quit()

if k >= n:
    k = n - 1
ans = 0
for i in range(0, k + 1):
    nci = fac[n] * inv[n-i] % mod * inv[i] % mod
    mci = fac[n-1] * inv[n-1-i] % mod * inv[i] % mod
    ans = (ans + nci * mci % mod) % mod
print(ans)

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


def prepare(n, MOD):
    
    f = 1
    factorials = [1]  
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    
    inv = pow(f, MOD - 2, MOD)
    
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


def comb(n, r, factorials, invs):
    return factorials[n] * invs[r] * invs[n - r] % MOD


def main():
    n, k = map(int, input().split())
    factorials, invs = prepare(n, MOD)
    ans = 0
    for m in range(min(k, n - 1) + 1):
        ans += comb(n - 1, m, factorials, invs) * comb(n, m, factorials, invs)
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()