cho.sh

뉴턴의 사과나무

아직 제출이 없습니다시간 제한4초메모리 제한1024 MB

문제

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

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

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

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

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

∑_i=1N\sum\_{i=1}^{N} (ii 번째 색깔로 색칠된 정점의 개수) ×\times (ii 번째 색깔로 색칠된 정점의 P_iP\_i 의 합)

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

입력

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

두 번째 줄에는 정점의 아름다움 수치 P_1,P_2,P_3,...,P_NP\_1, P\_2, P\_3, ..., P\_N 를 나타내는 정수 NN개가 공백으로 구분되어 주어집니다. (1≤P_i≤100)(1 \le P\_i \le 100)

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

출력

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