Задачи
Числа Каталана
Числа Каталана
Числа Каталана $c_n$ задаются рекуррентным соотношением:
$$
c_0 = 1, \\
c_n = \sum_{k=0}^{n-1} c_k c_{n-k-1}, n > 0
$$
Вычислите $n$-ое число Каталана по модулю $m$.
\InputFile
Два целых числа $n~(0 \le n \le 10^4)$ и $m~(0 < m \le 10^9)$.
\OutputFile
Выведите значение $c_n~mod~m$.
Входные данные #1
5 100
Выходные данные #1
42