Cho cây gồm ~N~ đỉnh. Với mỗi tập ~S = {x_1, …, x_K}~, tính tổng khoảng cách giữa mọi cặp đỉnh trong tập:

~F(S) = ∑_{1 ≤ i < j ≤ K} dist(x_i, x_j)~.

Ở đây ~dist(u,v)~ là số cạnh trên đường đi ngắn nhất giữa ~u~ và ~v~. In kết quả theo modulo ~10^9+7~.

Dữ liệu vào

• Dòng đầu chứa số nguyên ~N~ (~1 ≤ N ≤ 200000~).
• ~N-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ mô tả một cạnh vô hướng của cây. Các đỉnh đánh số từ ~1~ đến ~N~; mỗi cạnh có độ dài ~1~.
• Dòng tiếp theo chứa số nguyên ~Q~ (~1 ≤ Q ≤ 200000~).
• Tiếp theo là ~Q~ truy vấn độc lập. Mỗi truy vấn gồm một dòng chứa ~K~ (~1 ≤ K ≤ N~), tiếp theo là ~K~ số nguyên phân biệt ~x_1, x_2, …, x_K~ (~1 ≤ x_i ≤ N~) mô tả tập ~S~.

Kết quả

Với mỗi truy vấn, in ~F(S)~ modulo ~1000000007~.

Ví dụ

Input

7
1 2
1 3
2 4
2 5
3 6
3 7
1
3
4 5 7

Output

10

Ràng buộc

• Subtask 1: ~N, Q ≤ 1000~.
• Subtask 2: ~K=N~ với mọi truy vấn.
• Subtask 3: ~∑K ≤ 200000~.

Quy cách chấm

Đọc từ đầu vào chuẩn, ghi ra đầu ra chuẩn. Có 50 test độc lập, mỗi test 2 điểm; tổng điểm là 100. Không chấm theo batch. Thời gian: 3 giây; bộ nhớ: 512 MiB.

Nguồn: Lưu Hải Phong — hpcode.edu.vn.