Shimulare preOJI Octavian | Tonnelle

Cerință

Se dă un arbore cu $N$ noduri rădăcinat în $1$.
Fiecare nod $i$ are o valoare asociata $v_i$.

Costul unui lanț este definit ca suma valorilor de pe lanț la puterea $K$.
Se consideră toate lanțurile care pornesc în nodul $X$ și se termină în nodul $Y$ cu proprietatea că $Y$ este un strămoș al lui $X$.

Care este suma costurilor tuturor lanțurilor descrise mai sus modulo $10^9+7$?

Date de intrare

Pe prima linie se găsesc două numere $N$ și $K$.
Pe următorul rând se găsesc $N$ valori: $v_1, v_2, ..., v_N$.
Pe următoarele $N-1$ rânduri se vor găsi câte $2$ numere, cu proprietatea că există muchie între cele $2$ noduri.

Date de ieșire

Se va afișa suma dorită modulor $10^9+7$.

Restricții și precizări

• $1 \leq N \leq 2 \cdot 10^5$
• $1 \leq K \leq 100$
• $1 \leq v_i \leq 10^9$
• Arborele este rădăcinat în nodul $1$.

Subtaskuri

• Pentru 15p $N \leq 100$
• Pentru alte 15p $K = 1$
• Pentru alte 20p $K = 2$

Exemplul 1

stdin

5 2
3 1 4 5 4
1 2
1 3
2 4
2 5

stdout

338

Explicație

Lanțurile de interes sunt: $(1), (2,1), (3,1), (2), (3), (4,2,1), (5,2,1), (4), (5), (4,2), (5,2)$
Suma dorită este: $3^2 + (1+3)^2 + (4+3)^2 + 1^2 + 4^2 + (5+1+3)^2 + (4+1+3)^2 + 5^2 + 4^2 + (5+1)^2 + (4+1)^2 = 338$.

Exemplul 2

stdin

3 5
66 68 70
1 2
2 3

stdout

945826610