Gegeben ist ein Baum mit $N$ Knoten und $N - 1$ Kanten, wobei jede Kante $i$ einen Komplexitätsgrad $l_i$ hat. Der Abstand $d(u, v)$ zwischen zwei Knoten $u$ und $v$ ist die Summe der Komplexitätsgrade entlang des eindeutigen Pfades zwischen ihnen im Baum. Beachten Sie, dass $d(u, v) = d(v, u)$ und $d(v, v) = 0$ gilt.

Es gibt $M$ Rätsel, und jedes Rätsel $i$ erfordert $k_i$ Informationsteile, die sich entlang bestimmter Kanten im Baum befinden. Es ist möglich, dass sich mehrere Informationsteile auf derselben Kante befinden!

Für zwei beliebige Knoten $S$ und $T$ ist eine Reise zwischen $S$ und $T$ erfolgreich, wenn entlang des Pfades von $S$ nach $T$ alle erforderlichen Informationsteile für jedes angetroffene Rätsel gesammelt werden. Genauer gesagt gilt ein Rätsel während einer Reise als lösbar, wenn alle für dieses Rätsel erforderlichen Informationsteile entlang des Pfades angetroffen werden.

Die Aufgabe besteht darin, die Summe der Abstände für alle erfolgreichen Reisen zwischen zwei beliebigen Knoten $S$ und $T$ (wobei $1 \le S \le T \le N$) modulo $10^9 + 7$ zu berechnen.

Formal besteht die Aufgabe darin, Folgendes zu berechnen:

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

Ausgehend von einem Knoten $S$ müssen Sie entlang des eindeutigen Pfades im Baum zu einem anderen Knoten $T$ reisen. Unterwegs wird jedes Informationsteil, das sich auf den Kanten dieses Pfades befindet, automatisch eingesammelt. Damit die Reise von $S$ nach $T$ als erfolgreich gilt, muss sie die folgende Bedingung erfüllen:

• Sei $O$ die Menge der Rätsel, für die während der Reise mindestens ein Informationsteil gesammelt wurde. Die Reise ist genau dann erfolgreich, wenn alle Informationsteile gesammelt wurden, die erforderlich sind, um jedes Rätsel in der Menge $O$ zu lösen. Mit anderen Worten: Sie müssen jedes Informationsteil gesammelt haben, das benötigt wird, um jedes Rätsel in $O$ vollständig zu lösen.

Eingabe

Die erste Zeile enthält zwei durch Leerzeichen getrennte ganze Zahlen $N$ und $M$ ($2 \le N \le 10^6, 1 \le M \le 10^6$).

Danach folgen $N - 1$ Zeilen, die jeweils drei durch Leerzeichen getrennte ganze Zahlen $a_i, b_i, l_i$ ($1 \le a_i, b_i \le N, 1 \le l_i \le 10^9$) enthalten und eine Kante $i$ beschreiben, die die Knoten $a_i$ und $b_i$ mit der Komplexität $l_i$ verbindet.

Anschließend folgen die Definitionen von $M$ Rätseln. Für jedes Rätsel $i$ besteht die Eingabe aus einer Zeile, die $k_i$ gefolgt von $k_i$ durch Leerzeichen getrennten ganzen Zahlen $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$) enthält, wobei $u_{i_j}$ die Indizes der Kanten sind, auf denen sich die zur Lösung des Rätsels erforderlichen Informationsteile befinden.

Hierbei ist $K$ die Summe aller $k_i$-Werte über alle Rätsel hinweg, und es wird garantiert, dass $1 \le K \le 10^6$ gilt.

Ausgabe

Geben Sie eine Zeile mit einer ganzen Zahl aus, der Antwort auf das Problem modulo $10^9 + 7$.

Beispiel

Beispieleingabe 1

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

Beispielausgabe 1

17

Hinweis

Abbildung 1. Die Struktur des Baums. Die Rauten sind die Informationsteile und die Werte an den Kanten sind die Komplexitäten.