Annetaan puu, jossa on $N$ solmua ja $N - 1$ kaarta, missä jokaisella kaarella $i$ on monimutkaisuustaso $l_i$. Kahden solmun $u$ ja $v$ välinen etäisyys $d(u, v)$ on monimutkaisuustasojen summa niiden välisellä yksikäsitteisellä polulla puussa. Huomaa, että $d(u, v) = d(v, u)$ ja $d(v, v) = 0$.

On olemassa $M$ pulmaa, ja jokainen pulma $i$ vaatii $k_i$ tiedonjyvää, jotka sijaitsevat tietyillä puun kaarilla. Samalla kaarella voi olla useita tiedonjyviä!

Mille tahansa kahdelle solmulle $S$ ja $T$ matka solmujen $S$ ja $T$ välillä on onnistunut, jos polulla solmusta $S$ solmuun $T$ kerätään kaikki tarvittavat tiedonjyvät jokaiseen kohdattuun pulmaan. Tarkemmin sanottuna pulma katsotaan ratkaistavissa olevaksi matkan aikana, jos kaikki kyseiseen pulmaan vaadittavat tiedonjyvät kohdataan polun varrella.

Tehtävänä on laskea etäisyyksien summa kaikille onnistuneille matkoille minkä tahansa kahden solmun $S$ ja $T$ välillä (missä $1 \le S \le T \le N$), modulo $10^9 + 7$.

Muodollisesti tehtävänä on laskea:

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

Lähdettäessä solmusta $S$ sinun tulee kulkea toiseen solmuun $T$ puun yksikäsitteistä polkua pitkin. Matkan varrella kaikki tämän polun kaarilla sijaitsevat tiedonjyvät kerätään automaattisesti. Jotta matka solmusta $S$ solmuun $T$ katsottaisiin onnistuneeksi, sen on täytettävä seuraava ehto:

• Olkoon $O$ niiden pulmien joukko, joihin on kerätty vähintään yksi tiedonjyvä matkan aikana. Matka on onnistunut jos ja vain jos kaikki joukon $O$ jokaisen pulman ratkaisemiseen vaadittavat tiedonjyvät on kerätty. Toisin sanoen sinun on täytynyt kerätä jokainen tiedonjyvä, joka tarvitaan joukon $O$ jokaisen pulman täydelliseen ratkaisemiseen.

Syöte

Ensimmäinen rivi sisältää kaksi välilyönnillä eroteltua kokonaislukua $N$ ja $M$ ($2 \le N \le 10^6, 1 \le M \le 10^6$).

Sitten seuraa $N - 1$ riviä, joista jokainen sisältää kolme välilyönnein eroteltua kokonaislukua $a_i, b_i, l_i$ ($1 \le a_i, b_i \le N, 1 \le l_i \le 10^9$), jotka kuvaavat solmut $a_i$ ja $b_i$ yhdistävän kaaren $i$, jonka monimutkaisuus on $l_i$.

Sen jälkeen seuraavat $M$ pulman määritelmät. Jokaiselle pulmalle $i$ syöte koostuu yhdestä rivistä, joka sisältää luvun $k_i$ ja sen perässä $k_i$ välilyönnein eroteltua kokonaislukua $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$), missä $u_{i_j}$ ovat niiden kaarien indeksit, joilla pulman ratkaisemiseen tarvittavat tiedonjyvät sijaitsevat.

Tässä $K$ on kaikkien pulmien arvojen $k_i$ summa, ja on taattu, että $1 \le K \le 10^6$.

Tuloste

Tulosta yksi rivi, joka sisältää yhden kokonaisluvun: tehtävän vastauksen modulo $10^9 + 7$.

Esimerkki

Esimerkkisyöte 1

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

Esimerkkituloste 1

17

Huomautus

Kuva 1. Puun rakenne. Vinoneliöt ovat tiedonjyviä ja kaarilla olevat arvot ovat monimutkaisuuksia.