#P18422. Colonization
Colonization
Colonization
最近,Bytecja 开始殖民一片新发现的大陆及周围无数岛屿。当地居民并不欢迎殖民者的到来。
一座岛屿上有 个村庄,由 条双向道路连接,任意两个村庄之间均可相互到达。因此,村庄和道路构成一棵树。殖民过程如下:
起初, 名殖民者出现在他们自行选择的同一个村庄,使该村庄被殖民。之后,殖民者可以沿道路自由移动,也可以等待其他殖民者。只要一名殖民者到达某村庄,这个村庄就被殖民。
如果一座已被殖民的村庄没有殖民者留守,而它又与尚未被殖民的村庄相邻,当地居民就可能突袭它,造成悲惨的后果。必须始终避免这种情况。殖民者可以留在这座村庄守卫,也可以处在两座相邻村庄之间的道路上,因为当地居民绝不会绕过他。
对于给定的道路布局,问至少需要多少名殖民者:允许他们选择合适的起始村庄,并安排移动策略,最终殖民整座岛屿,同时始终保证上述安全要求。
现在给定村庄数 ,请对每个 ,求恰好需要 名殖民者的不同道路布局数量。
两个布局在其对应的树不同构时才视为不同,也就是要计算无标号、无根树的数量。具体而言,如果存在两个布局的村庄之间的一一对应,使得第一种布局中任意两个村庄之间有道路,当且仅当对应的两个村庄在第二种布局中也有道路,那么这两个布局相同。起始村庄由策略自由选择,并不是布局的一部分。
答案可能很大,请对给定的质数 取模。
输入格式
唯一一行包含两个整数 ,其中
保证 是质数。 为村庄数, 为模数。
输出格式
在一行中输出 个整数。第 个整数表示恰好需要 名殖民者的不同道路布局数量模 的值。即使后面的答案为零,也必须输出全部 项。
完整原样例
样例一输入:
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
样例说明与原图
第一个样例只有一种道路布局,如下图。只需一名殖民者,但他不能从中间村庄出发。

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

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