Migrated from Lutece 478 Counting Binary Trees

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There are $5$ distinct binary trees of $3$ nodes

.

Let $T(n)$ be the number of distinct non-empty binary trees of no more than $n$ nodes, your task is to calculate $T(n)\ mod\ m$

Input

The input contains at most $10$ test cases. Each case contains two integers $n$ and $m$ ($1 \leq n \leq 100,000$, $1 \leq m \leq 10^9$) on a single line. The input ends with $n = m = 0$.

Output

For each test case, print $T(n)\ mod\ m$.

Samples

3 100
4 10
0 0

8
2

Resources

2011 UESTC ACM Training for Math