Cho một cây gồm \(n\) nút được đánh số từ 1 đến \(n\). Mỗi nút \(i\) có giá trị liên kết \(V_i\).

Nếu đường đi đơn giản từ \(u_1\) đến \(u_m\) gồm \(m\) nút, lần lượt

\[ u_1 → u_2 → u_3 → … → u_{m-1} → u_m \]

thì hàm xen kẽ \(A(u_1, u_m)\) được định nghĩa như sau:

\[ A(u_1, u_m) = \sum_{i=1}^{m} (-1)^{i+1} \cdot V_{u_i}. \]

Đường đi cũng có thể không có cạnh nào (tức \(m=1\), \(u_1 = u_m\)).

Hãy tính tổng các giá trị hàm xen kẽ của tất cả các đường đi đơn giản có hướng. Lưu ý rằng hai đường đi được coi là khác nhau nếu nút bắt đầu hoặc nút kết thúc khác nhau. Kết quả có thể rất lớn, hãy in ra theo modulo \(10^9 + 7\).

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(n\) (\(2 \le n \le 2\cdot10^5\)) — số lượng đỉnh của cây.
• Dòng thứ hai chứa \(n\) số nguyên \(V_1, V_2, \dots, V_n\) (\(-10^9 \le V_i \le 10^9\)) — giá trị của các nút.
• \(n-1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u\) và \(v\) (\(1 \le u, v \le n\), \(u \neq v\)) mô tả một cạnh nối hai đỉnh \(u\) và \(v\). Đảm bảo đồ thị đầu vào là một cây.

Dữ liệu ra

• In ra tổng các giá trị hàm xen kẽ của tất cả các đường đi đơn giản có hướng, theo modulo \(10^9 + 7\).

Input 1

4
-4 1 5 -2
1 2
1 3
1 4

Output 1

40

Input 2

8
-2 6 -4 -4 -9 -3 -7 23
8 2
2 3
1 4
6 5
7 6
4 7
5 8

Output 2

4