Binomial coefficient modulo prime
Your task
Given non-negative integers n and r and a prime p, return C(n, r) modulo p, where C(n, r) is the binomial coefficient "n choose r". n and r can be as large as 10^9, so you cannot precompute factorials up to n. Assume 2 <= p <= 10^9 and p is prime. If r > n the answer is 0.
Examples
ncr_mod_prime(n: int, r: int, p: int) -> intExample 1
Input
ncr_mod_prime(5, 2, 13)Output
10