#P18286. Algebra

Algebra

Algebra

按如下经典方法构造一棵有 nn 个顶点的随机有根树:

  • 根为顶点 11。
  • 按顺序处理顶点 i=2,3,…,ni=2,3,\ldots,n。每次从 1,2,…,i−11,2,\ldots,i-1 中均匀随机选取一个顶点 pp,令 pp 成为顶点 ii 的父亲。

记顶点 uu 的子树大小为 sus_u,令 fu=sukf_u=s_u^k。对于每个 u=1,2,…,nu=1,2,\ldots,n,分别计算 fuf_u 的期望值,并对给定素数 MM 取模。

严格地说,在本题数据范围内,每个期望都可以表示为分数 p/qp/q,其中 qq 与 MM 互质。你需要输出 p⋅q−1 mod Mp\cdot q^{-1}\bmod M,这里 q−1q^{-1} 满足 qq−1≡1(modM)q q^{-1}\equiv1\pmod M。

输入格式

一行包含三个整数 n,k,Mn,k,M,满足:

$$1\le n\le10^5,\qquad1\le k\le200,\qquad10^8\le M\le10^9+7.$$

保证 MM 为素数。

输出格式

按 u=1,2,…,nu=1,2,\ldots,n 的顺序输出 nn 个整数,第 uu 个整数为 suks_u^k 的期望在模 MM 意义下的值。

样例 1

3 1 1000000007
3 500000005 1

样例 2

3 2 998244353
9 499122179 1