나를 놀라게 해 줘!

지루한 데이트에 싫증이 난 Leha and Noora는 게임을 하기로 했다.

Leha는 1부터 n까지 번호가 매겨진 n개의 정점으로 이루어진 트리를 발견했다. 트리는 사이클이 없는 무방향 그래프임을 상기하자. 트리의 각 정점 v에는 수 av가 적혀 있다. 아주 우연히도 정점에 적힌 모든 값은 서로 다르며 1과 n 사이의 자연수였다.

게임은 다음과 같이 진행된다. Noora는 트리의 어떤 정점 u를 균등한 확률로 무작위 선택하고 Leha에게 차례를 넘긴다. 이어서 Leha도 트리 (v ≠ u)의 남은 정점 중 어떤 정점 v를 균등한 확률로 무작위 선택한다. 짐작할 수 있듯이 플레이어들이 정점을 선택하는 방법은 n(n - 1)가지이다. 그 후 플레이어들은 선택한 정점에 대한 함수 f(u, v) = φ(au·av) · d(u, v)의 값을 계산한다. 여기서 φ(x)는 오일러 피 함수이고, d(x, y)는 트리에서 정점 x와 y 사이의 최단 거리이다.

곧 Noora는 게임에 싫증을 냈고, Leha는 분위기를 누그러뜨리고 어떻게든 소녀를 조금이라도 놀라게 해 주고자 정점 u와 v를 선택하는 모든 방법에 대한 함수 f의 기댓값을 계산하기로 했다.

Leha는 이 기댓값을 계산하는 데 도움을 요청한다. 이 값을 기약분수 의 형태로 나타낼 수 있다고 하자. Noora를 더욱 놀라게 하기 위해 그는 그녀에게 값 을 알려 주고 싶어 한다.

Help Leha!

입력의 첫 번째 줄에는 트리의 정점 수를 나타내는 하나의 정수 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로 나눈 나머지와 같은 수를 출력한다.

오일러 피 함수 φ(n)는 1 ≤ i ≤ n이고 gcd(i, n) = 1인 i의 개수이다. 여기서 gcd(x, y)는 수 x와 y의 최대공약수이다.

첫 번째 테스트 케이스에서 Leha and 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

기댓값은 와 같다. Leha가 Noora에게 알려 주고 싶은 값은 7·3 - 1 = 7·333333336 = 333333338 이다.

두 번째 테스트 케이스의 기댓값은 과 같으므로, Leha는 Hoora를 수 8·1 - 1 = 8 로 놀라게 해야 한다.