Задача D. 2-3 Дерево

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб
Максимальный балл:100  

Условие

2-3 дерево - элегантная структура данных, изобретенная Джоном Хопкрофтом. Она предназначена для использования с той же целью, что и двоичное дерево поиска. 2-3 дерево представляет собой дерево с корнем, которое обладает следующими свойствами:

Единственное исключение - это когда дерево содержит ровно одну вершину. В этом случае корень дерева является и листом, и поэтому не имеет детей. Основная суть приведенных свойств в том, что дерево с l листьями имеет высоту O(log l).

Вообще говоря, может существовать несколько 2-3 деревьев с l листьями. Например, на следующем рисунке показаны два возможных дерева с 6 листьями.

По заданному числу l найдите количество различных 2-3 деревьев с l листьями. Так как ответ может быть довольно большим, выведите его по модулю r.

Формат входного файла

Входной файл содержит два целых числа: l и r.

Формат выходного файла

Выведите одно число - количество различных 2-3 деревьев, имеющих ровно l листьев, взятое по модулю r.

Ограничения

1 ≤ l ≤ 5000, 1 ≤ r ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
6 1000000000
2
2
7 1000000000
3

0.069s 0.008s 15