Time Limit: 6000/3000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
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.
Input file contains two integer numbers: l and r (1 ≤ l ≤ 5 000, 1 ≤ r ≤ 109).
Output one number — the number of different 2-3 trees with exactly l leaves modulo r.
Andrew Stankevich Contest 21