B-完美主义追求者_牛客练习赛133

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 有一位福建的 acmer 是某知名网站的管理员，他非常喜欢说一个中文二字英文七字的词语。当然，他说的是“完美”（Perfect）。

$\hspace{15pt}$ 如果你不认识他也没关系，我们这里有一个关于完美的问题，你能够解决她吗？

$\hspace{15pt}$

$\hspace{15pt}$ 小有有一棵有着 $n$ 个节点的树，节点编号依次为 $1,2,\dots,n$ 。她定义这棵树是“完美的”，当且仅当这棵树同时满足：

$\hspace{23pt}\bullet\,$ 编号为 $1$ 的节点是根节点；
$\hspace{23pt}\bullet\,$ 除根节点外，其余所有节点都恰好有一个父节点；
$\hspace{23pt}\bullet\,$ 每个节点最多有两个子节点，位于左边的子节点称为左子节点，位于右边的子节点称为右子节点；
$\hspace{23pt}\bullet\,$ 如果存在子节点，其子节点的编号一定大于其本身的编号。

$\hspace{15pt}$ 两棵树 $t_1$ 和 $t_2$ 被认为是本质不同的，如果满足以下任一条件：
$\hspace{23pt}\bullet\,$ 树的结构不同：某个位置在一棵树中有节点而另一棵树中没有；
$\hspace{23pt}\bullet\,$ 左子节点的分配不同：存在一个节点，其在 $t_1$ 和 $t_2$ 中的左子节点值不同；
$\hspace{23pt}\bullet\,$ 右子节点的分配不同：存在一个节点，其在 $t_1$ 和 $t_2$ 中的右子节点值不同。
$\hspace{15pt}$ 例如，在下图中，树虽然都由两个节点构成，但是在左图中节点 $2$ 是节点 $1$ 的左子节点，而在右图中节点 $2$ 是节点 $1$ 的右子节点，这被看作是左右子节点的分配不同。

$\hspace{15pt}$ 现在，对于给定的整数 $p$ ，小有想求出模 $p$ 意义下本质不同的有 $n$ 个节点的完美的树的数量。你能帮帮她吗？

输入描述:

在一行上输入两个整数  代表树的节点数、取模的数。

输出描述:

输出一个整数，表示模  意义下本质不同的有  个节点的完美树的数量。

示例1

输入

复制

2 1000000

输出

复制

说明

在这个样例中，两棵本质不同的完美树如下：

示例2

输入

复制

114 191981

输出

复制

备注:

在几乎全部的情况下， 的运行速度优于 ，我们建议您选择对应版本的  进行提交、而不是 。