Gefið er tré með $N$ hnútum og $N - 1$ leggjum, þar sem hver leggur $i$ hefur flækjustig $l_i$. Fjarlægðin $d(u, v)$ milli tveggja hnúta $u$ og $v$ er summa flækjustiganna eftir eina vegarins milli þeirra í trénu. Athugið að $d(u, v) = d(v, u)$ og $d(v, v) = 0$.

Það eru $M$ þrautir og hver þraut $i$ krefst $k_i$ upplýsingabúta sem eru staðsettir á tilteknum leggjum í trénu. Það er mögulegt að margir upplýsingabútar séu á sama legg!

Fyrir hvaða tvo hnúta $S$ og $T$ sem er, þá tekst ferðalag milli $S$ og $T$ ef allir nauðsynlegir upplýsingabútar fyrir sérhverja þraut sem verður á vegi manns á leiðinni frá $S$ til $T$ eru safnaðir. Nánar tiltekið telst þraut leysanleg á ferðalagi ef allir nauðsynlegir upplýsingabútar fyrir þá þraut verða á vegi manns á leiðinni.

Verkefnið er að reikna summu fjarlægða fyrir öll vel heppnuð ferðalög milli hvaða tveggja hnúta $S$ og $T$ sem er (þar sem $1 \le S \le T \le N$), modulo $10^9 + 7$.

Formlega séð er verkefnið að reikna:

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

Með upphafsstað í hnúti $S$ þarftu að ferðast til annars hnúts $T$ eftir eina veginum í trénu. Á leiðinni safnast sjálfkrafa allir upplýsingabútar sem eru á leggjum þessa vegar. Til þess að ferðalagið frá $S$ til $T$ teljist hafa tekist verður það að uppfylla eftirfarandi skilyrði:

• Látum $O$ vera mengi þeirra þrauta sem að minnsta kosti einum upplýsingabút hefur verið safnað fyrir á ferðalaginu. Ferðalagið tekst ef og aðeins ef öllum upplýsingabútum sem þarf til að leysa hverja þraut í menginu $O$ hefur verið safnað. Með öðrum orðum verður þú að hafa safnað sérhverjum upplýsingabút sem þarf til að leysa hverja þraut í $O$ að fullu.

Inntak

Fyrsta línan inniheldur tvær heiltölur aðskildar með bili $N$ og $M$ ($2 \le N \le 10^6, 1 \le M \le 10^6$).

Síðan fylgja $N - 1$ línur, þar sem hver lína inniheldur þrjár heiltölur aðskildar með bili $a_i, b_i, l_i$ ($1 \le a_i, b_i \le N, 1 \le l_i \le 10^9$), sem lýsa legg $i$ sem tengir hnútana $a_i$ og $b_i$ með flækjustigi $l_i$.

Síðan fylgja skilgreiningar á $M$ þrautum. Fyrir hverja þraut $i$ byrjar inntakið á einni línu sem inniheldur $k_i$ og í kjölfarið koma $k_i$ heiltölur aðskildar með bili $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$), þar sem $u_{i_j}$ eru númer leggjanna sem upplýsingabútarnir sem þarf til að leysa þrautina eru á.

Hér er $K$ summa allra gilda $k_i$ yfir allar þrautir, og tryggt er að $1 \le K \le 10^6$.

Úttak

Prentaðu eina línu sem inniheldur eina heiltölu, svarið við verkefninu modulo $10^9 + 7$.

Dæmi

Dæmi um inntak 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æmi um úttak 1

17

Athugasemd

Mynd 1. Bygging trésins. Tígullinn táknar upplýsingabútana og gildin á leggjunum eru flækjustigin.