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

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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

输入格式

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

输出格式

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

样例

样例输入 1

3 233

样例输出 1

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) :无特殊限制