3834. [雅礼集训 2018 Day1] 树

【题目描述】

有一棵 $n$ 个点的有根树，点编号为 $1 \sim n$，其中 $1$ 号点为根，除 $1$ 号点外，$i$ 号点的父亲在 $1$ 至 $i - 1$ 内均匀随机。

定义一棵树的深度为所有节点到根路径上节点数的最大值，求这棵树的期望深度。

【输入格式】

输入包含一行两个正整数 $n, p，p$ 的意义见输出格式。

【输出格式】

输出包含两行，每行一个非负整数，第一行表示答案四舍五入成整数的值，第二行表示答案在模 $p$ 意义下的值。

【样例1输入】

3 233

【样例1输出】

3
119

【样例2/3/4】

点击下载样例2/3/4

【数据规模与约定】

测试点 $1 \sim 6$：$1 \leq n \leq 10$；

测试点 $7 \sim 14$：$1 \leq n \leq 18$；

对于 $100\%$ 的数据，$1 \leq n \leq 24, 100 \leq p \leq 10^9 + 7, p$ 为质数。