保持连通

题目描述

给定整数 $N \geq 2$ 和素数 $P$。

考虑具有 $2N$ 个顶点和 $(3N-2)$ 条边的图 $G$。

具体来说,顶点标记为顶点 $1$,顶点 $2$,$\ldots$,顶点 $2N$,边标记为边 $1$,边 $2$,$\ldots$,边 $(3N-2)$,各边按如下方式连接顶点:

• 对于每个 $1\leq i\leq N-1$,边 $i$ 连接顶点 $i$ 和顶点 $i+1$。
• 对于每个 $1\leq i\leq N-1$,边 $(N-1+i)$ 连接顶点 $N+i$ 和顶点 $N+i+1$。
• 对于每个 $1\leq i\leq N$,边 $(2N-2+i)$ 连接顶点 $i$ 和顶点 $N+i$。

对每个 $i=1,2,\ldots ,N-1$,求解以下问题。

求从 $G$ 的 $3N-2$ 条边中恰好删除 $i$ 条边,使得剩余图仍然连通的方案数,对 $P$ 取模。

输入格式

输入按以下格式从标准输入给出：

N P

输出格式

输出 $N-1$ 个整数,第 $i$ 个整数为 $i=k$ 时的答案,用空格分隔。

样例

3 998244353

7 15

在 $N=3$ 的情况下,恰好删除一条边后仍保持连通的方案有 7 种。

恰好删除两条边后仍保持连通的方案有 15 种。

因此,应对 $P=998244353$ 取模后按顺序输出 $7$ 和 $15$。

16 999999937

46 1016 14288 143044 1079816 6349672 29622112 110569766 330377828 784245480 453609503 38603306 44981526 314279703 408855776

请务必输出对 $P$ 取模后的结果。

数据范围

• $2 \leq N \leq 3000$
• $9\times 10^8 \leq P \leq 10^9$
• $N$ 是整数。
• $P$ 是素数。