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