Gitt et tre med $N$ noder og $N - 1$ kanter, der hver kant $i$ har et kompleksitetsnivå $l_i$. Avstanden $d(u, v)$ mellom two noder $u$ og $v$ er summen av kompleksitetsnivåene langs den unike stien mellom dem i treet. Merk at $d(u, v) = d(v, u)$ og $d(v, v) = 0$.

Det er $M$ gåter, og hver gåte $i$ krever $k_i$ informasjonsbiter, som befinner seg langs bestemte kanter i treet. Det er mulig at flere informasjonsbiter befinner seg på samme kant!

For to vilkårlige noder $S$ og $T$ er en reise mellom $S$ og $T$ vellykket hvis alle nødvendige informasjonsbiter for enhver gåte man støter på langs stien fra $S$ til $T$ blir samlet inn. Mer spesifikt regnes en gåte som løsbar under en reise hvis alle nødvendige informasjonsbiter for den gåten blir påtruffet langs stien.

Oppgaven er å beregne summen av avstandene for alle vellykkede reiser mellom to vilkårlige noder $S$ og $T$ (der $1 \le S \le T \le N$), modulo $10^9 + 7$.

Formelt er oppgaven å beregne:

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

Med start i en node $S$ må du reise til en annen node $T$ langs den unike stien i treet. Underveis vil enhver informasjonsbit som ligger på kantene til denne stien automatisk bli samlet inn. For at reisen fra $S$ til $T$ skal regnes som vellykket, må den oppfylle følgende betingelse:

• La $O$ være mengden av gåter som det har blitt samlet inn minst én informasjonsbit for i løpet av reisen. Reisen er vellykket hvis og bare hvis alle informasjonsbitene som kreves for å løse hver gåte i mengden $O$ har blitt samlet inn. Med andre ord må du ha samlet inn hver eneste informasjonsbit som trengs for å løse hver gåte i $O$ fullstendig.

Inndata

Den første linjen inneholder to mellomromseparerte heltall $N$ og $M$ ($2 \le N \le 10^6, 1 \le M \le 10^6$).

Deretter følger $N - 1$ linjer, som hver inneholder tre mellomromseparerte heltall $a_i, b_i, l_i$ ($1 \le a_i, b_i \le N, 1 \le l_i \le 10^9$), som beskriver en kant $i$ som forbinder nodene $a_i$ og $b_i$ med kompleksitet $l_i$.

Deretter følger definisjonene av $M$ gåter. For hver gåte $i$ starter inndataene med én linje som inneholder $k_i$ etterfulgt av $k_i$ mellomromseparerte heltall $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$), der $u_{i_j}$ er indeksene til kantene hvor informasjonsbitene som kreves for å løse gåten befinner seg.

Her er $K$ summen av alle $k_i$-verdier over alle gåter, og det er garantert at $1 \le K \le 10^6$.

Utdata

Skriv ut én linje som inneholder ett heltall, svaret på problemet modulo $10^9 + 7$.

Eksempel

Eksempelinndata 1

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

Eksempelutdata 1

17

Merk

Figur 1. Strukturen til treet. Rombene er informasjonsbitene, og verdiene på kantene er kompleksitetene.