Cerință

Se dau un arbore cu $N$ noduri cu rădăcina în nodul $1$ al cărui muchii au lungimi exprimate prin numere naturale nenule și $Q$ query-uri de forma $u \ v$ . Pentru fiecare query să se afle suma lungimilor tuturor drumurilor distincte de la un nod aflat în subarborele cu rădăcina în nodul $u$ la un nod aflat în subarborele cu rădăcina în nodul $v$ modulo $10^9 + 7$ . (lungimea unui drum este egală cu suma lungimilor tuturor muchiilor ce îl alcătuiesc).

Date de intrare

Pe prima linie se vor citi de la tastatură numerele $N$ și $Q$ reprezentând numărul de noduri din arbore, respectiv numărul de query-uri.

Următoarele $N - 1$ linii conțin câte 2 numere $p_i \ w_i$ , $i=\overline{2,N}$ , reprezentând tatăl nodului $i$ în arbore, respectiv lungimea muchiei dintre $p_i$ și $i$ (nodul $1$ este rădăcina arborelui, deci nu are tată).

Pe următoarele $Q$ linii se va afla câte un query.

Date de ieșire

Programul va afișa pe ecran pe câte o linie rezultatele query-urilor, în ordinea în care acestea apar în input.

Restricții și precizări

$1 \leq N \leq 200 \ 000$
$1 \leq Q \leq 500 \ 000$
$1 \leq w_i \leq 1 \ 000 \ 000 \ 000$
$1 \leq u, v \leq N$
pentru fiecare query de tipul $2$ , subarborii cu rădăcinile în nodurile $u$ , respectiv $v$ nu vor avea noduri comune.

Exemplu

stdin

stdout

Explicație

Arborele descris în exemplu arată în felul următor:

Pentru primul query drumurile sunt:

De la $4$ la $8$ de lungime $14$
De la $4$ la $14$ de lungime $23$
De la $9$ la $8$ de lungime $22$
De la $9$ la $14$ de lungime $31$
De la $10$ la $8$ de lungime $15$
De la $10$ la $14$ de lungime $24$

Total: $14 + 23 + 22 + 31 + 15 + 24 = 129$

paths_sums

Time limit: 0.5s

Memory limit: 64MB

Input:

Output: