2-3 Дерева
2-3 дерево — это элегантная структура данных, разработанная Джоном Хопкрофтом. Оно служит для выполнения тех же функций, что и бинарное дерево поиска. 2-3 дерево представляет собой упорядоченное корневое дерево с такими свойствами:
Корень и каждая внутренняя вершина имеют либо 2, либо 3 дочерних узла.
Расстояние от корня до любого листа дерева одинаково.
Единственное исключение — это дерево, содержащее ровно одну вершину. В этом случае корень дерева является единственной вершиной и одновременно листом, то есть не имеет дочерних узлов. Основная идея этих свойств заключается в том, что дерево с l листьями имеет высоту O(log l).
Для заданного числа листьев l может существовать несколько допустимых 2-3 деревьев, имеющих l листьев. Например, на рисунке ниже показаны два возможных 2-3 дерева с ровно 6 листьями.
Дано l, найдите количество различных 2-3 деревьев, имеющих l листьев. Поскольку это число может быть довольно большим, выведите его по модулю r.
Входные данные
Входной файл содержит два целых числа: l и r (1 ≤ l ≤ 5000, 1 ≤ r ≤ 10^9).
Выходные данные
Выведите одно число — количество различных 2-3 деревьев с ровно l листьями по модулю r.