#P18422. Colonization

Colonization

Colonization

最近,Bytecja 开始殖民一片新发现的大陆及周围无数岛屿。当地居民并不欢迎殖民者的到来。

一座岛屿上有 nn 个村庄,由 n−1n-1 条双向道路连接,任意两个村庄之间均可相互到达。因此,村庄和道路构成一棵树。殖民过程如下:

起初,kk 名殖民者出现在他们自行选择的同一个村庄,使该村庄被殖民。之后,殖民者可以沿道路自由移动,也可以等待其他殖民者。只要一名殖民者到达某村庄,这个村庄就被殖民。

如果一座已被殖民的村庄没有殖民者留守,而它又与尚未被殖民的村庄相邻,当地居民就可能突袭它,造成悲惨的后果。必须始终避免这种情况。殖民者可以留在这座村庄守卫,也可以处在两座相邻村庄之间的道路上,因为当地居民绝不会绕过他。

对于给定的道路布局,问至少需要多少名殖民者:允许他们选择合适的起始村庄,并安排移动策略,最终殖民整座岛屿,同时始终保证上述安全要求。

现在给定村庄数 nn,请对每个 k=1,2,…,nk=1,2,\ldots,n,求恰好需要 kk 名殖民者的不同道路布局数量。

两个布局在其对应的树不同构时才视为不同,也就是要计算无标号、无根树的数量。具体而言,如果存在两个布局的村庄之间的一一对应,使得第一种布局中任意两个村庄之间有道路,当且仅当对应的两个村庄在第二种布局中也有道路,那么这两个布局相同。起始村庄由策略自由选择,并不是布局的一部分。

答案可能很大,请对给定的质数 pp 取模。

输入格式

唯一一行包含两个整数 n,pn,p,其中

2≤n≤500,108+7≤p≤109+7.2\le n\le500,\qquad 10^8+7\le p\le10^9+7.

保证 pp 是质数。nn 为村庄数,pp 为模数。

输出格式

在一行中输出 nn 个整数。第 kk 个整数表示恰好需要 kk 名殖民者的不同道路布局数量模 pp 的值。即使后面的答案为零,也必须输出全部 nn 项。

完整原样例

样例一输入:

3 100000007

输出:

1 0 0

样例二输入:

6 300000007

输出:

1 5 0 0 0 0

样例三输入:

10 1000000007

输出:

1 104 1 0 0 0 0 0 0 0

样例说明与原图

第一个样例只有一种道路布局,如下图。只需一名殖民者,但他不能从中间村庄出发。

三个村庄的唯一布局,原题图

第二个样例共有六种道路布局,如下图。只有左上角的布局能由一名殖民者完成殖民,其余五种都恰好需要两名。以中间一行右侧的布局为例,两人可以从最左侧村庄同时出发,向右共同移动两个村庄;随后一人留守,另一人依次殖民剩余三个村庄。

六个村庄的全部六种布局,原题图

第三个样例恰有一种布局需要三名殖民者,如下图。

十个村庄中唯一需要三名殖民者的布局,原题图