Problem:
 Score : 500 points    Problem Statement There is a building with n rooms, numbered 1 to n .  We can move from any room to any other room in the building.  Let us call the following event a move : a person in some room i goes to another room j~ (i \neq j) .  Initially, there was one person in each room in the building.  After that, we know that there were exactly k moves happened up to now.  We are interested in the number of people in each of the n rooms now. How many combinations of numbers of people in the n rooms are possible?  Find the count modulo (10^9 + 7) .      Constraints  All values in input are integers.  3 \leq n \leq 2 \times 10^5  2 \leq k \leq 10^9         Input Input is given from Standard Input in the following format:  n  k       Output Print the number of possible combinations of numbers of people in the n rooms now, modulo (10^9 + 7) .        Sample Input 1 3 2      Sample Output 1 10  Let c_1 , c_2 , and c_3 be the number of people in Room 1 , 2 , and 3 now, respectively. There are 10 possible combination of (c_1, c_2, c_3) :   (0, 0, 3)  (0, 1, 2)  (0, 2, 1)  (0, 3, 0)  (1, 0, 2)  (1, 1, 1)  (1, 2, 0)  (2, 0, 1)  (2, 1, 0)  (3, 0, 0)   For example, (c_1, c_2, c_3) will be (0, 1, 2) if the person in Room 1 goes to Room 2 and then one of the persons in Room 2 goes to Room 3 .       Sample Input 2 200000 1000000000      Sample Output 2 607923868  Print the count modulo (10^9 + 7) .       Sample Input 3 15 6      Sample Output 3 22583772

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import log10, ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k = MAP()

lim = 10**6  
factorial = [1]
for i in range(1, lim):
    factorial.append(factorial[i-1] * i % mod)

def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, int(y/2)) ** 2 % mod
    else:
        return power(x, int((y-1)/2)) ** 2 * x % mod

def C(n, r):
    return (((factorial[n] * x_inv[r]) % mod) * x_inv[n-r]) % mod
x_inv = [0] * lim
x_inv[-1] = power(factorial[-1], mod-2)
for i in range(lim-2, -1, -1):
    x_inv[i] = x_inv[i+1] * (i+1) % mod

if k >= n-1:
	k = n-1
ans = 0
for m in range(k+1):
	ans = (ans+C(n, m)*C(n-1, m))%mod
print(ans)

Solution (Python):
import sys
import itertools

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


class Comb(object):

    def __init__(self, n, MOD=1e9 + 7):
        self.MOD = MOD

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

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

        for i in range(2, n + 10):
            fac[i] = fac[i - 1] * i % MOD
            inv[i] = MOD - inv[int(MOD % i)] * (MOD // i) % MOD
            finv[i] = finv[i - 1] * inv[i] % MOD
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def calc_c(self, n, k):
        if n < k:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] %
                              self.MOD) % self.MOD

    def calc_h(self, n, k):
        return self.calc_c(n + k - 1, k)


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

comb = Comb(n, MOD)

ans = 0

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

print(ans % MOD)

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

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

	tmp *= comb
	tmp %= mod

	H *= n-i
	H %= mod
	H *= pow(i, mod-2, mod)
	H %= mod

	tmp *= H
	tmp %= mod

	ans += tmp
	ans %= mod

print(ans)

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

mod = 10 ** 9 + 7
f = [1]
for i in range(1,2*n+1):
    f.append((f[-1] * i) % mod)
def comb(n,r):
    return f[n] * (pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod) % mod

ans = comb(2*n-1, n)
if n-1 <= k:
    print(ans)
    sys.exit()

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

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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

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

