对于所有 $n$ 个节点的有根树，对每棵树的高度求和。答案对 $p$ 取模。

高度是指从根节点出发的最长简单路径的长度（即路径上的边数）。

两棵有根树相等，当且仅当它们的根节点的孩子数相等，且从左往右对应的子树也相等。

输入格式

输入两个整数 $n, p$。

输出格式

输出所有 $n$ 个节点的有根树的高度之和模 $p$ 的结果。

样例

样例 1 输入

4 998244353

样例 1 输出

10

样例 1 说明

对于样例 1：

• 有 $1$ 种高度为 $1$ 的树：根节点直接连接 $3$ 个叶子节点。
• 有 $3$ 种高度为 $2$ 的树：
  • 根节点有一个孩子，该孩子下连两个叶子节点。
  • 根节点有两个孩子，其中一个孩子是叶子节点。由于孩子有先后顺序，第一个孩子是叶子节点与第二个孩子是叶子节点视为两种不同的方案。
• 有 $1$ 种高度为 $3$ 的树：一条链。

样例 2 输入

10 998244353

样例 2 输出

19838

样例 3 输入

514 998244353

样例 3 输出

867876856

子任务

对于前 $20\%$ 的数据，$n\le 50$。

对于前 $40\%$ 的数据，$n\le 400$。

对于前 $60\%$ 的数据，$n\le 1000, p = 998244353$。

对于前 $80\%$ 的数据，$n\le 2000$。

对于 $100\%$ 的数据，$1\le n\le 10^5, 9\times 10^8 \le p\le 1.01 \times 10^9$，$p$ 是质数。