Compute Catalan Numbers mod p

In the Architectural Office of Prime City, the Architect counts the number of valid bracket sequences, binary search trees, and polygon triangulations ÔÇö all governed by the Catalan numbers. The nth Catalan number is C(n) = C(2n, n) / (n + 1). "The Catalan numbers satisfy the recurrence C(n) = sum of C(i) * C(n-1-i) for i = 0 to n-1," the Architect says. "Or use the formula C(n) = C(2n, n) / (n+1) with modular inverses." Given n and a prime p, compute the nth Catalan number modulo p. Constraints: 0 <= n <= 5000, 2 <= p <= 10^9 (prime) Input: 3 1000000007 Output: 5 Input: 4 1000000007 Output: 14