Alternating Tree

1부터 n까지 번호가 매겨진 n개의 노드로 이루어진 트리가 주어진다. 각 노드 i에는 값 $V_i$가 대응되어 있다.

$u_1$에서 $u_m$까지의 단순 경로가 m개의 노드, 즉 $u_1$ → $u_2$ → $u_3$ → ... $u_{m-1}$ → $u_{m}$로 이루어져 있다면, 그 교대 함수 A($u_{1}$,$u_{m}$)는 A($u_{1}$,$u_{m}$) = ∑{i=1}^{m} (-1)^{i+1} ⋅ V{$u_{i}$}로 정의한다. 경로는 간선을 0개 가질 수도 있다. 즉, $u_{1}$=$u_{m}$일 수 있다.

서로 다른 모든 단순 경로의 교대 함수 합을 계산한다. 경로에는 방향이 있다는 점에 유의한다. 시작 정점이 다르거나 끝 정점이 다르면 두 경로는 서로 다른 것으로 간주한다. 답이 클 수 있으므로 $10^{9}$+7로 나눈 나머지를 계산한다.

첫 번째 줄에는 트리의 정점 수인 정수 n (2 ≤ n ≤ 2⋅$10^{5}$ )이 주어진다.

두 번째 줄에는 노드의 값인 공백으로 구분된 n개의 정수 $V_1$, $V_2$, …, $V_n$ (-$10^9$≤ $V_i$ ≤ $10^9$)이 주어진다.

다음 n-1개의 줄에는 각각 공백으로 구분된 두 정수 u와 v (1≤ u, v≤ n, u ≠ v)가 주어지며, 이는 정점 u와 v 사이의 간선을 나타낸다. 주어진 그래프가 트리임이 보장된다.

서로 다른 모든 단순 경로의 교대 함수의 총합을 $10^{9}$+7로 나눈 나머지를 출력한다.

첫 번째 예제를 살펴보자.

노드 1에서 노드 2로 가는 단순 경로 1 → 2의 교대 함수는 A(1,2) = 1 ⋅ (-4)+(-1) ⋅ 1 = -5이다.

노드 1에서 노드 3으로 가는 단순 경로 1 → 3의 교대 함수는 A(1,3) = 1 ⋅ (-4)+(-1) ⋅ 5 = -9이다.

노드 2에서 노드 4로 가는 단순 경로 2 → 1 → 4의 교대 함수는 A(2,4) = 1 ⋅ (1)+(-1) ⋅ (-4)+1 ⋅ (-2) = 3이다.

노드 1에서 노드 1로 가는 단순 경로에는 노드 1 하나만 있으므로 A(1,1) = 1 ⋅ (-4) = -4이다.

마찬가지로 A(2, 1) = 5, A(3, 1) = 9, A(4, 2) = 3, A(1, 4) = -2, A(4, 1) = 2, A(2, 2) = 1, A(3, 3) = 5, A(4, 4) = -2, A(3, 4) = 7, A(4, 3) = 7, A(2, 3) = 10, A(3, 2) = 10이다. 따라서 답은 (-5) + (-9) + 3 + (-4) + 5 + 9 + 3 + (-2) + 2 + 1 + 5 + (-2) + 7 + 7 + 10 + 10 = 40이다.

Similarly A(1,4)=-2, A(2,2)=1, A(2,1)=5, A(2,3)=10, A(3,3)=5, A(3,1)=9, A(3,2)=10, A(3,4)=7, A(4,4)=-2, A(4,1)=2, A(4,2)=3 , A(4,3)=7이며, 그 합은 40이다.