题目描述

$2$ 以上の整数 $N$ および素数 $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$ 個の整数を空白区切りで出力せよ。 ただし、$k$ 番目の整数は $i=k$ に対する答えである。

题目大意

给定 $n, p$，存在如图的 $2 \times n$ 的网格图，显然初始共有 $2n$ 个顶点和 $3n - 2$ 条边，分别求删除 $i \in [1, n - 1]$ 条边后仍使图连通的删边方案数，对 $p$ 取模。

3 998244353

7 15

16 999999937

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

提示

制約

• $2\ \leq\ N\ \leq\ 3000$
• $9\times\ 10^8\ \leq\ P\ \leq\ 10^9$
• $N$ は整数である。
• $P$ は素数である。

Sample Explanation 1

$N=3$ の場合について、取り除いた後のグラフも連結となるように、ちょうど $1$ 本の辺を取り除く方法は次の $7$ 通りです。  取り除いた後のグラフも連結となるように、ちょうど $2$ 本の辺を取り除く方法は次の $15$ 通りです。  よって、これらを $P=998244353$ で割ったあまりである $7$, $15$ をこの順に出力します。

Sample Explanation 2

$P$ で割ったあまりを出力することに注意してください。