25052번 - 뉴턴의 사과나무

DGIST의 E1 건물 앞에는 뉴턴의 사과나무에서 네 번 접목한 나무가 심겨 있습니다. 

은하는 왜인지 모르게 앙상해 보이는 나무가 문득 불쌍하게 느껴졌습니다. 그래서 나무를 아름답게 색칠해 주려고 합니다.

나무는 $N$개의 정점을 가진 트리 형태로 표현할 수 있고, $1$번 정점을 루트로 가집니다. 은하는 $N$가지의 색깔을 이용해 아래와 같은 규칙에 따라 나무를 색칠하고자 합니다.

1. 아직 색이 칠해지지 않은 정점 중 가장 루트와 가까운 정점을 고릅니다. 그러한 정점이 여러 개가 있다면 가장 번호가 작은 정점을 고릅니다. 고른 정점의 번호를 $i$ 라고 할 때, $i$ 번째 색깔로 해당 정점을 색칠합니다.
2. $i$ 번 정점의 자식 중 아직 색칠되지 않은 정점들이 있다면, 그 정점들 중 하나를 균등한 확률로 골라서 $i$ 번째 색깔로 색칠합니다. 색칠한 정점의 자식 중 아직 색칠되지 않은 정점이 없다면 1번 과정으로 돌아가고, 아니라면 그 정점의 색칠되지 않은 자식 중 하나를 균등한 확률로 골라 $i$ 번째 색깔을 칠하는 것을 재귀적으로 반복합니다.
3. 1~2번 과정을 나무의 모든 정점이 색칠될 때까지 반복합니다.

나무의 각 정점은 아름다움 수치 $P_i$ 를 가지고 있습니다. 은하는 같은 색으로 칠해진 정점이 많을수록 아름다운 나무라고 생각하기 때문에, 아래 식처럼 트리의 아름다움을 정의했습니다.

$\sum_{i=1}^{N}$ ($i$ 번째 색깔로 색칠된 정점의 개수) $\times$ ($i$ 번째 색깔로 색칠된 정점의 $P_i$ 의 합)

은하는 나무를 가장 아름답게 만들어 주고 싶었지만, 미적 감각이 부족해서 그럴 수는 없다는 사실을 깨닫고 슬퍼졌습니다. 슬퍼하는 은하를 위해 대신 은하가 색칠한 나무의 아름다움의 기댓값을 구해줍시다.

첫 번째 줄에 나무의 정점 개수 $N$이 주어집니다. $(2 \le N \le 5 \times 10^3)$

두 번째 줄에는 정점의 아름다움 수치 $P_1, P_2, P_3, ..., P_N$ 를 나타내는 정수 $N$개가 공백으로 구분되어 주어집니다. $(1 \le P_i \le 100)$

세 번째 줄부터 $N+1$ 번째 줄에는 나무의 간선이 연결하고 있는 두 정점 $a, b$가 공백으로 구분되어 주어집니다. $(1 \le a, b \le N, a \neq b)$

첫 번째 줄에 나무의 아름다움의 기댓값을 기약분수로 나타낸 결과가 $\cfrac{p}{q}$ 일 때, $p \times q^{-1}$ 을 $1\ 000\ 000\ 007$로 나눴을 때의 나머지를 출력합니다. $q^{-1}$ 은 $q$ 를 $1\ 000\ 000\ 007$로 나눈 나머지 연산의 곱셈 역원입니다. 이 문제에서는 답이 존재하는 입력만 주어지는 것이 보장됩니다.