题目描述

最终，六花的设计完美解决了城市的交通问题——兼备登峰造极的效率和无可挑剔的低成本。不过她并不关心无聊的市政府是否赏识自己的方案——因为 LCR 已经在她身后等待许久了。这位少女正如传闻那般戴着花环，穿着白裙，带着纯净的微笑。六花渐渐意识到，这就是她所憧憬的相遇。于是她伸出手，开启了二人的旅程。她们的脚步穿过大街小巷，停在西工大附中的一间教室中。

白板和白纸上的公式令六花想起了她的学业——组合数学还要补考，于是她邀请 LCR 和自己玩一个游戏来复习。

游戏中，LCR 有一个 $n$ 阶排列，六花会尝试猜测它。具体来说，六花会先选定一组排列，接着 LCR 作出一些查询。每次查询中 LCR 给出一个区间 $[L, R] (1\le L, R\le n)$，六花需要回答在她选出的每个排列中这个区间是否是连续的（“连续”的定义见下文）。最终如果六花选定的排列中有一个与 LCR 的初始排列对于 LCR 的所有问题的答案都相同，六花就会获胜。

六花想知道，为了保证获胜，她至少要选多少个不同的排列。她想对每个不超过 $N$ 的正整数 $n$ 都求出答案。由于她认不清楚太大的数，你只需要输出答案对某个质数 $P$ 取模的结果即可。

区间 $[L,R]$ 在 $n$ 阶排列 $p$ 中连续当且仅当不存在三个整数 $x, y, z$ 使得 $1\le x,y,z\le n, p_x < p_y < p_z , x, z\in [L,R], y \notin [L,R]$，其中 $p_i$ 是一个 $[1,n]$ 中的整数，表示排列的第 $i$ 项。

输入格式

输入一行两个正整数 $N, P$，分别表示最大询问的排列阶数和模数。保证 $P$ 是质数。

输出格式

输出 $N$ 行每行一个自然数，第 $n$ 行的数表示排列为 $n$ 阶时为了保证获胜需选择的最小排列个数，对 $P$ 取模。

样例

input

10 65537

output

1
1
3
12
52
240
1160
5795
29681
23951

数据范围与提示

$1\le N\le 5000, 1\le P < 2^{30}, (\exists k\in \mathbb{N})(P = k\cdot 2^{14}+1)$

提示

当 $n=3$ 时，可能的排列和询问各有 $6$ 种，如下：

答案应该是 $3$，例如六花可以选择 $(1,2,3),(1,3,2),(2,1,3)$，这样无论 LCR 如何提问，她总有一个排列与 LCR 选择的排列回答相同。