2-3 Trees

$2$-$3$ tree is an elegant data structure invented by John Hopcroft. It is designed to implement the same functionality as the binary search tree. $2$-$3$ tree is an ordered rooted tree with the following properties:

• the root and each internal vertex have either $2$ or $3$ children;

• the distance from the root to any leaf of the tree is the same.

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 $l$ leaves has the height O(\log l).

Given the number of leaves $l$ there can be several valid $2$-$3$ trees that have $l$ leaves. For example, the picture below shows the two possible $2$-$3$ trees with exactly $6$ leaves.

Given $l$ find the number of different $2$-$3$ trees that have $l$ leaves. Since this number can be quite large, output it modulo $r$.