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

Solution (Python):
MOD = 10**9 + 7
fac = [1 for k in range(200010)]
inv = [1 for k in range(200010)]
finv = [1 for k in range(200010)]
for k in range(2,200010):
    fac[k] = (fac[k-1]*k)%MOD
    inv[k] = (MOD - inv[MOD%k] * (MOD // k))%MOD
    finv[k] = (finv[k - 1] * inv[k]) % MOD;

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

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

Solution (Python):
import sys
from operator import itemgetter
from collections import deque, Counter
from itertools import permutations, combinations
from heapq import heapify, heappop, heappush
from bisect import bisect, bisect_left

def comb(n, r, fact, revfact, mod):
    return (fact[n] * revfact[n - r] * revfact[r]) % mod

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    mod = 7 + 10 ** 9
    fact = [1] * (2 * N)
    revfact = [1] * (2 * N)
    for i in range(1, 2 * N): fact[i] = (fact[i - 1] * i) % mod
    revfact[2 * N - 1] = pow(fact[2 * N - 1], mod - 2, mod)
    for i in reversed(range(1, 2 * N - 1)): revfact[i] = ((i + 1) * revfact[i + 1]) % mod
    ans = 1
    if K < N:
        for i in range(1, min(K + 1, N + 1)): 
            z = comb(N, i, fact, revfact, mod) 
            add = comb(N - 1, N - i - 1, fact, revfact, mod)
            ans += (z * add) % mod
    else:
        ans = comb(N + N - 1, N, fact, revfact, mod)

    print(ans % mod)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def modinv2(x,r):
  return pow(x,r-2,r)

def comb(n,a):
    dend = n
    for i in range(1,a):
        dend = (dend*(n-i))%R
    sor = 1
    for i in range(2,a+1):
        sor = (sor*i)%R
    return (dend*modinv2(sor,R))%R

n,k = inm()
if n-1<=k:
    print(comb(2*n-1,n-1))
    exit()
c = [1]*(k+1)
d = [1]*(k+1)
for i in range(1,k+1):
    m = modinv2(i,R)
    c[i] = (c[i-1]*(n-i+1)*m)%R
    d[i] = (d[i-1]*(n-i)*m)%R
ddprint("c,d")
ddprint(c)
ddprint(d)
sm = 0


for j in range(k+1):
    sm = (sm+c[j]*d[j])%R
if k==1:
    sm = (sm-1)%R
print(sm)

Solution (Python):

import sys 
input = sys.stdin.readline

def factorial_mod(x, y, mod):
    factorial = 1
    for i in range(x,y+1):
        factorial *= i
        factorial %= mod
    return factorial

def n_C_k(n,k,mod):
    factorial_nk = factorial_mod(n-k+1, n, mod)
    factorial_k = factorial_mod(1,k,mod)
    conbi=factorial_nk*pow(factorial_k, mod-2, mod)
    return conbi%mod


def main():
    n, k = map(int, input().split())
    mod = 10**9+7
    ans = 1+n*(n-1)

    a = n
    
    
    b = n-1

    for i in range(1, min(n, k)):
        temp1 = (n-i)*pow(i+1, mod-2, mod)%mod
        a *= temp1
        a %= mod
        temp2 = (n-1-i)*pow(i+1, mod-2, mod)%mod
        b *= temp2
        b %= mod
        temp3 = a*b%mod
        ans += temp3
        ans %= mod

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def main():

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

    g1 = [1, 1]
    g2 = [1, 1]
    inv = [0, 1]

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

    def combi(n, r):
        r = min(r, n-r)
        return g1[n]*g2[r]*g2[n-r]%mod

    if k >= n-1:
        k = n-1
    ans = 1
    for i in range(1, k+1):
        ans += (combi(n, i) * combi(n-1, n-i-1)) % mod
    return ans % mod


if __name__ == '__main__':
    print(main())

Solution (Python):
n,k=map(int,input().split())
MAX_NUM = 4*10**5
pr = 10**9+7
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
a=c(2*n-1,n)
if k>=n-1:
    print(a)
else:
    for i in range(k+1,n):
        a=(a-c(n,i)*c(n-1,n-i-1))%pr
    print(a)

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

class BiCoeff(object):
    def __init__(self, MAX, m):
        super(BiCoeff, self).__init__()
        fac = [0]*MAX
        finv = [0]*MAX
        inv = [0]*MAX

        fac[0] = 1
        fac[1] = 1
        finv[0] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2,MAX):
            fac[i] = (fac[i-1]*i)%m
            inv[i] = m - (inv[m%i] * (m//i))%m
            finv[i] = (finv[i-1] * inv[i])%m

        self.MAX = MAX
        self.m = m
        self.fac = fac
        self.finv = finv
        self.inv = inv

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


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

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

res = 0
for i in range(1,n+1):
    if n-i<=k:
        res += bicoeff.calc(n-1,i-1)*bicoeff.calc(n,i)
        res %= MOD
print(res)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
fact = [i for i in range(4 * 10 ** 5 + 1)]
fact[0] = 1
for i in range(4 * 10 ** 5):
    fact[i + 1] *= fact[i]
    fact[i + 1] %= mod

def combination_mod(n, k, mod):
    """ power_funcを用いて(nCk) mod p を求める """
    """ nCk = n!/((n-k)!k!)を使用 """
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = fact[n] % mod
    b = fact[k] % mod
    c = fact[n - k] % mod
    return (a * pow(b, mod - 2, mod) * pow(c, mod - 2, mod)) % mod


def solve():
    n, k = LI()

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

    return



if __name__ == '__main__':
    solve()

Solution (Python):
n,k = map(int,input().split())
k = min(n-1, k)
MOD = 10**9 + 7
N = 3*10**5

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


def perm(n, k):
  return fact[n] * rfact[n-k] % MOD


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

ans = 0
for i in range(0, k+1):
    if i == 0:
        zero_pt = 1
    else:
        zero_pt = comb(n, i)
    rest = i
    sikiri = n - i - 1
    if sikiri == 0:
        plus_pt = 1
    else:
        plus_pt = comb(rest + sikiri, sikiri)
    ans += zero_pt * plus_pt
    ans %= MOD
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
INF=10**9+7
p=[0]*n
p[0]=1
def modinv(a,m):
    b=m
    (x,lastx)=(0,1)
    (y,lasty)=(1,0)
    while not b==0:
        q=a//b
        (a,b)=(b,a%b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx%m
x=n-1
y=n
for i in range(1,n):
    p[i]=(x*y)%INF
    a=n-1-i
    b=modinv(i+1,INF)
    x=(x*a*b)%INF
    a = n - i
    b = modinv(i+1, INF)
    y = (y * a * b) % INF
ans=0
if k>=n:
    for i in range(n):
        ans=(ans+p[i])%INF
else:
    for i in range(k+1):
        ans=(ans+p[i])%INF
print(ans)

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

comb0 = [1] * (n)

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

comb1 = [1] * (n)

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

ans = 0

for i in range(min(n - 1, k) + 1):
    ans += comb0[i] * comb1[i]
    ans %= mod

print(ans)

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

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

mod=10**9 + 7
fact=[1,1]
factinv=[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 // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)
    
ans=0

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

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

def inv(a,mod):
    r = [1,0,a]
    w = [0,1,mod]
    while w[2]!=1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = w
        w = r_new
    x,y = w[0],w[1]    
    return (mod+x%mod)%mod

max_num = 2*10**5+1
fact = [0 for _ in range(max_num)]
ifact = [0 for _ in range(max_num)]

fact[0] = fact[1] = 1
ifact[0] = ifact[1] = 1

for i in range(2,max_num):
    fact[i] = fact[i-1] * i % mod
    ifact[i] = ifact[i-1] * inv(i,mod) % mod

def comb(x,y):
    return fact[x] * ifact[y] * ifact[x-y] % mod

ans = 1

ff = min(k+1,n)

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

print(ans)

Solution (Python):
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
    
n,k = map(int,input().split())
A = [1 for _ in range(n+1)]
for i in range(2,n+1):
    A[i] = (i*A[i-1])%p
B = [1 for _ in range(n+1)]
B[n] = pow(A[n],p-2)
for i in range(n-1,1,-1):
    B[i] = (B[i+1]*(i+1))%p

cnt = 0
for i in range(min(k,n-1)+1):
    a = (A[n]*B[n-i]*B[i])%p
    b = (A[n-1]*B[n-1-i]*B[i])%p
    cnt = (cnt+a*b)%p
print(cnt)

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

def mod_inverse(a, p):
    mod = 1
    p_bin = bin(p-2)
    for i in range(len(p_bin) - 1, 1, -1):
        if i == len(p_bin) - 1:
            mul = a
            mul %= p
            mod *= (mul ** int(p_bin[i]))
            mod %= p
        else:
            mul = mul ** 2
            mul %= p
            mod *= (mul ** int(p_bin[i]))
            mod %= p
    return mod

b = []
for i in range(a):
    b.append(mod_inverse(i + 1, p))
b1 = [1]
b2 = [1]
for i in range(a):
    temp = b1[-1] * (n - i)
    temp *= b[i]
    temp %= p
    b1.append(temp)
    temp2 = b2[-1] * (n - 1 - i)
    temp2 *= b[i]
    temp2 %= p
    b2.append(temp2)
ans = 0
for i in range(a + 1):
    ans += b1[i] * b2[i]
    ans %= p
print(ans)

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

fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]

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

for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

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

sum = 1
t = 1
for i in range(min(n, k)):
  t = ((t * (n-i)) % MOD * (n-i-1)) % MOD
  t = ((t * inv[i+1]) % MOD * inv[i+1]) % MOD
  sum = (sum + t) % MOD

print(sum)

Solution (Python):
import sys

def inverse(a,mod): 
    return pow(a,mod-2,mod)







def modfac(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 modnCr(n,r,mod,fac,inv): 

    return fac[n] * inv[n-r] * inv[r] % mod


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

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

print (nm1lis)
"""

if k >= n:
    print (modnCr(2*n-1,n,mod,fac,inv))
    sys.exit()

"""
求めるのは人数の組み合わせ
どうする？
不可能なものの数を数えて引くか？
k+2以上の人数の部屋があったら不可能
k+2人以上が1つあるときの組み合わせ- (2つあるときの組み合わせ) + …

でいけそうかな？
それ以外は可能なのか？

0の数がk恋かの組み合わせ
0の数がk個より大きいなら不可能

0がk+1個…Nこ
"""

ans = modnCr(2*n-1,n,mod,fac,inv)
loop = 1

for i in range(k+1,n):

    bn = n - i - 1
    now = modnCr(n,i,mod,fac,inv) * modnCr(i+bn,bn,mod,fac,inv)

    ans -= now
    
    ans %= mod

    loop += 1

print (ans)

"""

while (k+2)*loop <= n:

    now = modnCr(n,loop,mod,fac,inv) * modnCr(n-1 + (n-(k+2)*loop),n-1,mod,fac,inv)
    if loop % 2 == 1:
        ans -= now
    else:
        ans += now

    ans %= mod

    loop += 1

"""

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

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

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

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

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


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

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

    mi = min(k, n - 1)

    cl = Calc(max_value=n * 2 - 1, mod=mod)

    ret = 0
    for r in range(mi + 1):
        ret += cl.combination(n - 1, n - r - 1) * cl.combination(n, r)
        ret %= mod

    print(ret)


if __name__ == '__main__':
    main()

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 
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

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


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

Solution (Python):
import sys

MOD = 10 ** 9 + 7

def make_table(size=10**6, p=MOD):
    fac = [None] * (size + 1)
    fac[0] = 1
    for i in range(size):
        fac[i+1] = fac[i] * (i + 1) % p
    ifac = [None] * (size + 1)
    ifac[size] = pow(fac[size], p-2, p)
    for i in range(size, 0, -1):
        ifac[i-1] = ifac[i] * i % p
    return fac, ifac

fac, ifac = make_table(5*10**5)

def comb(n, r, mod=MOD):
    if r > n or r < 0:
        return 0
    return fac[n] * ifac[r] % mod * ifac[n-r] % mod

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

n, k = map(int, sys.stdin.readline().split())

def main():
    if k >= n - 1:
        return nHr(n, n)
    else:
        res = nHr(n, n)
        for i in range(k+1, n+1):
            res -= comb(n, i) * nHr(n-i, i) % MOD
            res %=MOD

        return res % MOD
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
p = 10 ** 9 + 7
N = (10 ** 5)*2 +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 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


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

ans = [1]







for  i in range(1,N+1):
    mm1 = cmb(N,i,p)
    
    
    mm2 = cmb(N-i+i-1,i,p)

    ans.append((mm1*mm2)%p)

mm = 0
for i in range(min(N+1,K+1)):
    mm += ans[i]
    mm %= p
print(mm)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
INF = 10 ** 20
MOD = 10**9 + 7
def combmod(n, k, mod=MOD):
    if k == 0:
        return 1
    if k == 1:
        return n
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret

def main():
    n, k = getList()
    if k >= n-1:
        ans = combmod(n+n-1, n)
    else:
        
        ans = 1
        tmp = 1
        for i in range(1, k+1):
            tmp *= n-i
            tmp *= n + 1 - i
            tmp *= pow(i, MOD-2, MOD)
            tmp *= pow(i, MOD - 2, MOD)
            ans += tmp
            tmp %= MOD
            
            
            
            
            ans %= MOD
        
        
        
        
    print(ans)


if __name__ == "__main__":
    main()

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


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

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

    return modFacts, invs


N, K = map(int, input().split())
modFacts, invs = prepare(N)

ans = 0
for k in range(min(K + 1, N)):
    num = (modFacts[N - 1] * invs[N - k - 1] * invs[k]) % MOD
    zero = (modFacts[N] * invs[k] * invs[N - k]) % MOD
    ans += (num * zero) % MOD
    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 = 4*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 )

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

else:
    print(cmb(2*n-1,n,mod))

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

ret=modpow(2,n)
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
def comb(x,n):
    divd=1
    for i in range(n):
        divd*=ModInt(x-i)
    for i in range(n):
        divd/=ModInt(i+1)
    return divd
if k<n-1:
    combl_1=[1]*n
    combl_2=[1]*(n+1)
    combl_1[1]=n-1
    combl_2[1]=n
    for i in range(2,n):
        combl_1[i]=ModInt(n-i)*combl_1[i-1]/ModInt(i)
        combl_2[i]=ModInt(n-i+1)*combl_2[i-1]/ModInt(i)
    ans=0
    for i in range(k+1):
        ans+=combl_1[i]*combl_2[i]
    print(ans)
if k>=n-1:
    print(comb(2*n-1,n-1))

Solution (Python):


import numpy as np

stdin = open(0)


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


MOD = 10 ** 9 + 7




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


def make_fact(U, MOD=MOD):
    x = np.arange(U, dtype=np.int64)
    x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64)
    x[0] = pow(int(fact[-1]), MOD - 2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    fact.flags.writeable = False
    fact_inv.flags.writeable = False
    return fact, fact_inv



fact, fact_inv = make_fact(N + 10)


if K >= N:
    K = N - 1
x = fact[N] * fact_inv[0:K + 1] % MOD * fact_inv[N - K:N + 1][::-1] % MOD
y = fact[N - 1] * fact_inv[0:K + 1] % MOD * fact_inv[N - K - 1:N][::-1] % MOD
answer = np.sum(x * y % MOD) % MOD


print(answer)

Solution (Python):
MOD = 10**9+7
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __imod__(self, other):
        self.x %= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __mod__(self, other):
        return (
            mint(self.x % other.x) if isinstance(other, mint) else
            mint(self.x % other)
        )
    def __truediv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rmod__(self, other):
        return (
            mint(other.x % self.x) if isinstance(other, mint) else
            mint(other % self.x)
        )
    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

class comb():
    
    def __init__(self, n):
        self.n = n
        fact = [0]*(n+1) 
        ifact = [0]*(n+1) 
        fact[0] = mint(1)
        for i in range(1, n+1):
            fact[i] = fact[i-1]*i
        ifact[-1] = pow(fact[-1], MOD-2)
        for i in range(n, 0, -1):
            ifact[i-1] = ifact[i]*i
        self.fact = fact
        self.ifact = ifact
    def calc(self, n, k):
        if k<0 or k>n:
            return 0
        return self.fact[n]*self.ifact[k]*self.ifact[n-k]

n,k = map(int, input().split())
cb=comb(200005)

ans=mint(0)

for i in range(min(n,k+1)):
    ans+=cb.calc(n,i)*cb.calc(n-1, i)



print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __str__(self):
        return str(self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10**9+7
def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] * ifac[com_n - com_r]

def nHr(hn,hr):return nCr(hn+hr-1,hr)

n_max = 200005
fac = [mint(1)]
for i in range(1, n_max + 1): fac.append(fac[-1] * i)
ifac = [mint(1)] * (n_max + 1)
ifac[n_max] /= fac[n_max]
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1)

def main():
    n,k=MI()
    ans=mint(0)
    for v in range(min(k+1,n)):
        ans+=nCr(n,v)*nHr(n-v,v)
    print(ans)

main()

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 
g1 = [1, 1]  
g2 = [1, 1]  
inverse = [0, 1]  

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

def modPow(a, n, mod):
    if n == 1:
        return a
    if n % 2 == 1:
        return (a * (modPow(a, n//2, mod) ** 2)) % mod
    else:
        return (modPow(a, n//2, mod) ** 2) % mod


def modInverse(a, p):
    
    
    return modPow(a, p-2, p)


def modBinomial(n, k, p):
    

    numerator = 1  
    for i in range(k):
        numerator = (numerator * (n-i)) % p

    denominator = 1  
    for i in range(1, k+1):
        denominator = (denominator * i) % p

    
    return (numerator * modInverse(denominator, p)) % p

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

if n <= k:
    print(modBinomial(2*n-1,n,mod))
    exit()
ans = 0
if k != 1:
    ans += 1
for i in range(1,k+1):
    ans = (ans + cmb(n,i,mod) * cmb(n-1,i,mod)) % mod

print(ans)

Solution (Python):
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
def comb(n,k,mod):
    c = 1
    for i in range(k):
        c = c*(n-i)%mod
        c = c*mod_inv(i+1,mod)%mod
    return c
n,k = map(int,input().split())
mod = 10**9+7
if k >= n-1:
    print(comb(n+n-1,n,mod))
else:
    ans = 0
    c = 1
    c2 = 1
    for i in range(k):
        c = c*(n-1-i)%mod
        c2 = c2*(n-i)%mod
        c = c*mod_inv(i+1,mod)%mod
        c2 = c2*(mod_inv(i+1,mod))%mod
        ans += c*c2
        ans %= mod
    if k > 1:
        ans += 1
    print(ans)

Solution (Python):









n,k  = map(int,input().split( ))
mod = 10**9+7
if k==1:
    print(n*(n-1))
    exit()
rev = [0]+[pow(i,mod-2,mod) for i in range(1,n+3)]
chs_nx = [0]
def chs(t,s):
    res = 1
    for i in range(t,t-s,-1):
        res *= i
        res %=mod
    for i in range(1,s+1):
        res *= rev[i]
        res %=mod
    return res
res = 1
mn = min(n,k)
for i in range(1,mn+1):
    res *= n-i+1
    res *= rev[i]
    res %=mod
    chs_nx.append(res)
ans = 1

for i in range(1,mn+1):
    ans += chs_nx[i]**2*(n-i)*rev[n]
print(ans%mod)