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

Условие

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

• корень и каждая внутренняя вершина имеет либо 2 либо 3 ребенка;
• глубина всех листьев одна и та же.

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

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

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

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

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

Ограничения

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

6 1000000000

2

7 1000000000

3