[AdditionalFile6495.zip](file://AdditionalFile6495.zip?type=additional_file)

#6495. 「雅礼集训 2018 Day1」树

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

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

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

输入格式

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

输出格式

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

样例

输入

3 233

输出

3
119

数据范围与提示

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

• 子任务 $\rm 1(points: 10)$：$n \leq 10, p \leq 10^6 + 7$
• 子任务 $\rm 2(points: 10)$：$n \leq 12$
• 子任务 $\rm 3(points: 50)$：$n \leq 18$
• 子任务 $\rm 4(points: 30)$：无特殊限制