Arbquery

Manuela are un arbore cu $N$ noduri, unde fiecare muchie are câte o lungime. Un lanţ este o secvenţă de noduri distincte $x_1, \dots, x_k$, astfel încât să existe câte o muchie între oricare două noduri adiacente. Numim lungimea unui lanţ $x_1, ..., x_k$ suma lungimilor muchiilor care unesc nodurile adiacente din drum. Pentru fiecare muchie $(x, y)$ fie $d(x, y)$ suma lungimilor tuturor lanţurilor care conţin muchia de la $x$ la $y$.

Cerință

Manuela are $Q$ interogări, fiecare de forma unui lanţ $x_1, \dots, x_k$. Ea vrea să afle suma $d(x_1, x_2) + ... + d(x_{k-1}, x_k)$ modulo ${10}^{9} + 7$.

Date de intrare

Primul rând al fişierului de intrare arbquery.in conţine numerele $N$ şi $Q$. Urmează $N - 1$ rânduri, fiecare conţinând trei valori $x$, $y$ si $l$, ce indică existenţa unei muchii de la $x$ la $y$ cu lungimea $l$.

Urmează apoi $Q$ linii, fiecare conţinând două valori $x$ si $y$, ce reprezintă o interogare asupra lanţului unic de la $x$ la $y$.

Date de ieșire

Fişierul de ieşire arbquery.out conţine răspunsurile celor $Q$ interogări, în ordine.

Restricții și precizări

Exemplu

arbquery.in

3 3
1 2 1
2 3 100
1 2
2 3
1 3

arbquery.out

102
201
303

Explicație

Observăm că sunt trei lanţuri, $1 - 2$ de cost $1$, $2 - 3$ de cost $100$ şi $1 - 2 - 3$ de cost $101$. Astfel $d(1, 2) = 102$, $d(2, 3) = 201$. Astfel rezultatul pentru $1 \ 2$ este $d(1, 2) = 102$, pentru $2 \ 3$ este $d(2, 3) = 201$, şi pentru $1 \ 3$ este $d(1, 2) + d(2, 3) = 303$.