inv_table = [0]+[1]
for i in range(2,k+1):
  inv_table.append(-1*(MOD//i)*inv_table[MOD%i] %MOD)

comb_sum=1
fact=1
comb1=1
comb2=1
for i in range(1,k+1):
  comb1=(comb1*(n-i+1)*inv_table[i])%MOD
  comb2=(comb2*(n-i)*inv_table[i])%MOD
  comb=(comb1*comb2)%MOD
  comb_sum+=comb

print(comb_sum%MOD)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
[解説AC]
一回の操作で行うことは動く人を1人決める+動き先を1つ決める
⇒0人の部屋は選べない
⇒0人の部屋を固定して考える.
0人の部屋をm個作る場合(0 <= m <= min(n-1,k))
nCm(n個のうちm個選ぶ)(移動元) * n-mHm(n-m個のうち重複ありでm個選ぶ)(移動先)
"""
def C(n,r):
    return fact[n] * pow(fact[n-r],mod-2,mod) * pow(fact[r],mod-2,mod) % mod


n,k = LI()

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

ans = 0

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

Solution (Python):
import sys
from math import factorial
n, k = [int(i) for i in sys.stdin.readline().split()]
mod = 10**9+7
fact_ls = [1]
res = 1
for i in range(1, n+1):
    res = res * i % mod
    fact_ls.append(res)

def my_fact(r):
    return fact_ls[r]

def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    
    return [w[0], w[1]]



def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m

def nCr(n, r, mod):
    a = my_fact(r)
    b = 1
    for i in range(1, r + 1):
        b = b * (n - i + 1) % mod
    a = mod_inv(a, mod)
    return b * a

def nHr(n, r, mod):
    return nCr(n + r - 1, r, mod)

def calc_func(n, r):
    a = my_fact(r)
    c = my_fact(n - r)
    b = my_fact(n)
    d = my_fact(n-1)
    e = my_fact(n-1-r)
    a = mod_inv(a, mod)
    c = mod_inv(c, mod)
    e = mod_inv(e, mod)
    return b * a * c % mod * d * e * a % mod

res = 1
for i in range(1, min(n, k + 1)):
    res = (res + calc_func(n, i)) % mod
print(res)

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

mod = 10 ** 9 + 7
f = [1]
for i in range(1,2*n+1):
    f.append((f[-1] * i) % mod)
def comb(n,r):
    return f[n] * (pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod) % mod

ans = comb(2*n-1, n)
if n-1 <= k:
    print(ans)
    sys.exit()

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

print(ans)

Solution (Python):
def pow(x, n, mod=None):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n >>= 1
    return ret
n,k = map(int,input().split())
mod = 10**9+7
fact = [None]*(1+n)
finv = [None]*(1+n)
fact[0] = 1
for i in range(1,n+1):
    fact[i] = (fact[i-1]*i)%mod
finv[n] = pow(fact[n],mod-2, mod=mod)
for i in range(n,0,-1):
    finv[i-1] = (finv[i]*i)%mod
def comb(n,k):
    tmp = (finv[n-k]*finv[k])%mod
    return (tmp*fact[n])%mod
ans = 0
for m in range(min(n,k+1)):
    ans = (ans+comb(n,m)*comb(n-1,m))%mod
print(ans)

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

ans = 0
lim = 2*(10**5) + 5
mothers = [1] * lim
mothers_inv = [1] * lim
for i in range(1, lim):
    mothers[i] = mothers[i-1] * i % mod
    mothers_inv[i] = pow(mothers[i], mod-2, mod)


def calc(n,k):
    child = mothers[n] * mothers_inv[n-k] % mod
    mother_inv = mothers_inv[k]
    return((child * mother_inv)%mod)

def calc2(n,k):
    child = 1
    for i in range(n, n-k, -1):
        child = child * i % mod
    mother_inv = mothers_inv[k]
    return((child * mother_inv)%mod)

if( n <= k+1):
    ans = calc2(2*n-1, n-1)
    print(ans)
    exit()

ans = calc2(2*n-1, n-1)

for i in range(1,n-k):
    if(i ==1):
        c1 = 1
    else:
        c1 = calc(n-1, i-1)

    c2 = calc(n, i)
    ans = (ans - c1 * c2)%mod


print(ans)

Solution (Python):

n, k = map(int, input().split())
p = 10 ** 9 + 7
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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


def cmb(n, r):
    return g1[n] * g2[r] * g2[n - r] % p


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

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


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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


n,k = LI()

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

ans = 0

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

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

from math import factorial
class Facts():
    """
    階乗のメモ化
    組み合わせ数、順列数の計算を高速に行う
    """
    def __init__(self, max_num=2*10**5, p=10**9 + 7):
        self.p = p
        self.max_num = max_num
        self.fact = [1] * (self.max_num + 1)
        self.ifact = [1] * (self.max_num + 1)
        for i in range(1, self.max_num + 1):
            self.fact[i] = self.fact[i-1] * i
            self.fact[i] %= self.p
            self.ifact[i] = self.power_func(self.fact[i], self.p-2)

    def comb(self, n, k):
        """ nCk mod p を求める """
        if n < 0 or k < 0 or n < k:
            return 0
        if n == 0 or k == 0:
            return 1
        a = self.fact[n]
        return (a*self.ifact[k] * self.ifact[n-k]) % self.p


    def power_func(self, a, b):
        """ a^b mod p　を繰り返し二乗法で求める """
        if b == 0:
            return 1
        if b % 2 == 0:
            d = self.power_func(a, b//2)
            return d*d % self.p
        if b % 2 == 1:
            return (a*self.power_func(a, b-1)) % self.p

facts = Facts()

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

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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

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

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

comb_sum=1
fact=1
comb1=1
comb2=1
for i in range(1,k+1):
  comb1=(comb1*(n-i+1)*inv_table[i])%MOD
  comb2=(comb2*(n-i)*inv_table[i])%MOD
  comb=(comb1*comb2)%MOD
  comb_sum+=comb

print(comb_sum%MOD)

Solution (Python):
n, k = map(int, input().split())
mod = 10**9+ 7 
def power_(n, p, mod):
    if p == 1:
        return n
    if p % 2 == 0:
        return (power_(n, p//2, mod) ** 2) % mod
    else:
        return n * (power_(n, p//2, mod) ** 2) % mod

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    
    return [w[0],w[1]]



def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod
fact = [1 for i in range(n*2+1)]
for i in range(1,n*2+1):
    fact[i] = (fact[i-1] * i) % mod
if k + 1 >= n:
    child = fact[n * 2  - 1]
    mother = mod_inv(fact[n], mod) * mod_inv(fact[n-1], mod)
    print((child * mother) % mod)
else:
    
    bow = n - k - 1
    """
    child = fact[bow + k]
    mother = (mod_inv(fact[k], mod) * mod_inv(fact[bow], mod)) % mod
    combi = (fact[n] * mod_inv(fact[n - k],mod) * mod_inv(fact[k],mod)) % mod
    aa = power_(n,k,mod)
    aa -= combi
    """
    ans = 0
    
    
    for i in range(k+1):
        bow = n - i - 1
        child = fact[bow + i]
        mother = (mod_inv(fact[i], mod) * mod_inv(fact[bow], mod)) % mod
        combi = (fact[n] * mod_inv(fact[n - i],mod) * mod_inv(fact[i],mod)) % mod
        ans += (child * mother * combi) % mod
        ans %= mod
    print(ans % mod)

Solution (Python):
class Combination:
    '''MOD上の
    計算量：階乗・逆元テーブルの作成O(N)
    nCkを求める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 = [pow(self.fact[i], MOD - 2, MOD) for i in range(n + 1)]
        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[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


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

ans = 0


for cnt_0 in range(0, min(n, k + 1)):
    ball = n
    box = n - cnt_0
    tmp = comb.combination(ball - 1, box - 1)
    tmp *= comb.combination(n, cnt_0)
    ans += tmp
    ans %= MOD

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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

def pow_mod(x,n):
  if n==0:
    return 1
  elif n==1:
    return x
  else:
    xn2=pow_mod(x,n//2)
    if n%2==0:
      return (xn2*xn2)%MOD
    else:
      return (xn2*xn2*x)%MOD

def fact_mod(a):
  if a<=1:
    return 1
  else:
    return a*fact_mod(a-1)%MOD
  
def perm_mod(n,a):
  if a==1:
    return n
  else:
    return (n*perm_mod(n-1,a-1))%MOD

def inv_mod(a):
  return pow_mod(a,MOD-2)%MOD
  
def comb_mod(na,fa):
  ainv=inv_mod(fa)
  return (na*ainv)%MOD
  
if k>=n-1:  
  
  perm=perm_mod(2*n-1,n)
  fact=fact_mod(n)
  comb=comb_mod(perm,fact)
  
  print(comb)
else:
  inv_table = [0]+[1]
  for i in range(2,k+1):
    inv_table+=[inv_table[MOD%i]*(MOD-int(MOD/i))%MOD]
  
  comb_sum=1
  fact=1
  comb1=1
  comb2=1
  for i in range(1,k+1):
    
    comb1=(comb1*(n-i+1)*inv_table[i])%MOD
    
    comb2=(comb2*(n-i)*inv_table[i])%MOD
    comb=(comb1*comb2)%MOD
    comb_sum+=comb
  
  print(comb_sum%MOD)

Solution (Python):
n, k = map(int, input().split())
class factorial:
  def __init__(self, n, p=10**9 + 7):
    self.__p  = p
    self.__fac  = [0] * (n+1)
    self.__inv  = [0] * (n+1)
    self.__finv = [0] * (n+1)

    self.__fac[0] = self.__fac[1] = 1
    self.__inv[1] = 1
    self.__finv[0] = self.__finv[1] = 1

    for i in range(2, n+1):
      self.__fac[i] = self.__fac[i-1] * i % p
      self.__inv[i] = p - self.__inv[p%i] * (p // i) % p
      self.__finv[i] = self.__finv[i-1] * self.__inv[i] % p
  
  def fact(self, n):
    return self.__fac[n]
  
  def perm(self, n, k):
    return self.__fac[n] * self.__finv[n-k] % self.__p
  
  def comb(self, n, k):
    return self.perm(n, k) * self.__finv[k] % self.__p

f = factorial(n)
p = 10**9 + 7
ans = 0
for i in range(min(k+1, n)):
  ans = (ans + f.comb(n, i) * f.comb(n-1, n-i-1)) % p
print(ans)

Solution (Python):
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def power_func(a,b,p):
  if b==0:
    return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return (d*d)%p
  else:
    return (a*power_func(a,b-1,p))%p
n,k=map(int,input().split())
mod=10**9+7
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
r=min(k,n)
for i in range(r+1):
  ans=(ans+cmb(n,i,mod)*cmb(n-1,i,mod))%mod
print(ans)

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

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

ans=0
if k>=n-1:
    ans=fac[n+n-1]*ifac[n]*ifac[n-1]%MOD
else:
    for i in range(k+1):
        if i>n: break
        tmp=fac[n]*ifac[n-i]*ifac[i]%MOD
        tmp=tmp*fac[i+n-i-1]*ifac[n-i-1]*ifac[i]%MOD
        ans=(ans+tmp)%MOD

print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
MOD = 10**9+7

MAXN = 2*10**5+5
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

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

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

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

N = 2 * 2 * 10 ** 5
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

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


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

print(ans)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']
Yn=['Yes','No']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase

sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo


show_flg=False
show_flg=True

ans=0

n,k=LI()
cm=Comb(2*n+10)
if k>=n-1:
    ans=cm.comb(n+n-1,n)
else:
    for i in range(k+1):
        ans+=cm.comb(n,i)*cm.comb(n-1,i)
        ans%=mo
print(ans)

Solution (Python):
MOD = 10**9 + 7
inpl = lambda: list(map(int,input().split()))
def inv_mod(a, p=10**9+7):
    p = abs(p)
    a %= p
    stack = []
    p0 = p
    while a > 1:
        d, a, p = p//a, p%a, a
        stack.append(d)
    x, y = 1, 0
    while stack:
        d = stack.pop()
        x, y = y-d*x, x
    return x % p0
n, k = inpl()
if k >= n:
    k = n-1
ans = 1
t = 1
for i in range(k):
    t *= (n-1-i)*(n-i)
    t %= MOD
    j = inv_mod(i+1)
    t *= j*j % MOD
    ans += t
    ans %= MOD
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class ModTools:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        
        inverse = [1] * MAX
        
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, 0, -1):
            
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 (必要な階乗と逆元のテーブルを事前に作っておく) """

        if n < r: return 0
        
        r = min(r, n-r)
        
        numerator = self.fact[n]
        
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

    def nHr(self, n, r):
        """ 重複組み合わせ """

        
        return self.nCr(r+n-1, r)

N, K = MAP()

mt = ModTools(N*2, MOD)
ans = 0
for i in range(min(K+1, N)):
    ans += mt.nCr(N, i) * mt.nHr(N-i, i)
    ans %= MOD
print(ans)

Solution (Python):

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

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


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


def read_str_n():
    return list(map(str, input().split()))


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


def mt(f):
    import time

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

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

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)

M = Mod(10**9+7)


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):
    C = Combination(N*2, 10**9+7)
    ans = 0
    for i in range(0, min(K+1, N)):
        r = N - i
        t = M.mul(C(N, i), C(r+i-1, i))
        ans = M.add(ans, t)

    return ans




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


