Catalan number modulo prime
Compute the n-th Catalan number modulo a prime p, where C_n = (2n choose n) / (n + 1). Use factorials and modular inverses (Fermat) so the division by (n+1) is done mod p. Constraints: 0 <= n <= 100000, p is a prime up to 10^9+7 with p > n+1. Return C_n mod p. C_0 = 1.
Implement
catalan_mod_p(n: int, p: int) → intExamples
in
[3,1000000007]out5What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 30 min
solution.py
InputExpectedGot
[3,1000000007]5not run yetsample