最终，Rikka 得到了一个既能创造高效流量又花费甚少的绝佳设计。但 Rikka 并不在乎那些陈腐的官员是否接受它——LCR 已经陪伴她很久了，带着纯真的微笑、花环和白裙。在微笑的安抚下，女孩们牵起手，开始了她们的旅程。在这次浪漫的会面后，她们最终来到了西北工业大学附属中学的一间自习室。
白板和纸上的公式提醒了 Rikka（当然是关于她的学习），所以她现在要求 LCR 和她玩一个游戏（为了复习组合数学）。
LCR 有一个 $n$ 阶排列，Rikka 试图猜出它。起初，Rikka 应该选择一组 $n$ 阶排列。然后 LCR 会进行一些询问。每次，LCR 给出一个区间 $[L, R]$ ($1 \le L \le R \le n$)，对于每个选定的排列，Rikka 都要回答该区间在其中是否是“连续的”（定义见下文）。最后，当且仅当存在一个选定的排列，其对每个询问的回答都与 LCR 的原始排列一致时，Rikka 赢得游戏。
Rikka 想知道她至少需要选择多少个排列才能确保赢得游戏。对于未来的游戏，她需要知道每个不大于 $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$ ($i = 1, 2, \dots, n$) 是排列 $p$ 中的第 $i$ 个元素，且 $p_i \in [1, n]$。
输入格式
仅一行，包含两个整数 $N$ ($1 \le N \le 5000$) 和 $P$ ($1 \le P < 2^{30}, \exists k \in \mathbb{N}, P = k \cdot 2^{14} + 1$)，分别表示排列的最大阶数和除数，中间用空格隔开。保证 $P$ 是素数。
输出格式
输出 $N$ 行；对于 $n = 1, 2, \dots, N$，第 $n$ 行包含一个整数，表示 Rikka 对于 $n$ 阶排列至少需要选择的排列数量，对 $P$ 取模。
样例
输入 1
10 65537
输出 1
1 1 3 12 52 240 1160 5795 29681 23951
说明
如果 $n = 3$，共有 6 种排列和 6 种可能的询问。在这些情况下，Rikka 的回答如下：
| (1, 2, 3) | (1, 3, 2) | (2, 1, 3) | (2, 3, 1) | (3, 1, 2) | (3, 2, 1) | |
|---|---|---|---|---|---|---|
| [1, 1] | True | True | True | True | True | True |
| [2, 2] | True | True | True | True | True | True |
| [3, 3] | True | True | True | True | True | True |
| [1, 2] | True | False | True | True | False | True |
| [2, 3] | True | True | False | False | True | True |
| [1, 3] | True | True | True | True | True | True |
答案应该是 3。例如，Rikka 可以选择 (1, 2, 3), (1, 3, 2), (2, 1, 3)，这样无论 LCR 持有哪种排列，都存在一个选定的排列，其对每个询问的回答与 LCR 的一致。