题目描述

给定正整数 $N$ 和素数 $P$。

$\forall K=0,1,\ldots,N$，求出满足以下条件的简单有向图的数量：

• 图中仅包含 $i\to j$（$1\le i\lt j\le N$）的边；
• 满足以下条件的点 $u$ 恰好有 $K$ 个：
  • 存在 $1\to u$ 和 $u\to N$ 的路径。

只需要输出答案对 $P$ 取模后的结果。

输入格式

$N$ $P$

输出格式

输出一行 $(N+1)$ 个非负整数，第 $i$ 个数表示 $K=i-1$ 时的答案。

输入输出样例 #1

输入 #1

2 1000000007

输出 #1

1 0 1

输入输出样例 #2

输入 #2

3 1000000007

输出 #2

3 0 3 2

输入输出样例 #3

输入 #3

5 1000000007

输出 #3

183 0 183 286 250 122

说明/提示

样例解释

样例 $2$ 解释：

$K=0$ 的时候，根据定义，下面三个边集合法：

• $\varnothing$；
• $\{(1, 2)\}$；
• $\{(2, 3)\}$。

$K=2$ 时，合法的边集：

• $\{(1, 3)\}$；
• $\{(1, 3), (1, 2)\}$；
• $\{(1, 3), (2, 3)\}$。

$K=3$ 时，合法的边集：

• $\{(1, 2), (2, 3)\}$；
• $\{(1, 2), (1, 3), (2, 3)\}$。

数据范围

• $2\le N\le 2\,000$；
• $10^8\le P\le 10^9+100$；
• $P$ 是素数。

子任务

子任务 $0$ 为样例。