Fişierul intrare/ieşire:	palatulvoltaic.in, palatulvoltaic.out	Sursă	Algoritmiada 2019 Runda Maraton
Autor	Tamio-Vesa Nakajima	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	1 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Palatulvoltaic

Tanaka a decis sa viziteze locul de unde vine toata electricitatea din univers, mai exact, Palatul Voltaic. Palatul voltaic il putem modela ca pe un arbore cu N noduri, unde nodurile reprezinta turnuri ale palatului, si muchiile reprezinta coridoare ale palatului. In fiecare camera se joaca cate un sport, pasii meciurilor acelui sport furnizand electricitatea Palatului Voltaic. Se stie ca, pentru sportul din camera i, intr-un meci faci exact v_i pasi. Odata aflat intr-o camera, poti juca oricate meciuri ale sportului din camera aceea.
Tanaka are, totodata, un pedometru (adica un dispozitiv care masoara cati pasi faci), care poate numara pana la K pasi. Mai exact, in momentul in care Tanaka face cel de-al K+1-lea pas, el se reseteaza si o ia de la 0 (precum kilometrajul la masina).
In vizita sa Tanaka isi incepe drumul dintr-un nod x, ales de el. Apoi, organizatorii palatului ii vor da un numar d ales uniform aleator intre 1 si N. Apoi, Tanaka viziteaza toate nodurile la distanta cel mult d fata de x, jucand sau nu meciuri in camerele acelea. El va alege meciurile la care participa astfel incat la finalul vizitei sale, numarul de pasi pe care il arata pedometrul sau este maximizat. Tanaka ar vrea sa stie, pentru fiecare valoare posibila a lui x de la 1 la N, care este valoarea medie a numarului maxim de pasi pe care il poate arata pedometrul sau, tinand cont ca d este ales aleator uniform intre 0 si N - 1. Puteti calcula aceste valori?

Date de intrare

Fişierul de intrare palatulvoltaic.in va contine, pe primul rand, numerele N si K.
Urmeaza, pe urmatorul rand, N numere, valorile lui v.
Urmeaza, pe urmatoarele N-1 randuri, cate o pereche a, b, ce reprezinta o muchie de la nodul a la nodul b.

Date de ieşire

În fişierul de ieşire palatulvoltaic.out valorile cerute de Tanaka in ordine, pentru x de la 1 la N. Daca o medie ceruta se poate scrie ca fractia ireductibila P / Q, atunci se cere sa se afiseze P * Q^-1 (mod 10⁹ + 7), unde Q^-1 este inversul modular al lui Q modulo 10⁹+7.

Restricţii

• 1 ≤ N ≤ 300.000
• 1 ≤ v_i, K ≤ 1.000.000.000
• Pentru 10 puncte, N ≤ 20 -- feedback testele 1, 3.
• Pentru alte 30 de puncte, N ≤ 1.000 -- feedback testele 6, 13, 18.
• Pentru alte 10 puncte, K este ales uniform aleator intre 1 si 1.000.000.000, si valorile lui v sunt alese uniform aleator independent intre 1 si K -- feedback testele 21, 24.

Exemplu

Cum se trimit solutii?