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