官解居然还是 TBD，只能自己写了。

同构的树出现次数显然相同，于是可以认为链上点的顺序已经固定了，最后再乘 $\frac{n!}{2}$。

我们考虑每次枚举一条出现最晚的边，合并两个连通块，要求另外两个连通块链上的边出现必须早于这条边，且这条边是连接这两个连通块边中最早出现的。于是考虑记 $f_{i,j}$ 为长为 $i$ 的链，链上最晚出现的边排名为 $j$，加边顺序的方案数。

转移考虑枚举左右两个链大小 $i,j$，它们链上边最晚出现时间 $k,l$，以及当前边的出现时间 $o$。再枚举一个 $h$ 表示左边这个连通块有多少条边在当前边之前出现，这样就确定了每种边在 $o$ 前后分别出现了多少次。于是有转移：

$$ f_{i+j,o}+f_{i,k}f_{j,l}(ij-1)!\sum_{k\le h\le \min(C(i),o-l-1)} \binom{o-1}{h}\binom{C(i+j)-o}{C(i)-h}\binom{C(i+j)-o-C(i)+h}{ij-1}\to f_{i+j,o} $$

其中 $C(i)=\frac{i(i-1)}{2}$。这样我们就得到了一个优秀的 $O(n^{10})$ 做法！

发现上述转移系数和 $k,l$ 无关，考虑调换枚举顺序，先枚举 $h$，合法的 $k,l$ 都是一个前缀，再把组合数拆开，得到如下转移：

$$ f_{i+j,o}+\sum_{0\le h\le \min(C(i),o-1)} s_{i,h}s_{j,o-h-1}\frac{(o-1)!(C(i+j)-o)!}{h!(o-h-1)!(C(i)-h)!(C(j)-o+h+1)!}\to f_{i+j,o} $$

其中 $s_{i,j}=\sum_{k\le j} f_{i,k}$。不难发现枚举 $h$ 这一维可以写成卷积形式，题目保证了模数是 NTT 模数，所以可以做到 $O(n^4\log n)$。

实际上我们做卷积的元素只有 $O(n^3)$ 个，于是没有必要每一次卷积都 NTT，我们先把元素 NTT 好，这样每次卷积都只需要对位相乘，最后再 INTT。时间复杂度 $O(n^4)$，常数很小，可以轻松通过。