On vous donne un arbre avec $N$ nœuds et $N - 1$ arêtes, où chaque arête $i$ a un niveau de complexité $l_i$. La distance $d(u, v)$ entre deux nœuds $u$ et $v$ est la somme des niveaux de complexité le long de l'unique chemin entre eux dans l'arbre. Notez que $d(u, v) = d(v, u)$ et $d(v, v) = 0$.

Il y a $M$ énigmes, et chaque énigme $i$ nécessite $k_i$ fragments d'information, qui sont situés le long d'arêtes spécifiques dans l'arbre. Il est possible que plusieurs fragments d'information se trouvent sur la même arête !

Pour deux nœuds quelconques $S$ et $T$, un voyage entre $S$ et $T$ est réussi si, le long du chemin de $S$ à $T$, tous les fragments d'information nécessaires pour toute énigme rencontrée sont collectés. Plus précisément, une énigme est considérée comme résoluble au cours d'un voyage si tous les fragments d'information requis pour cette énigme sont rencontrés le long du chemin.

La tâche consiste à calculer la somme des distances pour tous les voyages réussis entre deux nœuds quelconques $S$ et $T$ (où $1 \le S \le T \le N$), modulo $10^9 + 7$.

Formellement, la tâche consiste à calculer :

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

En partant d'un nœud $S$, vous devez voyager vers un autre nœud $T$ le long de l'unique chemin dans l'arbre. En chemin, tout fragment d'information situé sur les arêtes de ce chemin sera automatiquement collecté. Pour que le voyage de $S$ à $T$ soit considéré comme réussi, il doit remplir la condition suivante :

• Soit $O$ l'ensemble des énigmes pour lesquelles au moins un fragment d'information a été collecté au cours du voyage. Le voyage est réussi si et seulement si tous les fragments d'information requis pour résoudre chaque énigme de l'ensemble $O$ ont été collectés. En d'autres termes, vous devez avoir rassemblé chaque fragment d'information nécessaire pour résoudre complètement chaque énigme de $O$.

Entrée

La première ligne contient deux entiers séparés par des espaces $N$ et $M$ ($2 \le N \le 10^6, 1 \le M \le 10^6$).

Ensuite, $N - 1$ lignes suivent, contenant chacune trois entiers séparés par des espaces $a_i, b_i, l_i$ ($1 \le a_i, b_i \le N, 1 \le l_i \le 10^9$), décrivant une arête $i$ qui relie les nœuds $a_i$ et $b_i$ avec une complexité $l_i$.

Ensuite, les définitions des $M$ énigmes suivent. Pour chaque énigme $i$, l'entrée commence par une ligne contenant $k_i$ suivi de $k_i$ entiers séparés par des espaces $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$), où $u_{i_j}$ sont les indices des arêtes sur lesquelles se trouvent les fragments d'information requis pour résoudre l'énigme.

Ici, $K$ est la somme de toutes les valeurs $k_i$ sur toutes les énigmes, et il est garanti que $1 \le K \le 10^6$.

Sortie

Affichez une ligne contenant un entier, la réponse au problème modulo $10^9 + 7$.

Exemple

Exemple d'entrée 1

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

Exemple de sortie 1

17

Note

Figure 1. La structure de l'arbre. Les losanges sont les fragments d'information et les valeurs sur les arêtes sont les complexités.