P12495 [集训队互测 2024] 链覆盖

你的学弟向你请教这样一道题： - 给定一颗 $n$ 个点的有根树，初始所有点均为白色。 - 你可以执行不超过 $k$ 次操作，每次操作为选定一个点，把它到根简单路径上的所有点涂成黑色。 - 求你最终最多能涂黑多少点。对 $k=1 \sim n$ 分别求解。 这当然不是什么难题，你很快向学弟解释清楚了这应该怎么做，他惊叹于做法的巧妙，然后满意地离开了。 你看着他离去的身影，想起两三年前，你第一次得知这道题怎么做时，也曾为这道题的解法赞叹过。但对于现在的你来说，这也并没有什么神奇之处，只是一个平凡的套路罢了。 但熟知的原题与结论并不一定真的就乏味无趣、无甚可观，这样想着，你记录下了这道题：

- 给定一颗 $n$ 个点的有根树，初始所有点均为白色。 - 你可以执行不超过 $k$ 次操作，每次操作为选定一个点，把它到根简单路径上的所有点涂成黑色。 - 求你最终最多能涂黑多少点。对 $k=1 \sim n$ 分别求解。 记对于有标号有根树 $T$，上述问题在 $k=i$ 时的答案为 $ans(T,i)$。 给定 $n,mod$，对所有 $1 \le k \le n,1 \le m \le n$，计算有多少不同的 $n$ 个点以 $1$ 为根的有标号树 $T$ 满足 $ans(T,k)=m$。答案对 $mod$ 取模。 两颗有标号以 $1$ 为根的树被认为是不同的，当且仅当它们的边集不同。

一行两个整数 $n,mod$。

输出 $n$ 行每行 $n$ 个整数，第 $k$ 行的第 $m$ 个整数表示满足 $ans(T,k)=m$ 的不同的 $n$ 个点以 $1$ 为根的有标号树 $T$ 的数量对 $mod$ 取模的结果。

本题使用捆绑测试，你只有通过一个子任务的所有测试点，才能获得这个子任务的分数。 | Subtask | $n \le$ | 分值 | | :-----: | :-----: | :--: | | $1$ | $5$ | $1$ | | $2$ | $10$ | $9$ | | $3$ | $20$ | $10$ | | $4$ | $32$ | $15$ | | $5$ | $40$ | $5$ | | $6$ | $50$ | $15$ | | $7$ | $65$ | $5$ | | $8$ | $80$ | $5$ | | $9$ | $120$ | $15$ | | $10$ | $300$ | $20$ | 对于所有数据：$1 \le n \le 300$，$10^8 \le mod \le 1.05 \times 10^9$，保证 $mod$ 是质数。