if __name__ == '__main__':
    main()

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

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

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

def getCombNs(n, invs, MOD):
    combNs = [1] * (n//2+1)
    for x in range(1, n//2+1):
        combNs[x] = (combNs[x-1] * (n-x+1) * invs[x]) % MOD
    return combNs + combNs[:(n+1)//2][::-1]

def getInvs(n, MOD):
    invs = [1] * (n+1)
    for x in range(2, n+1):
        invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
    return invs


ans = getComb(2*n-1, n, MOD)

if k < n-1:
    m = n-1-k
    invs = getInvs(n+3, MOD)
    combNs = getCombNs(n, invs, MOD)
    combN1s = getCombNs(n-1, invs, MOD)

    for i in range(m):
        ans -= combN1s[i] * combNs[i+1] % 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
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 



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


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(n+1,k+1)):
    ans += cmb(n,i,mod)*cmb(n-1,i,mod)
    ans %= mod
print(ans)

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

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



mod = 10**9+7
 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,2*n+1):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
      
    return fact[n]*finv[r]*finv[n-r]%mod

def nHr(n,r,mod):
    return nCr(n+r-1,r,mod)



ans = 0

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

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

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

k = min(n-1,k)

dp = [0] * (k+1) 
dp[0] = 1
dp[1] = (n * (n-1)) % MOD

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

def nCr(n,r):
    return fact[n] * ifact[r] * ifact[n-r] % MOD

for i in range(2,k+1):
    dp[i] = (nCr(n,i) * nCr(n-1,i)) % MOD

print(sum(dp) % MOD)

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)
ans=0
if(k<n-1):
    for i in range(1,k+1):
        k=cmb(n,i,p)*cmb(n-1,i,p)% p
        ans=ans+k
        ans=ans % p
    ans+=1 % p
else:
    for i in range(1,n):
        k=cmb(n,i,p)*cmb(n-1,i,p)% p
        ans=ans+k
        ans=ans % p
    ans+=1 % p
print(ans)