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.