Problems
Catalan numbers
Catalan numbers
Catalan numbers $c_n$ are given by recurrence relation:
$$
c_0 = 1, \\
c_n = \sum_{k=0}^{n-1} c_k c_{n-k-1}, n > 0
$$
Compute the $n$-th Catalan numbers modulo $m$.
\InputFile
Two integers $n~(0 \le n \le 10^4)$ and $m~(0 < m \le 10^9)$.
\OutputFile
Print the value of $c_n~mod~m$.
Input example #1
5 100
Output example #1
42