题目描述

有一棵 (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) 为质数。