E: 可以出生成树计数相关吗[吃瓜.jpg]

X: 别

E: 啊，主要是今天弄出来一个求一种特别的矩阵的行列式的东西

X: 来个一般难度的推式子题即可

对于所有 $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$ 是质数。