给出一棵$n(2 \le n \le 2 \times 10^5)$$个节点的树，边权为$1$。给定一个$1$到$n$的排列$a_i$，设$dist(i,j)$为树上两点间距离，求$$\frac{1}{n(n-1)}\sum_{i=1}^{n}\sum_{j=1}^{n} \varphi(a_i \cdot a_j) dist(i,j)\pmod{10^9+7}$$

考虑每个前缀有多少个后缀和它相等，可以用广义后缀自动机，也可以把哈希开到$\text{long long}$用$\text{unordered_map}$过。但这样直接算会算重，考虑去重：求出每个字符串的$\operatorname{next}$数组，则将$\operatorname{cnt}[\operatorname{next}[i]]$减去$\operatorname{cnt}[i]$即可。