厌倦了无聊的约会,Leha 和 Noora 决定玩一个游戏。
Leha 找到了一棵有 n 个顶点的树,编号从 1 到 n。我们提醒您,树是没有环的无向图。树的每个顶点 v 上都写有一个数字 av 。非常偶然的是,写在顶点上的所有值都是不同的,并且是 1 到 n 之间的自然数。
游戏按以下方式进行。 Noora 均匀随机选择树的某个顶点 u 并将移动传递给 Leha。 Leha 又从树的剩余顶点中选择(也是均匀随机地)某个顶点 v (v ≠ u)。正如您所猜测的,玩家选择顶点有 n(n - 1) 种变体。之后,玩家计算所选顶点的函数 f(u, v) = φ(au·av) · d(u, v) 的值,其中 φ(x) 是欧拉函数,d(x, y) 是树中顶点 x 和 y 之间的最短距离。
很快,游戏对 Noora 来说就变得无聊了,所以 Leha 决定化解这种情况,并计算函数 f 在选择顶点 u 和 v 的所有变体上的期望值,希望至少能以某种方式给女孩带来惊喜。
Leha 请求您帮助计算此期望值。令该值可以用不可约分数 $$\frac{p}{q}$$ 的形式表示。为了进一步让 Noora 感到惊讶,他想将她的值命名为 $$P \cdot Q^{-1} \mod 10^9 + 7$$。
帮助莱哈!
输入
输入的第一行包含一个整数 n (2 ≤ n ≤ 2·105) — 树中的顶点数。
第二行包含 n 个不同的数字 a1, a2, ..., an (1 ≤ ai ≤ n),用空格分隔,表示写在树顶点上的值。
接下来的 n - 1 行中的每一行都包含两个整数 x 和 y (1 ≤ x, y ≤ n),描述树的下一条边。保证这组边描述一棵树。
输出
在一行中打印一个等于 P·Q - 1 模 109 + 7 的数字。
示例
输入 #1
3 1 2 3 1 2 2 3
输出 #1
333333338
输入 #2
5 5 4 3 1 2 3 5 1 2 4 3 2 5
输出 #2
8
注意
欧拉 totient 函数 φ(n) 是满足 1 ≤ i ≤ n 且 gcd(i, n) = 1 的 i 的个数,其中 gcd(x, y) 是数字 x 和 y 的最大公约数。
在第一个测试用例中,Leha 和 Noora 有 6 种选择顶点的变体:
- u = 1,v = 2,f(1, 2) = Φ(a1·a2)·d(1, 2) = Φ(1·2)·1 = Φ(2) = 1
- u = 2,v = 1,f(2, 1) = f(1, 2) = 1
- u = 1,v = 3,f(1, 3) = Φ(a1·a3)·d(1, 3) = Φ(1·3)·2 = 2Φ(3) = 4
- u = 3,v = 1,f(3, 1) = f(1, 3) = 4
- u = 2,v = 3,f(2, 3) = Φ(a2·a3)·d(2, 3) = Φ(2·3)·1 = Φ(6) = 2
- u = 3,v = 2,f(3, 2) = f(2, 3) = 2
期望值等于 $${ \frac { 1 } { 6 } } \cdot ( 1 + 1 + 4 + 4 + 2 + 2 ) = { \frac { 1 4 } { 6 } } = { \frac { 7 } { 3 } }$$。 Leha 想要命名 Noora 的值为 7·3 - 1 = 7·333333336 = 333333338 $$\mod 10^9+7$$。
在第二个测试用例中,预期值等于 $$\frac{160}{20} = \frac{8}{1}$$,因此 Leha 必须用数字 8·1 - 1 = 8 $$\mod 10^9+7$$ 给 Hoora 带来惊喜。