Compute nCr mod p Using Precomputed Factorials

In the Royal Treasury of Prime City, the Treasurer must compute binomial coefficients modulo a prime for various combinatorial calculations. The key insight is that nCr = n! / (r! * (n-r)!), and with modular inverses of factorials, this can be computed in O(1) after O(n) precomputation. "Precompute factorials and their modular inverses up to n," the Treasurer says. "Then nCr mod p = fact[n] * invFact[r] * invFact[n-r] mod p. Use Fermat's Little Theorem for the inverses: inv(x) = x^(p-2) mod p." Given n, r, and a prime p, compute C(n, r) mod p. If r > n, output 0. Constraints: 0 <= r <= n <= 10^6, 2 <= p <= 10^9 (prime) Input: 5 2 1000000007 Output: 10 Input: 10 3 7 Output: 3