Bạn được cho một cây (đồ thị vô hướng liên thông không có chu trình) gồm ~n~ đỉnh đánh số ~1, 2, \dots, n~ và một dãy số nguyên dương ~a_1, a_2, \dots, a_n~. Nhiệm vụ của bạn là tìm một hoán vị ~p_1, p_2, \dots, p_n~ của ~\{1, 2, \dots, n\}~. Sau đó với mỗi đỉnh ~i~ gán giá trị ~a_{p_i}~ cho đỉnh này.

Giá trị của một đường đi giữa hai đỉnh ~u~ và ~v~ được tính bằng tổng các giá trị đã gán cho các đỉnh trên đường đi này (gồm cả đỉnh ~u~ và ~v~).

Yêu cầu: Tính giá trị lớn nhất của tổng giá trị các con đường từ một đỉnh lá đến một đỉnh lá khác (đỉnh lá là đỉnh chỉ nối duy nhất với một đỉnh khác). Do giá trị này có thể rất lớn nên chỉ cần lấy phần dư của nó khi chia cho ~10^9 + 7~.

Input

Dòng đầu tiên chứa số nguyên dương ~T~ ~(T \le 1000)~ biểu diễn số lượng bộ dữ liệu. Tiếp theo là ~T~ nhóm dòng, mỗi nhóm gồm ~n+1~ dòng mô tả một bộ dữ liệu có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(3 \le n \le 3 \cdot 10^5)~;

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(a_i \le 10^9; 1 \le i \le n)~;

• Mỗi dòng trong ~n-1~ dòng cuối cùng chứa hai số nguyên dương ~u, v~ thể hiện có một cạnh của cây nối hai đỉnh ~u, v~ ~(1 \le u, v \le n; u \ne v)~;

• Các số trên cùng một dòng cách nhau bởi dấu cách. Tổng giá trị ~n~ trong tất cả các bộ dữ liệu không vượt quá ~5 \cdot 10^5~.

Output

• Với mỗi bộ dữ liệu in ra trên một dòng một số nguyên duy nhất là kết quả tìm được.

Scoring

Sample Input 1

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

Sample Output 1

24
15

Notes

Với test ~1~, hoán vị ~p~ thỏa mãn là: ~(1, 4, 3, 2)~. Trọng số được gán cho các đỉnh ~1, 2, 3, 4~ lần lượt là ~1, 4, 3, 2~.

• Giá trị đường đi từ đỉnh lá ~1~ đến đỉnh lá ~3~ là ~1 + 4 + 3 = 8~.

• Giá trị đường đi từ đỉnh lá ~1~ đến đỉnh lá ~4~ là ~1 + 4 + 2 = 7~.

• Giá trị đường đi từ đỉnh lá ~3~ đến đỉnh lá ~4~ là ~3 + 4 + 2 = 9~.

Tổng giá trị các đường đi là: ~8 + 7 + 9 = 24~.