随

考虑使用原根将题目中的乘法转化为加法，那么这样直接可以得到一个 ( m{Theta(mod^3 log m)}) 的做法

首先根据期望的统计方式把题目变成统计多少种方案满足结果是 (x)

统计下来每个数的出现次数，得到一个多项式 (sum_{i=0}^{mod-1} a_ix^i)

那么矩阵快速幂里面的加法就可以转成多项式次数的加法，同时也可以通过这个方式统计方案数

然后 (mod) 很小，那么可以直接冲一个 (n^2) 的多项式乘法，指数上记得对 (mod-1) 取模就行了

熟练剖分

令 (f_{x,h}) 表示以 (x) 为根的子树里面 (h) 为轻边数量最大值的方案数

然后每次计数的时候钦定一个子树的深度然后乘起来剩下的

在归并子树的过程中，给 dp 数组多加一维，表示是否已经选择过重儿子即可。

时间复杂度 (Theta(n^2))，一般的暴力转移的实现优化之后不太好卡，也可以前缀和优化转移，那样实现难度不知道要高到哪里去