Monica problem

def factorial(n):
    if n <= 1:
        return 1
    result = 1
    for i in range(2, n + 1):
        result = (result * i) % 10000
    return result

def combination(n, r):
    if r > n or r < 0:
        return 0
    if r == 0 or r == n:
        return 1
    
    # Use the formula C(n,r) = n! / (r! * (n-r)!)
    # To avoid overflow, we calculate it step by step
    result = 1
    for i in range(min(r, n - r)):
        result = result * (n - i) // (i + 1)
    return result % 10000

def solve():
    n = int(input())
    k = int(input())
    
    total = 0
    # Sum of C(n,1) + C(n,2) + ... + C(n,min(k,n))
    for i in range(1, min(k, n) + 1):
        total = (total + combination(n, i)) % 10000
    
    return total

result = solve()
print(result)