#P18653. Is This FFT?

Is This FFT?

Is This FFT?

考虑如下生成一棵有 nn 个有标号顶点的随机树的方法:

取出所有 n(n−1)/2n(n-1)/2 条可能的无向边,并在这些边的所有排列中等概率地选择一个。开始时图中没有边,按照选定排列的顺序依次考察每条边:如果这条边连接两个不同的连通分量,就把它加入图中。最终得到一棵树。

给定 NN 和 PP,请对每个 n=2,3,…,Nn=2,3,\ldots,N,求最终的树是一条链的概率,并对 PP 取模。链指所有顶点的度数都不超过 22 的树。

保证 PP 是素数,且 P mod 216=1P\bmod 2^{16}=1。

输入格式

唯一一行包含两个整数 N,PN,P。

  • 2≤N≤2502\le N\le250;
  • 2<P<1092<P<10^9;
  • PP 为素数,P mod 65536=1P\bmod65536=1。

输出格式

输出 N−1N-1 个整数,依次为 n=2,3,…,Nn=2,3,\ldots,N 的答案。

若某个概率的最简分数为 u/vu/v,且 vv 与 PP 互素,则它对 PP 取模的结果定义为 u⋅v−1 mod Pu\cdot v^{-1}\bmod P,其中 v−1v^{-1} 为 vv 在模 PP 意义下的乘法逆元。

样例输入

10 998244353

样例输出

1
1
532396989
328786831
443364983
567813846
34567523
466373946
474334062