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):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007





m, k = LI()
n = m * 2 + 2

fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


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


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


ret = 0
for i in range(min(m, k + 1)):
    ret = ret + comb(m, i) * comb(m - 1, i) % mod
    ret %= mod


print(ret)

Solution (Python):
n, k = map(int, input().split())
mod = 10**9+7
def make_fact(n):
    fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i%mod
    return fact
fact = make_fact(n*2) 
def make_fact_inv(n):
    fact_inv = [1]*(n+1)
    fact_inv[n] = pow(fact[n], mod-2, mod)
    for i in range(n, 0, -1):
        fact_inv[i-1] = fact_inv[i]*i%mod
    return fact_inv
fact_inv = make_fact_inv(n*2)
def comb(n, k):
    return fact[n]*fact_inv[k]*fact_inv[n-k]%mod
mod = 10**9+7
ans = 0
for i in range(n):
    m = n-i
    c = n-m
    if c+i>k*2:
        continue
    ans+=comb(n, i)*comb(m+c-1, m-1)%mod
    ans%=mod
print(ans)

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

fra=[1]*(2*n+2)
inv=[1]*(2*n+2)
t=1
for i in range(1,2*n+2):
    t*=i
    t%=mod
    fra[i]=t
t=pow(fra[2*n+1],mod-2,mod)
for i in range(2*n+1,0,-1):
    inv[i]=t
    t*=i
    t%=mod
def comb(n,r):
    return fra[n]*inv[n-r]*inv[r]%mod
if n<=k:
    print(comb(2*n-1,n))
    quit()
ans=0
for i in range(min(n,k)+1):
    ans+=comb(n,i)*comb(n-1,i)
    ans%=mod
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7
fac = [1]
caf = [1]

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


def pow(n, p):
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod


for i in range(1, N * 2):
    fac.append((fac[i - 1] * i) % mod)
    caf.append(pow(fac[i], mod - 2))


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


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

Solution (Python):
mod=10**9+7
f=[1]
for i in range(10**6):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod

n,k=map(int,input().split())
ans=comb(n*2-1,n-1)
if k>=n-1:print(ans);exit()
for i in range(n-1,k,-1):
  
  
  
  
  
  anss=comb(n-1,i)*comb(n,n-i)%mod
  ans=ans+(mod-anss)
  ans%=mod
print(ans)

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

mod = 10**9+7

class PERM_COMB_MOD():
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

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

    def comb(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.mod) % self.mod

    def h(self, n, k):
        if n == k == 0:
            return 1
        return self.comb(n+k-1, k)

n,k = map(int, input().split())
PCM = PERM_COMB_MOD()
if k > n:
    k = n

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

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

MOD = 10**9+7
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%MOD
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % MOD
    return frac, fraci
frac, fraci = frac(1341398)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%MOD

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

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

Solution (Python):
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n_ = 5*10**5
mod = 10**9+7
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod

def nCr(n,r):
    if r > n:
        return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

n,k = nm()
if k >= n-1:
    print(nCr(2*n-1, n-1))
    exit(0)

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

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

Solution (Python):
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

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

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

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

NNN = (3*10**5)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
N, K = map(int, input().split())

K = min(N-1, K)

r = 0
for i in range(K+1):
    r = (r + mul(cmb(N, i), cmb(N-1, N-i-1)))%mod
print(r)

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

    return factorials, invs


def solve(n, k):
    MOD = 10 ** 9 + 7
    facts, invs = prepare(2 * n, MOD)
    if k >= n - 1:
        return facts[2 * n - 1] * invs[n - 1] * invs[n] % MOD

    ans = 0
    for z in range(k + 1):
        tmp = facts[n] * invs[z] * invs[n - z] % MOD
        tmp = tmp * facts[n - 1] * invs[z] * invs[n - z - 1] % MOD
        ans = (ans + tmp) % MOD

    return ans


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

Solution (Python):
nn = 404040
P = 10**9+7

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P

C = lambda a, b: fa[a] * fainv[b] * fainv[a-b] % P if 0 <= b <= a else 0

N, K = map(int, input().split())
if K >= N-1:
    print(C(2*N-1, N))
else:
    s = 0
    for i in range(K+1):
        s = (s + C(N, i) * C(N-1, i)) % P
    print(s)

Solution (Python):

import sys
input = sys.stdin.readline
MOD = 10**9 + 7
MAX_N = 2 * 10**5 + 10

fac = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * (i) % MOD

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

def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD

n, k = [int(item) for item in input().split()]
ans = 0
for zero_num in range(min(n, k+1)):
    ans += mod_nCr(n-1, zero_num) * mod_nCr(n, zero_num)
    ans %= MOD

print(ans)

Solution (Python):
SIZE=4*10**5+1; MOD=10**9+7 

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

def choose(n,r): 
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0

def chofuku(ball,box): 
    return choose(box+ball-1,box)




import sys
readline = sys.stdin.readline
read = sys.stdin.read





n,k = [int(i) for i in read().split()]




ans = 0
M = min(k,n)

for j in range(M+1):
    ans += choose(n,j)*choose(n-1,j)%MOD

print(ans%MOD)

Solution (Python):

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

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

M = [1]  
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  
    return pow(x, mod-2, mod)



MI = [0] * (l-1) +[inv(M[l-1], mod)]  
for i in range(l-2, -1, -1):
    MI[i] = MI[i+1] * (i+1) % mod

def C(x, y):  
    if y < 0 or y > x:
        return 0
    ans = M[x]
    ans = (ans * MI[y]) % mod
    return (ans * MI[x-y]) % mod

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

Solution (Python):
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
'''
p = 10 ** 9 + 7
N = 10 ** 6 + 2
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 = list(map(int, input().split()))

j = min(n-1,k)

p = 10 ** 9 + 7
N = 10 ** 5 * 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 = 1

for ii in range(j):
    i = ii+1
    ans += cmb(n,i,p)*cmb(n-1,i,p)
    ans %= p

print(ans)

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n, k = na()
mod = 1000000007

def comb(n, r, mod):
    if n < 0 or r < 0 or r > n: return 0
    nu = 1
    de = 1
    for i in range(r):
        nu = nu * (n-i) % mod
        de = de * (i+1) % mod
    return nu * inv(de, mod) % mod

def inv(a, mod):
    b = mod
    p, q = 1, 0
    while b > 0:
        c = a//b
        d = a; a = b; b = d % b
        d = p; p = q; q = d-c*q
    return p+mod if p < 0 else p







def enumfif(n, mod):
    f = [0] * (n+1)
    invf = [0] * (n+1)
    f[0] = 1
    for i in range(1, n+1):
        f[i] = f[i-1] * i % mod

    a = f[n]
    b = mod
    p, q = 1, 0
    while b > 0:
        c = a//b
        d = a; a = b; b = d % b
        d = p; p = q; q = d-c*q
    invf[n] = p + mod if p < 0 else p
    for i in range(n-1,-1,-1):
        invf[i] = invf[i+1] * (i+1) % mod
    return f, invf

def C(n, r, mod, fif):
    if n < 0 or r < 0 or r > n:
        return 0
    return fif[0][n] * fif[1][r] * fif[1][n-r] % mod


if k >= n-1:
    print(comb(n-1+n, n, mod))
else:
    fif = enumfif(400005, mod)
    
    ans = comb(n-1+n, n, mod)
    for z in range(k+1, n+1):
        ans -= C(n, z, mod, fif) * C(n-z-1+(n-(n-z)), (n-(n-z)), mod, fif)
    ans %= mod
    if ans < 0:
        ans += mod
    print(ans)