$N$개의 노드와 $N - 1$개의 간선으로 이루어진 트리가 주어지며, 각 간선 $i$는 복잡도 $l_i$를 가집니다. 두 노드 $u$와 $v$ 사이의 거리 $d(u, v)$는 트리에서 두 노드를 잇는 유일한 경로상의 간선들의 복잡도 합입니다. 참고로 $d(u, v) = d(v, u)$이고 $d(v, v) = 0$입니다.

$M$개의 퍼즐이 있으며, 각 퍼즐 $i$는 $k_i$개의 정보 조각을 필요로 합니다. 이 정보 조각들은 트리의 특정 간선들 위에 위치해 있습니다. 같은 간선 위에 여러 개의 정보 조각이 있을 수도 있습니다!

임의의 두 노드 $S$와 $T$에 대해, $S$에서 $T$로 가는 경로를 따라 마주친 모든 퍼즐에 대해 필요한 정보 조각들이 모두 수집되었다면 $S$와 $T$ 사이의 여정은 성공적입니다. 구체적으로, 어떤 퍼즐에 필요한 모든 정보 조각을 경로상에서 마주쳤다면 그 퍼즐은 여정 중에 풀 수 있는 것으로 간주됩니다.

과제는 임의의 두 노드 $S$와 $T$ ($1 \le S \le T \le N$) 사이의 모든 성공적인 여정에 대한 거리들의 합을 $10^9 + 7$로 나눈 나머지를 구하는 것입니다.

공식적으로, 계산해야 하는 값은 다음과 같습니다:

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

노드 $S$에서 출발하여 트리의 유일한 경로를 따라 다른 노드 $T$로 이동해야 합니다. 이동하는 동안 이 경로의 간선 위에 있는 모든 정보 조각은 자동으로 수집됩니다. $S$에서 $T$까지의 여정이 성공적인 것으로 간주되려면 다음 조건을 만족해야 합니다:

• 여정 중에 적어도 하나의 정보 조각이 수집된 퍼즐들의 집합을 $O$라고 합시다. 집합 $O$에 속한 모든 퍼즐을 푸는 데 필요한 모든 정보 조각이 수집되었을 때 그리고 그때에만 여정이 성공적입니다. 즉, $O$에 있는 각 퍼즐을 완전히 푸는 데 필요한 모든 정보 조각을 모았어야 합니다.

입력

첫째 줄에 공백으로 구분된 두 정수 $N$과 $M$ ($2 \le N \le 10^6, 1 \le M \le 10^6$)이 주어집니다.

그다음 $N - 1$개의 줄이 이어지며, 각 줄에는 공백으로 구분된 세 정수 $a_i, b_i, l_i$ ($1 \le a_i, b_i \le N, 1 \le l_i \le 10^9$)가 주어집니다. 이는 노드 $a_i$와 $b_i$를 연결하고 복잡도가 $l_i$인 간선 $i$를 나타냅니다.

그다음 $M$개의 퍼즐에 대한 정의가 이어집니다. 각 퍼즐 $i$에 대해, 입력은 $k_i$와 그 뒤에 공백으로 구분된 $k_i$개의 정수 $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$)가 포함된 한 줄로 구성되며, 여기서 $u_{i_j}$는 퍼즐을 푸는 데 필요한 정보 조각들이 위치한 간선의 번호들입니다.

여기서 $K$는 모든 퍼즐에 대한 $k_i$ 값들의 총합이며, $1 \le K \le 10^6$임이 보장됩니다.

출력

문제의 정답을 $10^9 + 7$로 나눈 나머지를 나타내는 정수 하나를 한 줄에 출력합니다.

예제

예제 입력 1

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

예제 출력 1

17

노트

그림 1. 트리의 구조. 마름모는 정보 조각을 나타내고, 간선 위의 값은 복잡도를 나타냅니다.