#6632. 「EC Final 2018」神秘的……东道主 / Mysterious … Host

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

题目描述

最终,六花的设计完美解决了城市的交通问题——兼备登峰造极的效率和无可挑剔的低成本。不过她并不关心无聊的市政府是否赏识自己的方案——因为 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 取模。

样例

样例输入 1

10 65537

样例输出 1

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 种,如下:

(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
[2,2]
[3,3]
[1,2] False False
[2,3] True False True
[1,3] True

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