Time Limit: 6000/3000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

#### Problem Description

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

Input file contains two integer numbers: l and r (1 ≤ l ≤ 5 000, 1 ≤ r ≤ 10^{9}).

#### Output

Output one number — the number of different 2-3 trees with exactly l leaves modulo r.

#### Sample Input

6 1000000000
7 1000000000

#### Sample Output

#### Source

Andrew Stankevich Contest 21

#### Manager