Обмеження на час виконання 1 секунда Обмеження на використання пам'яті 128 мегабайтів Числа Каталана cn задаются рекуррентным соотношением:
c0=1,cn=k=0∑n−1ckcn−k−1,n>0
Вычислите n-ое число Каталана по модулю m.
Вхідні дані
Два целых числа n (0≤n≤104) и m (0<m≤109).
Вихідні дані
Выведите значение cn mod m.
Приклади