1328. Counting Balanced Arrangements
Print the nth Catalan number modulo a prime p. You are guaranteed
2n < p.
C(0)=1 C(1)=1 C(2)=2 C(3)=5 C(4)=14 C(5)=42 C(10)=16796
The Catalan numbers count a surprising number of different things with the same
answer: bracket sequences of n pairs that are balanced, binary trees with n
nodes, ways to triangulate a polygon, paths that never cross the diagonal. Being
able to recognise the sequence is most of the value of knowing it.
The closed form is:
Catalan(n) = C(2n, n) / (n + 1)
which needs the same treatment as problem 1326: build factorials modulo p, and
turn both divisions into multiplications by modular inverses through Fermat.
Note there are two divisions, not one. Dividing by n + 1 modulo p is another
inverse, and doing it with ordinary integer division after the reduction gives a
wrong answer that looks plausible.
2n < p is what keeps every factorial free of the factor p, so all the
inverses exist.
Constraints - `0 ≤ n ≤ 1000000` - `2n < p ≤ 1000000007`, and `p` is prime
Input
One line containing two integers n and p.
Output
Print the nth Catalan number modulo p.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.