== include(page="template/taskheader" task_id="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, ..., 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$.

Manuela are un arbore cu $N$ noduri, unde fiecare muchie are câte o lungime. Un lanţ este o secvenţă de noduri distincte <tex> $x_1, ..., x_k$ </tex>, astfel încât să existe câte o muchie între oricare două noduri adiacente. Numim lungimea unui lanţ <tex> x_1, ..., x_k </tex> 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$.

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

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

h2. Date de intrare

h2. Subtaskuri

* Subtask 1 (10 puncte)

* *Subtask 1 (10 puncte)*

** $N, Q ≤ 20$.
** Oricare muchie are lungimea cel mult $10^5^$.

* Subtask 2 (30 puncte)

* *Subtask 2 (30 puncte)*

** $N, Q ≤ 2.000$.
** Oricare muchie are lungimea cel mult $10^5^$.

* Subtask 3 (10 puncte)

* *Subtask 3 (10 puncte)*

** $N, Q ≤ 100.000$.
** Oricare nod are cel mult 2 muchii incidente.
** Oricare muchie are lungimea cel mult $10^5^$.

* Subtask 4 (10 puncte)

* *Subtask 4 (10 puncte)*

** $N, Q ≤ 100.000$.
** Cel mult un nod are mai mult de 1 muchie incidentă.
** Oricare muchie are lungimea cel mult $10^5^$.

* Subtask 5 (40 puncte)

* *Subtask 5 (40 puncte)*

** $N, Q ≤ 100.000$.
** Oricare muchie are lungimea cel mult $10^5^$.
h2. Exemplu

table(Exemplu). |_. arbquery.in |_. arbquery.out |

table(example). |_. arbquery.in |_. arbquery.out |

| 3 3
1 2 1
2 3 100