Problems
2-3 Trees
2-3 Trees
\textbf{2}-\textbf{3} tree is an elegant data structure invented by John Hopcroft. It is designed to implement the same functionality as the binary search tree. \textbf{2}-\textbf{3} tree is an ordered rooted tree with the following properties:
\begin{itemize}
\item the root and each internal vertex have either \textbf{2} or \textbf{3} children;
\item the distance from the root to any leaf of the tree is the same.
\end{itemize}
The only exception is the tree that contains exactly one vertex --- in this case the root of the tree is the only vertex, and it is simultaneously a leaf, i.e. has no children. The main idea of the described properties is that the tree with \textbf{l} leaves has the height \textbf{O(log l)}.
Given the number of leaves \textbf{l} there can be several valid \textbf{2}-\textbf{3} trees that have \textbf{l} leaves. For example, the picture below shows the two possible \textbf{2}-\textbf{3} trees with exactly \textbf{6} leaves.
\includegraphics{https://static.e-olymp.com/content/a1/a1e514cb670e63a700142498a0706610d9fed5c0.jpg}
Given \textbf{l} find the number of different \textbf{2}-\textbf{3} trees that have \textbf{l} leaves. Since this number can be quite large, output itmodulo \textbf{r}.
\InputFile
Input file contains two integer numbers: \textbf{l} and \textbf{r} (\textbf{1} ≤ \textbf{l} ≤ \textbf{5000}, \textbf{1} ≤ \textbf{r} ≤ \textbf{10^9}).
\OutputFile
Output one number --- the number of different \textbf{2}-\textbf{3} trees with exactly \textbf{l} leaves modulo \textbf{r}.
Input example #1
6 1000000000
Output example #1
2