Cho một cây có $N$ nút và $N - 1$ cạnh, trong đó mỗi cạnh $i$ có mức độ phức tạp $l_i$. Khoảng cách $d(u, v)$ giữa hai nút $u$ và $v$ là tổng mức độ phức tạp dọc theo đường đi duy nhất giữa chúng trên cây. Lưu ý rằng $d(u, v) = d(v, u)$ và $d(v, v) = 0$.

Có $M$ câu đố, và mỗi câu đố $i$ đòi hỏi $k_i$ mảnh thông tin nằm dọc theo các cạnh cụ thể trên cây. Có thể có nhiều mảnh thông tin nằm trên cùng một cạnh!

Với hai nút bất kỳ $S$ và $T$, một hành trình giữa $S$ và $T$ là thành công nếu dọc theo đường đi từ $S$ đến $T$, tất cả các mảnh thông tin cần thiết cho bất kỳ câu đố nào gặp phải đều được thu thập. Cụ thể, một câu đố được coi là giải được trong hành trình nếu tất cả các mảnh thông tin cần thiết cho câu đố đó đều được bắt gặp dọc theo đường đi.

Nhiệm vụ là tính tổng khoảng cách của tất cả các hành trình thành công giữa hai nút bất kỳ $S$ và $T$ (với $1 \le S \le T \le N$), theo modulo $10^9 + 7$.

Một cách hình thức, nhiệm vụ là tính:

$$\sum_{\substack{1 \le S \le T \le N, \\ \text{journey } (S, T) \text{ is successful}}} d(S, T)$$

Bắt đầu từ một nút $S$, bạn cần di chuyển đến một nút khác $T$ dọc theo đường đi duy nhất trên cây. Trên đường đi, bất kỳ mảnh thông tin nào nằm trên các cạnh của đường đi này sẽ tự động được thu thập. Để hành trình từ $S$ đến $T$ được coi là thành công, nó phải thỏa mãn điều kiện sau:

• Gọi $O$ là tập hợp các câu đố mà ít nhất một mảnh thông tin đã được thu thập trong suốt hành trình. Hành trình là thành công khi và chỉ khi tất cả các mảnh thông tin cần thiết để giải mọi câu đố trong tập hợp $O$ đều đã được thu thập. Nói cách khác, bạn phải thu thập đủ mọi mảnh thông tin cần thiết để giải hoàn toàn từng câu đố trong $O$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách $N$ và $M$ ($2 \le N \le 10^6, 1 \le M \le 10^6$).

Sau đó là $N - 1$ dòng, mỗi dòng chứa ba số nguyên cách nhau bởi dấu cách $a_i, b_i, l_i$ ($1 \le a_i, b_i \le N, 1 \le l_i \le 10^9$), mô tả cạnh $i$ nối hai nút $a_i$ và $b_i$ với độ phức tạp $l_i$.

Tiếp theo là định nghĩa của $M$ câu đố. Với mỗi câu đố $i$, dữ liệu vào gồm một dòng chứa $k_i$ theo sau là $k_i$ số nguyên cách nhau bởi dấu cách $u_{i_1}, u_{i_2}, \dots, u_{i_{k_i}}$ ($0 \le k_i \le K, 1 \le u_{i_j} \le N - 1$), trong đó $u_{i_j}$ là chỉ số của các cạnh chứa các mảnh thông tin cần thiết để giải câu đố.

Ở đây, $K$ là tổng tất cả các giá trị $k_i$ trên mọi câu đố, và đảm bảo rằng $1 \le K \le 10^6$.

Dữ liệu ra

In ra một dòng chứa một số nguyên là đáp án của bài toán theo modulo $10^9 + 7$.

Ví dụ

Dữ liệu vào 1

5 4
1 2 3
1 4 1
1 5 6
4 3 2
2 4 4
1 1
0
2 3 4

Dữ liệu ra 1

17

Ghi chú

Hình 1. Cấu trúc của cây. Các hình thoi là các mảnh thông tin, và các giá trị trên các cạnh là độ phức tạp.