2-3 Дерево
(Время: 3 сек. Память: 16 Мб Сложность: 61%)
2-3 дерево — элегантная структура данных, изобретенная Джоном Хопкрофтом. Она предназначена для использования с той же целью, что и двоичное дерево поиска. 2-3 дерево представляет собой дерево с корнем, которое обладает следующими свойствами:
- корень и каждая внутренняя вершина имеет либо 2 либо 3 ребенка;
- глубина всех листьев одна и та же.
Единственное исключение — это когда дерево содержит ровно одну вершину. В этом случае корень дерева является и листом, и поэтому не имеет детей. Основная суть приведенных свойств в том, что дерево с L листьями имеет высоту O(log L).
Вообще говоря, может существовать несколько 2-3 деревьев с L листьями. Например, на следующем рисунке показаны два возможных дерева с 6 листьями.
По заданному числу L найдите количество различных 2-3 деревьев с L листьями. Так как ответ может быть довольно большим, выведите его по модулю R.
Входные данные
Входной файл INPUT.TXT содержит два целых числа: L и R (1 ≤ L ≤ 5 000, 1 ≤ R ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – количество различных 2-3 деревьев, имеющих ровно L листьев, взятое по модулю R.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 6 1000000000 | 2 |
| 2 | 7 1000000000 | 3 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
