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):
N, K = map(int, input().split())

MAX = 4 * 10 ** 5 + 1
MOD = 10 ** 9 + 7


fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1


inv = [0] * (MAX + 1)
inv[1] = 1


finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1

for i in range(2, MAX + 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 comb(n, k):
    if n < k or k < 0:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % MOD


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

Solution (Python):

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

MAX = 4 * 10 ** 5 + 1
MOD = 10 ** 9 + 7


fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1


inv = [0] * (MAX + 1)
inv[1] = 1


finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1

for i in range(2, MAX + 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 comb(n, k):
    if n < k or k < 0:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % MOD


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

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


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


mod = 10**9+7  
N = 2*10**5+1
g1 = [1, 1]  
g2 = [1, 1]  
inverse = [0, 1]  

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


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

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy


import heapq

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


m = 4*10**5
mod = 10**9 + 7


fact = [0]*(m+5)
fact_inv = [0]*(m+5)
inv = [0]*(m+5)

fact[0] = fact[1] = 1
fact_inv[0] = fact_inv[1] = 1
inv[1] = 1

for i in range(2,m+5):
    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



def cmb(n,k,mod):
    return fact[n] * (fact_inv[k] * fact_inv[n-k] % mod) % mod

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


class CmbMod:
    def __init__(self, n, p):
        """
        二項係数nCr(n個の区別できるものからr個のものを選ぶ組み合わせの数)をpで割った余りを求める
        """
        self.n = n
        self.p = p
        self.fact = [1, 1]
        self.factinv = [1, 1]
        self.inv = [0, 1]

    def cmb_mod(self, n, r):
        """
        二項係数nCr(mod p)をO(r)にて計算。nが大きいがrは小さい時に使用。
        """
        numer, denom = 1, 1
        for i in range(r):
            numer = (numer * (n - i)) % self.p
            denom = (denom * (i + 1)) % self.p
        return (numer * pow(denom, self.p - 2, self.p)) % self.p

    def prep(self):
        """
        二項係数nCr(mod p)をO(1)で求める為の前処理をO(N)にて実行。
        """
        for i in range(2, self.n + 1):
            self.fact.append((self.fact[-1] * i) % self.p)
            self.inv.append((-self.inv[self.p % i] * (self.p // i)) % self.p)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % self.p)

    def cmb_mod_with_prep(self, n, r):
        """
        二項係数nCr(mod p)をO(1)で求める。事前にprepを実行する事。
        """
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] * self.factinv[n - r] % self.p


def resolve():
    n, k = map(int, input().split())
    k = min(n - 1, k)
    cmb = CmbMod(n, mod)
    cmb.prep()
    res = 0
    for i in range(k + 1):
        res += (cmb.cmb_mod_with_prep(n, i) * cmb.cmb_mod_with_prep(n - 1, i)) % mod
        res %= mod
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
n, k = map(int, input().split())
mod = pow(10, 9) + 7
c1, c2 = 1, 1
n1, n2 = n, n - 1
ans = 1
for r in range(1, min(k + 1, n)):
    c1 = (c1 * n1 * pow(r, mod - 2, mod)) % mod
    c2 = (c2 * n2 * pow(r, mod - 2, mod)) % mod
    n1 -= 1
    n2 -= 1
    ans += (c1 * c2) % mod
    ans %= mod
print(ans)

Solution (Python):
n, k = map(int, input().split())
mod = pow(10, 9) + 7
c1, c2 = 1, 1
n1, n2 = n, n - 1
ans = 1
for r in range(1, min(k + 1, n)):
    c1 = (c1 * n1 * pow(r, mod - 2, mod)) % mod
    c2 = (c2 * n2 * pow(r, mod - 2, mod)) % mod
    n1 -= 1
    n2 -= 1
    ans += (c1 * c2) % mod
    ans %= mod
print(ans)

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

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

def getFacts(n, MOD):
    facts = [1] * (n+1)
    for x in range(2, n+1):
        facts[x] = (facts[x-1] * x) % MOD
    return facts
facts = getFacts(2*N, MOD)
def getInvFacts(n, MOD):
    invFacts = [0] * (n+1)
    invFacts[n] = pow(facts[n], MOD-2, MOD)
    for x in reversed(range(n)):
        invFacts[x] = (invFacts[x+1] * (x+1)) % MOD
    return invFacts
invFacts = getInvFacts(2*N, MOD)
def getComb(n, k, MOD):
    if n < k:
        return 0
    return facts[n] * invFacts[k] * invFacts[n-k] % MOD

ans = 0
for x in range(min(K, N-1)+1):
    ans += getComb(N, x, MOD) * getComb(N-1, x, MOD)
    ans %= MOD

print(ans)

Solution (Python):
mod = int(1e9) + 7 
maxf = 500000           

def make_fact(n, k):
    tmp = n
    perm = [i for i in range(k)]
    L = [0 for _ in range(k)]
    for i in range(k):
        L[i] = tmp % (i + 1)
        tmp //= i + 1
    LL = [0 for _ in range(k)]
    for i in range(k):
        LL[i] = perm[L[-i-1]]
        for j in range(L[-i-1]+1, k):
            perm[j-1] = perm[j]
    return LL

def doubling(n, m, modulo=mod):
    y = 1
    base = n
    tmp = m
    while tmp != 0:
        if tmp % 2 == 1:
            y *= base
            if modulo > 0:
                y %= modulo
        base *= base
        if modulo > 0:
            base %= modulo
        tmp //= 2
    return y

def inved(a, modulo=mod):
    x, y, u, v, k, l = 1, 0, 0, 1, a, modulo
    while l != 0:
        x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
        k, l = l, k % l
    return x % modulo

fact = [1 for _ in range(maxf+1)]
invf = [1 for _ in range(maxf+1)]

for i in range(maxf):
    fact[i+1] = (fact[i] * (i+1)) % mod
invf[-1] = inved(fact[-1])
for i in range(maxf, 0, -1):
    invf[i-1] = (invf[i] * i) % mod
n, k = map(int, input().split())
S = 0
if n <= k + 1:
    print(fact[2*n-1]*invf[n]*invf[n-1]%mod)
else:
    S = 0
    for i in range(min(n, k+1)):
        S += invf[i]*invf[i]*invf[n-i-1]*invf[n-i]%mod
        S %= mod
    print(S*fact[n-1]*fact[n]%mod)

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

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

if k >=n:
  L = 2*n-1
  ansbunsi =1
  for j in range(n-1):
    ansbunsi = ansbunsi*L%mod
    L -= 1
  ansbunbo = 1
  L = n - 1
  for j in range(n-1):
    ansbunbo = ansbunbo*L%mod
    L -= 1
  ansbunbo = modinv(ansbunbo)
  print(ansbunsi*ansbunbo%mod)

else:
  kaijou = [1, 1]
  for j in range(2, n):
    kaijou.append(kaijou[-1]*j%mod)
  
  ans = 0

  for m in range(k+1):
    ansbunsi = (kaijou[n-1]**2)*n%mod
    ansbunbo = kaijou[n-m-1]*kaijou[m]%mod
    ansbunbo = ansbunbo*ansbunbo%mod*(n-m)%mod
    ansbunbo = modinv(ansbunbo)
    ans += ansbunbo*ansbunsi%mod
    ans %= mod
  
  print(ans)

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

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

if k >=n:
  L = 2*n-1
  ansbunsi =1
  for j in range(n-1):
    ansbunsi = ansbunsi*L%mod
    L -= 1
  ansbunbo = 1
  L = n - 1
  for j in range(n-1):
    ansbunbo = ansbunbo*L%mod
    L -= 1
  ansbunbo = modinv(ansbunbo)
  print(ansbunsi*ansbunbo%mod)

else:
  kaijou = [1, 1]
  for j in range(2, n):
    kaijou.append(kaijou[-1]*j%mod)
  
  ans = 0

  for m in range(k+1):
    ansbunsi = (kaijou[n-1]**2)*n%mod
    ansbunbo = kaijou[n-m-1]*kaijou[m]%mod
    ansbunbo = ansbunbo*ansbunbo%mod*(n-m)%mod
    ansbunbo = modinv(ansbunbo)
    ans += ansbunbo*ansbunsi%mod
    ans %= mod
  
  print(ans)

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

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

if k >=n:
  L = 2*n-1
  ansbunsi =1
  for j in range(n-1):
    ansbunsi = ansbunsi*L%mod
    L -= 1
  ansbunbo = 1
  L = n - 1
  for j in range(n-1):
    ansbunbo = ansbunbo*L%mod
    L -= 1
  ansbunbo = modinv(ansbunbo)
  print(ansbunsi*ansbunbo%mod)

else:
  kaijou = [1, 1]
  for j in range(2, n+1):
    kaijou.append(kaijou[-1]*j%mod)
  
  ans = 0

  for m in range(k+1):
    ansbunsi = kaijou[n]*kaijou[n-1]%mod
    ansbunbo = kaijou[m]*kaijou[n-m]%mod
    ansbunbo = ansbunbo*kaijou[n-m-1]%mod
    ansbunbo = ansbunbo*kaijou[m]%mod
    ansbunbo = modinv(ansbunbo)
    ans += ansbunbo*ansbunsi
    ans %= mod
  
  print(ans)

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

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

if k >=n:
  L = 2*n-1
  ansbunsi =1
  for j in range(n-1):
    ansbunsi = ansbunsi*L%mod
    L -= 1
  ansbunbo = 1
  L = n - 1
  for j in range(n-1):
    ansbunbo = ansbunbo*L%mod
    L -= 1
  ansbunbo = modinv(ansbunbo)
  print(ansbunsi*ansbunbo%mod)

else:
  kaijou = [1, 1]
  for j in range(2, k+n+1):
    kaijou.append(kaijou[-1]*j%mod)
  
  ans = 0

  for m in range(k+1):
    ansbunsi = kaijou[n]*kaijou[n-1]%mod
    ansbunbo = kaijou[m]*kaijou[n-m]%mod
    ansbunbo = ansbunbo*kaijou[n-m-1]%mod
    ansbunbo = ansbunbo*kaijou[m]%mod
    ansbunbo = modinv(ansbunbo)
    ans += ansbunbo*ansbunsi
    ans %= mod
  
  print(ans)

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
factmod=[1 for i in range(n+1)]
for i in range(n):
    factmod[i+1]=(factmod[i]*(i+1))%mod

ans=0
for m in range(min(k+1,n)):
    a=factmod[-1]*pow((factmod[m]*factmod[n-m])%mod,mod-2,mod)
    b=factmod[n-1]*pow((factmod[m]*factmod[n-m-1])%mod,mod-2,mod)
    ans=(ans+(a*b))%mod
print(ans%mod)

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

mod = 10**9+7 
N = 2*(10**5)+1
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())
c=min(a,b)
s=0
for i in range(0,c+1):
    s+=cmb(a,i,10**9+7)*cmb(a-1,i,10**9+7)
print(s%(10**9+7))

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

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

g1=[1,1]
g2=[1,1]
inv=[0,1]
for i in range(2,1000003):
  g1.append((g1[-1]*i)%mod)
  inv.append((-inv[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inv[-1])%mod)
P=0
for i in range(min(N,K+1)):
  P=(P+cmb(N,i)*cmb(N-1,i))%mod
print(P)

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

mod = 10 ** 9 + 7
fact = [1] * (n + 1)
ifact = [1] * (n + 1)

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


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


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

Solution (Python):
def ext_euc(a, b):
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euc(a, mod)
    return x % mod


def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split()))
    c = [1, 1]  
    ans = 0
    for n in range(min(N - 1, K) + 1):
        ans += c[0] * c[1]
        ans %= MOD
        n_inv = mod_inv(n + 1, MOD)
        c[0] *= N - n
        c[0] *= n_inv
        c[0] %= MOD
        c[1] *= N - 1 - n
        c[1] *= n_inv
        c[1] %= MOD
    print(ans)


if __name__ == '__main__':
    main()

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

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):  
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * 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


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

k = min(k,n-1)
res = 0
for l in range(k+1):
    res += C(n,l)*C.H(n-l,l)
print(res%MOD)

Solution (Python):
MOD = 10**9 + 7
N = 10**6  
factorial_mod = [1, 1]  
modular_multiplicative_inverse = [0, 1]  
factorial_inverse_mod = [1, 1]  
 
for i in range(2, N + 1):  
    factorial_mod.append((factorial_mod[i - 1] * i) % MOD)
    modular_multiplicative_inverse.append((-modular_multiplicative_inverse[MOD % i] * (MOD // i)) % MOD)
    factorial_inverse_mod.append((factorial_inverse_mod[i-1] * modular_multiplicative_inverse[i]) % MOD)
 
def nCr_mod(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return factorial_mod[n] * factorial_inverse_mod[r] * factorial_inverse_mod[n - r] % MOD


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

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

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 = mod
N = 4 * 10 ** 6 + 10 
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 shikiri(a,b):
    return fact[a+b]*factinv[a]*factinv[b]%mod

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

if m==1:
    ans-=1
print(ans)

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


def read():
    N, K = list(map(int, input().strip().split()))
    return N, K


def binom_preprocess(n, MOD=10**9+7):
    f = [0 for i in range(n+1)]  
    invf = [0 for i in range(n+1)]  
    f[0] = 1
    f[1] = 1
    invf[0] = 1
    invf[1] = 1
    for i in range(2, n+1):
        f[i] = f[i-1] * i % MOD
    invf[n] = pow(f[n], MOD-2, MOD)
    for i in range(n, 2, -1):
        invf[i-1] = invf[i] * i % MOD
    return f, invf


def binom(n, k, f, invf, MOD=10**9+7):
    if n < k or n < 0 or k < 0:
        return 0
    else:
        return (f[n] * invf[k] % MOD) * invf[n-k] % MOD


def solve(N, K, MOD=10**9+7):
    
    
    f, invf = binom_preprocess(N, MOD)
    ans = 0
    for k in range(0, min(N, K+1)):
        ans += binom(N, k, f, invf, MOD) * binom(N-1, k, f, invf, MOD)
        ans %= MOD
    return ans


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Solution (Python):
class Combination:
  def __init__(self, n_max, mod=10**9+7):
    self.mod = mod
    self.modinv = self.make_modinv_list(n_max)
    self.fac, self.facinv = self.make_factorial_list(n_max)

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

  def make_factorial_list(self, n):
    
    
    fac = [1]
    facinv = [1]
    for i in range(1, n+1):
      fac.append(fac[i-1] * i % self.mod)
      facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
    return fac, facinv

  def make_modinv_list(self, n):
    
    modinv = [0] * (n+1)
    modinv[1] = 1
    for i in range(2, n+1):
      modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
    return modinv

n,k = map(int,input().split())
ans = 1
MOD = 10**9+7
comb = Combination(2*10**5+1)
for i in range(1, min(n, k+1)):
  ans += (comb(n,i)*comb(n-1, i))%MOD
  ans %= MOD

print(ans)

Solution (Python):

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

MAX = 6 * 10 ** 5 + 1
MOD = 10 ** 9 + 7


fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1


inv = [0] * (MAX + 1)
inv[1] = 1


finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1

for i in range(2, MAX + 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 comb(n, k):
    if n < k or k < 0:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % MOD


def comb_rep(n, k):
    return comb(n + k - 1, n - 1)


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

Solution (Python):

N_MAX = 10**6
MOD = 10**9 + 7
fac, finv, inv = [0]*N_MAX ,[0]*N_MAX, [0]*N_MAX
def com_init():
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, N_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, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

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

Solution (Python):

class Combination:
    def __init__(self,N,P=10**9+7):
        if N > 10**7:
            self.fact = lambda x: x * self.fact(x-1) % P if x > 2 else 2
            self.perm = lambda x, r: x * self.perm(x-1,r-1) % P if r > 0 else 1
            self.cmb = lambda n,r: (self.perm(n,min(n-r,r)) * pow(self.fact(min(n-r,r)) ,P-2 ,P) % P) if r > 0 else 1
        else:
            self.__fact = [1] * (N+1)
            self.__inv = [1] * (N+1)
            self.__inv_fact = [1] * (N+1)
            for i in range(2,N+1):
                self.__fact[i] = self.__fact[i-1] * i % P
                self.__inv[i] = - self.__inv[P%i] * (P//i) % P
                self.__inv_fact[i] = self.__inv_fact[i-1] * self.__inv[i] % P
            self.fact = lambda n: self.__fact[n]
            self.perm = lambda n,r: self.__fact[n] * self.__inv_fact[n-r] % P
            self.cmb = lambda n,r: (self.__fact[n] * self.__inv_fact[n-r] * self.__inv_fact[r] % P) if r > 0 else 1






import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    from collections import deque
    
    n,k = LMIIS()
    cmb = Combination(2*n)
    ans = 1
    for i in range(1,min(n,k+1)):
        ans = (ans + cmb.cmb(n,i) * cmb.cmb(n-1,i)) % MOD
    print(ans)

    
if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10**9 + 7
N = 10**6  
factorial_mod = [1, 1]  
modular_multiplicative_inverse = [0, 1]  
factorial_inverse_mod = [1, 1]  

for i in range(2, N + 1):  
    factorial_mod.append((factorial_mod[i - 1] * i) % MOD)
    modular_multiplicative_inverse.append((-modular_multiplicative_inverse[MOD % i] * (MOD // i)) % MOD)
    factorial_inverse_mod.append((factorial_inverse_mod[i-1] * modular_multiplicative_inverse[i]) % MOD)

def nCr_mod(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return factorial_mod[n] * factorial_inverse_mod[r] * factorial_inverse_mod[n - r] % MOD

def nPr_mod(n, r):
    return factorial_mod[n] * factorial_inverse_mod[n - r] % MOD



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

Solution (Python):
import sys
from io import StringIO
import unittest
import os


sys.setrecursionlimit(999999999)


def prepare(n, mod=pow(10, 9) + 7):
    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 resolve(test_def_name=""):
    n, k = map(int, input().split())

    
    fns, invs = prepare(pow(10, 6))

    
    ans = 0
    for i in range(1, min(n - 1, k) + 1):
        
        
        ans += (fns[n] * invs[i] * invs[n - i]) * (fns[n - 1] * invs[i] * invs[n - 1 - i]) % (pow(10, 9) + 7)
        ans = ans % (pow(10, 9) + 7)

    
    print(ans + 1)



class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 2"""
        output = """10"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """200000 1000000000"""
        output = """607923868"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """15 6"""
        output = """22583772"""
        self.assertIO(test_input, output)

    
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
class Factorial:
    def __init__(self, max_fact, mod):
        
        
        f = [1] * (max_fact + 1)
        for idx in range(2, max_fact + 1):
            f[idx] = f[idx - 1] * idx
            f[idx] %= mod
        if mod > max_fact:
            fi = [pow(f[-1], mod - 2, mod)]
            for idx in range(max_fact, 0, -1):
                fi += [fi[-1] * idx % mod]
            fi = fi[::-1]
        else:
            fi = [pow(n, mod - 2, mod) for n in f]
        self.mod = mod
        self.f = f
        self.fi = fi

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

    def factorial_inverse(self, n):
        return self.fi[n]

    def combination(self, n, r):
        f = self.f
        fi = self.fi
        return f[n] * fi[r] * fi[n - r] % self.mod

    def permutation(self, n, r):
        return self.f[n] * self.fi[n - r] % self.mod

    def homogeneous_product(self, n, r):
        f = self.f
        fi = self.fi
        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod


max_fact = 4 * 10**5 + 100
mod = 10**9 + 7
fact_instance = Factorial(max_fact, mod)
comb_repl = fact_instance.homogeneous_product
comb = fact_instance.combination

N, K = [int(_) for _ in input().split()]
ans = 0
for r in range(min(N - 1, K) + 1):
    ans += comb(N, r) * comb_repl(N - r, r)
    ans %= mod
print(ans)

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter



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

Mod=10**9+7
M=2*10**5 +1

fac=[0]*M
finv=[0]*M
inv=[0]*M


def COMinit():
  fac[0]=fac[1]=1
  finv[0]=finv[1]=1
  inv[1]=1
  for i in range(2,M):
    fac[i]=(fac[i-1]*i%Mod)%Mod
    inv[i]=Mod-inv[Mod%i]*(Mod//i) %Mod
    finv[i]=(finv[i-1]*inv[i]%Mod)%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)%Mod

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

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


def solve():
    N, K = Scanner.map_int()

    MOD = int(1e09) + 7
    MAX = 200010
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    fac[0] = fac[1] = finv[0] = finv[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 cmb(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

    ans = 0
    for m in range(0, min(K, N - 1) + 1):
        a = cmb(N, m)
        b = cmb(N - 1, m)
        ans += a * b
        ans %= MOD
    print(ans)


def main():
    
    
    
    
    
    
    solve()


if __name__ == "__main__":
    main()

Solution (Python):
N, K = [int(_) for _ in input().split()]
MOD = 10 ** 9 + 7

ans = 0


class ModFactorial:
    """
    階乗, 組み合わせ, 順列の計算
    """

    def __init__(self, n, MOD=10 ** 9 + 7):
        """

        :param n: 最大の要素数.
        :param MOD:
        """
        kaijo = [0] * (n + 10)
        gyaku = [0] * (n + 10)

        kaijo[0] = 1
        kaijo[1] = 1
        for i in range(2, len(kaijo)):
            kaijo[i] = (i * kaijo[i - 1]) % MOD
        gyaku[0] = 1
        gyaku[1] = 1
        for i in range(2, len(gyaku)):
            gyaku[i] = pow(kaijo[i], MOD - 2, MOD)
        self.kaijo = kaijo
        self.gyaku = gyaku
        self.MOD = MOD

    def nCm(self, n, m):
        return (self.kaijo[n] * self.gyaku[n - m] * self.gyaku[m]) % self.MOD

    def nPm(self, n, m):
        return (self.kaijo[n] * self.gyaku[n - m]) % self.MOD

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


mf = ModFactorial(N, MOD)
for i in range(1, N + 1):
    if N - i > K: continue

    p = N - i
    
    ans += mf.nCm(p + i - 1, i - 1) * mf.nCm(N, i)
    ans %= MOD
print(ans)

Solution (Python):
N, K = map(int, input().split())
MOD = 10**9 + 7
MAX_N = 10**6 + 5
fact = [0]*(MAX_N)
fact_inv = [0]*(MAX_N)
fact[0] = 1
for i in range(MAX_N-1):
    fact[i+1] = fact[i]*(i+1) % MOD
fact_inv[-1] = pow(fact[-1], MOD-2, MOD)
for i in range(MAX_N-2, -1, -1):
    fact_inv[i] = fact_inv[i+1]*(i+1) % MOD


def comb(n, k):
    return fact[n]*fact_inv[k] % MOD * fact_inv[n-k] % MOD


if K >= N:
    print(comb(2*N-1, N-1))
    exit()

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