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

Submission attempts (in order):
from functools import lru_cache


CHECK = False

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

MOD = 10 ** 9 + 7


@lru_cache(maxsize=None)
def modInverse(a, p):
    # Fermat's little theorem, a**(p-1) = 1 mod p
    return pow(a, p - 2, p)


if CHECK:
    fact = [1]
    for i in range(1, 2 * N + 1):
        fact.append((fact[-1] * i) % MOD)

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


if N - 1 <= K:
    # Any combo is achievable so this is stars and bars
    # N people into N rooms, which means N - 1 dividers
    stars = N
    bars = N - 1
    print(nCr(stars + bars, bars))
else:
    # Group by number of empty rooms
    # With K moves there can only be at most K empty rooms
    # Max of N - 1 empty rooms in general
    assert K + 1 < N
    tot = 0
    comb1 = 1
    comb2 = 1
    for numEmpty in range(K + 1):
        way3 = comb1 * comb2
        if CHECK:
            numNonEmpty = N - numEmpty
            stars = numEmpty  # Everyone moving into an occupied room
            bars = numNonEmpty - 1  # Number of dividers
            way1 = nCr(stars + bars, bars) * nCr(N, numEmpty)

            way2 = nCr(N, numEmpty) * nCr(N - 1, numEmpty)

            assert way1 % MOD == way2 % MOD == way3 % MOD
        tot += way3

        j = numEmpty + 1
        invJ = modInverse(j, MOD)
        comb1 = (N + 1 - j) * comb1 * invJ % MOD
        comb2 = (N - j) * comb2 * invJ % MOD
    print(tot % MOD)


from functools import lru_cache


CHECK = False

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

MOD = 10 ** 9 + 7


@lru_cache(maxsize=None)
def modInverse(a, p):
    # Fermat's little theorem, a**(p-1) = 1 mod p
    return pow(a, p - 2, p)


if N - 1 <= K or CHECK:
    fact = [1]
    for i in range(1, 2 * N + 1):
        fact.append((fact[-1] * i) % MOD)

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


if N - 1 <= K:
    # Any combo is achievable so this is stars and bars
    # N people into N rooms, which means N - 1 dividers
    stars = N
    bars = N - 1
    print(nCr(stars + bars, bars))
else:
    # Group by number of empty rooms
    # With K moves there can only be at most K empty rooms
    # Max of N - 1 empty rooms in general
    assert K + 1 < N
    tot = 0
    comb1 = 1
    comb2 = 1
    for numEmpty in range(K + 1):
        way3 = comb1 * comb2
        if CHECK:
            numNonEmpty = N - numEmpty
            stars = numEmpty  # Everyone moving into an occupied room
            bars = numNonEmpty - 1  # Number of dividers
            way1 = nCr(stars + bars, bars) * nCr(N, numEmpty)

            way2 = nCr(N, numEmpty) * nCr(N - 1, numEmpty)

            assert way1 % MOD == way2 % MOD == way3 % MOD
        tot += way3

        j = numEmpty + 1
        invJ = modInverse(j, MOD)
        comb1 = (N + 1 - j) * comb1 * invJ % MOD
        comb2 = (N - j) * comb2 * invJ % MOD
    print(tot % MOD)


Verdicts: Runtime Error

Accepted