Magul Roxanne, după nenumărate ore de cercetare a misterelor antice, a decis să meargă la cafenea să serelaxeze. Când a ajuns la vechea cafenea, a văzut pe perete o structură ciudată numită arbore. Formal, un arbore este o colect, ie de $N$ vârfuri numerotate cu numere naturale consecutive, unde vârful $0$ este rădăcina, şi toate celelalte vârfuri au un părinte unic (vârful $v$ are părintele $p{~v~}$). Deoarece cafeneaua este condusă de magi şi programatori, arborele este desenat cu rădăcina în sus.

Magul, intrigat de această structură, decide să toarne cafea magică într-unul dintre vârfuri. Dacă cafeua este turnată în vârful u, atunci aceasta se revarsă în subarborele cu rădăcina în vârful u. Deoarece este o cafea magică, nu curge la întâmplare ci ocupă cel mai lung lanţ, pe care îl poate ocupa, în subarborele cu rădăcina în vârful $u$, când trece prin nodul $u$. Cantitatea de cafea pierdută când curge, este proporţională cu lungimea lanţului pe care cafeaua îl ocupă. Roxanne notează această cantitate cu $r{~u~}$. Reţineţi că muchiile arborelui pot avea lungimi diferite.

Magul, intrigat de această structură, decide să toarne cafea magică într-unul dintre vârfuri. Dacă cafeua este turnată în vârful u, atunci aceasta se revarsă în subarborele cu rădăcina în vârful u. Deoarece este o cafea magică, nu curge la întâmplare ci ocupă cel mai lung lanţ, pe care îl poate ocupa, în subarborele cu rădăcina în vârful $u$, *când trece prin nodul* $u$. Cantitatea de cafea pierdută când curge, este proporţională cu lungimea lanţului pe care cafeaua îl ocupă. Roxanne notează această cantitate cu $r{~u~}$. Reţineţi că muchiile arborelui pot avea lungimi diferite.

Roxanne este interesată de cantitatea de cafea pe care ar putea să o piardă dacă o toarnă în toate vârfurile arborelui, aceasta este suma valorilor ru din toate vârfurile $u$ ale arborelui. Asta nu este greu de calculat iniţial, dar programatorii decid să o provoace şi cresc lungimea anumitor muchii de $Q$ ori. O poţi ajuta pe Roxanne să găseasc˘a lungimea totală a tuturor lanţurilor ocupate de cafea, dacă cafeua este turnată în toate vârfurile, iniţial şi după fiecare din cele $Q$ modificări? Atenţie! Are nevoie de răspunsuri modulo $10^9^ + 7$.

h2. Date de ieşire

În fişierul de ieşire $arboras.out$, tipăriţi $Q+ 1$ linii: pe linia $i+1$ - a afişaţi răspunsul după a $i$-a modificare. Pe prima linie trebuie să afişaţi răpunsul înainte de orice modificare. Toate răspunsurile trebuie afişate modulo $10^9^ + 7$.

În fişierul de ieşire $arboras.out$, tipăriţi $Q+ 1$ linii: pe linia $i+1$ - a afişaţi răspunsul după a $i$-a modificare. Pe prima linie trebuie să afişaţi răpunsul înainte de orice modificare. Toate răspunsurile trebuie afişate *modulo $10^9^ + 7$*.

h2. Restricţii