题目描述

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

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

输入格式

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

输出格式

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

样例

input

3 233

output

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