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, \ldots, x_k$, astfel încât să existe câte o muchie între oricare două noduri adiacente. Numim lungimea unui lanţ $x_1, \ldots, 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 $Q$ interogări, fiecare de forma unui lanţ $x_1, \ldots, x_k$. Ea vrea să afle suma $d(x_1, x_2) + \ldots + d(x_{k-1}, x_k) \mod 10^9 + 7$.

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

h2. Date de intrare