给出一棵$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) \operatorname{dist}(i,j)\pmod{10^9+7}$$

因为$a_i$是$1$到$n$的排列，所以我们可以设$p_{a_i}=i$。同时有以下结论$$\varphi(nm)=\frac{\varphi(n)\varphi(m)\gcd(n,m)}{\varphi(\gcd(n,m))}$$ 因此扔掉前面的分母$n(n-1)$，原式转化为$$\sum_{i=1}^{n}\sum_{j=1}^{n} frac{\varphi(i)\varphi(j)\gcd(i,j)\operatorname{dist}(p_i, p_j)}{\varphi(\gcd(i,j))} $$