CF809E.Surprise me!

Tired of boring dates, Leha and Noora decided to play a game.

Leha found a tree with n vertices numbered from 1 to n. We remind you that tree is an undirected graph without cycles. Each vertex v of a tree has a number a__v written on it. Quite by accident it turned out that all values written on vertices are distinct and are natural numbers between 1 and n.

The game goes in the following way. Noora chooses some vertex u of a tree uniformly at random and passes a move to Leha. Leha, in his turn, chooses (also uniformly at random) some vertex v from remaining vertices of a tree (v ≠ u). As you could guess there are n(n - 1) variants of choosing vertices by players. After that players calculate the value of a function f(u, v) = φ(a__u·a__v) · d(u, v) of the chosen vertices where φ(x) is Euler's totient function and d(x, y) is the shortest distance between vertices x and y in a tree.

Soon the game became boring for Noora, so Leha decided to defuse the situation and calculate expected value of function f over all variants of choosing vertices u and v, hoping of at least somehow surprise the girl.

Leha asks for your help in calculating this expected value. Let this value be representable in the form of an irreducible fraction . To further surprise Noora, he wants to name her the value .

Help Leha!

厌倦了无聊的约会，Leha 和 Noora 决定玩一个游戏。

Leha 找到了一棵包含 $ n $ 个顶点的树，顶点编号为 $ 1 $ 到 $ n $。我们提醒您：树是一种无环的无向图。树中每个顶点 $ v $ 上写有一个数 $ a_v $。巧合的是，所有顶点上的数值互不相同，且均为 $ 1 $ 到 $ n $ 之间的自然数。

游戏按如下方式进行：Noora 均匀随机地选择树中的某个顶点 $ u $，并将回合交给 Leha；Leha 随后也均匀随机地从树中剩余顶点（即除 $ u $ 外的顶点）中选择一个顶点 $ v $（即 $ v \ne u $）。如您所料，两名玩家选择顶点的方案总数为 $ n(n-1) $ 种。之后，双方计算所选顶点的函数值

$$f(u,\,v) = \varphi(a_u \cdot a_v) \cdot d(u,\,v),$$

其中 $ \varphi(x) $ 表示欧拉函数（Euler’s totient function），而 $ d(x,,y) $ 表示树中顶点 $ x $ 与 $ y $ 之间的最短距离。

很快，这个游戏让 Noora 感到乏味，于是 Leha 决定缓和局面，计算函数 $ f $ 在所有可能的顶点对 $ (u,,v) $ 上的期望值，希望能以某种方式给这位女孩带来一点惊喜。

Leha 请求您帮助他计算该期望值。设该期望值可表示为既约分数形式
。
为了进一步给 Noora 一个惊喜，他希望将该值命名为
。

请帮助 Leha！

The first line of input contains one integer number n (2 ≤ n ≤ 2·105) — number of vertices in a tree.

The second line contains n different numbers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ n) separated by spaces, denoting the values written on a tree vertices.

Each of the next n - 1 lines contains two integer numbers x and y (1 ≤ x, y ≤ n), describing the next edge of a tree. It is guaranteed that this set of edges describes a tree.

输入的第一行包含一个整数 $ n $（$ 2 \leq n \leq 2 \cdot 10^5 $）—— 表示树中顶点的数量。

第二行包含 $ n $ 个互不相同的整数 $ a_1, a_2, \dots, a_n $（$ 1 \leq a_i \leq n $），以空格分隔，表示写在树的各个顶点上的数值。

接下来的 $ n-1 $ 行中，每行包含两个整数 $ x $ 和 $ y $（$ 1 \leq x, y \leq n $），描述树的一条边。保证这些边构成一棵树。

In a single line print a number equal to P·Q - 1 modulo 109 + 7.

在一行中输出一个数，该数等于 $P \cdot Q^{-1} \bmod (10^9 + 7)$。

Euler's totient function φ(n) is the number of such i that 1 ≤ i ≤ n,and gcd(i, n) = 1, where gcd(x, y) is the greatest common divisor of numbers x and y.

There are 6 variants of choosing vertices by Leha and Noora in the first testcase:

• u = 1, v = 2, f(1, 2) = φ(_a_1·_a_2)·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) = φ(_a_1·_a_3)·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) = φ(_a_2·_a_3)·d(2, 3) = φ(2·3)·1 = φ(6) = 2
• u = 3, v = 2, f(3, 2) = f(2, 3) = 2

Expected value equals to . The value Leha wants to name Noora is 7·3 - 1 = 7·333333336 = 333333338 .

In the second testcase expected value equals to , so Leha will have to surprise Hoora by number 8·1 - 1 = 8 .

欧拉函数 $\varphi(n)$ 表示满足 $1 \leq i \leq n$ 且 $\gcd(i, n) = 1$ 的整数 $i$ 的个数，其中 $\gcd(x, y)$ 表示 $x$ 与 $y$ 的最大公约数。

在第一个测试用例中，Leha 和 Noora 选择顶点共有 6 种方案：

• $u = 1$, $v = 2$, $f(1, 2) = \varphi(a_1 \cdot a_2) \cdot d(1, 2) = \varphi(1 \cdot 2) \cdot 1 = \varphi(2) = 1$
• $u = 2$, $v = 1$, $f(2, 1) = f(1, 2) = 1$
• $u = 1$, $v = 3$, $f(1, 3) = \varphi(a_1 \cdot a_3) \cdot d(1, 3) = \varphi(1 \cdot 3) \cdot 2 = 2\varphi(3) = 4$
• $u = 3$, $v = 1$, $f(3, 1) = f(1, 3) = 4$
• $u = 2$, $v = 3$, $f(2, 3) = \varphi(a_2 \cdot a_3) \cdot d(2, 3) = \varphi(2 \cdot 3) \cdot 1 = \varphi(6) = 2$
• $u = 3$, $v = 2$, $f(3, 2) = f(2, 3) = 2$

期望值等于 。Leha 想告诉 Noora 的数值为 $7 \cdot 3^{-1} = 7 \cdot 333333336 = 333333338$ 。

在第二个测试用例中，期望值等于 ，因此 Leha 需要以数字 $8 \cdot 1^{-1} = 8$ 来让 Hoora 感到惊喜 。