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$ 是质数。