[ZJOI2022] 树
题目背景
一年一度的 ZJOI 又要举办了,但是老牌出题人九条可怜突然有急事要回趟英国。
“就交给你们啦!一定没有问题 desu!”,说完可怜就跑远了。
忍,爱丽丝,绫和阳子目送着远去的可怜,感到有点茫然,毕竞,ZJOI 只剩不到三星期了。
既然是可怜酱留下的任务,那我们一定要努力完成了,毕竟我才是姐姐”,爱丽丝说。
于是众人就开始热火朝天地出题了,“希望这是第一次也是最后一次了” 大家都不约而同地想。
同时,题目主角就定为九条可怜了!
题目描述
九条可怜是一个喜欢树的女孩子,她想生成两棵均有 $n$ 个节点的树。
第一棵树的生成方式是:
1. 节点 $1$ 作为树的根。
2. 对于 $i \in [2, n]$,从 $[1, i - 1]$ 中选取一个节点作为 $i$ 的父亲。
第二棵树的生成方式是:
1. 节点 $n$ 作为树的根。
2. 对于 $i \in [1, n - 1]$,从 $[i + 1, n]$ 中选取一个节点作为 $i$ 的父亲。
九条可怜希望对于任意 $i \in [1, n]$,若第一棵树中的节点 $i$ 为叶子,那么第二棵树中的节点 $i$ 为非叶子;若第一棵树中的节点 $i$ 为非叶子,那么第二棵树中的节点 $i$ 为叶子。一个节点被称为叶子当且仅当没有节点的父亲是它。
九条可怜希望你统计生成两棵树的方案数是多少。具体地,你需要对于所有 $n \in [2, N]$ 都计算方案数。两种方案不同当且仅当存在一棵树中的一个节点 $i$,两种方案中它的父亲不同。因为答案可能很大,你只需要输出答案对 $M$ 取模后的结果。
输入输出格式
输入格式
第一行输入两个整数 $N, M$,表示树的节点上限以及模数。
输出格式
输出 $N - 1$ 行,每行一个整数。
具体地,第 $i$ 行输出 $n = i + 1$ 时的答案对 $M$ 取模后的值。
输入输出样例
输入样例 #1
5 998244353
输出样例 #1
1
2
12
120
输入样例 #2
见附件中的 tree/tree_ex2.in
输出样例 #2
见附件中的 tree/tree_ex2.ans
说明
对于所有测试点:保证 $2 \le N \le 500$,$10 \le M \le 2^{30}$。
每个测试点的具体限制见下表:
| 测试点编号 | $N \le$ | 特殊限制 |
|:-:|:-:|:-:|
| $1$ | $10$ | 无 |
| $2$ | $20$ | 保证 $M$ 为质数 |
| $3$ | $50$ | 无 |
| $4$ | $50$ | 保证 $M$ 为质数 |
| $5$ | $100$ | 无 |
| $6$ | $100$ | 保证 $M$ 为质数 |
| $7$ | $500$ | 无 |
| $8$ | $500$ | 保证 $M$ 为质数 |
| $9$ | $500$ | 无 |
| $10$ | $500$ | 保证 $M$ 为质数 |