eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Числа Каталана

Числа Каталана

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Числа Каталана 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