cucuruz

“When it feel like living's harder than dying
For me giving up's way harder than trying”

Stifon deține $N$ parcele de teren cultivate cu porumb, legate prin $N-1$ drumuri bidirecționale, astfel garantându-se că se poate ajunge de la o parcelă la alta pe exact un drum. Stifon se poate poziționa pe o parcelă cu numărul $D$ și să selecteze altă parcelă $W$, $W < D$ cu $dist(D, W) \leq P$, și să colecteze porumbul de pe parcelele de pe lanțul de la $D$ la $W$. Observăm că pentru o parcelă $D$ există mai multe parcele $W$ care respectă cerințele impuse. Prin urmare, Stifon notează $Fss(D)$ ca fiind suma totală a porumbului de pe fiecare lanț $(D, W)$ cu $W < D$ și $dist(D, W) \leq P$.

Cerință

Acum Stifon este foarte indecis din care parcelă să înceapă recoltarea, așa că vă întreabă care este suma totală dacă ar începe din oricare parcelă, mai exact valoarea $\displaystyle \sum_{i=1}^{N} Fss(i)$ mod $10^9 + 7$.

Date de intrare

Pe prima linie se află două numere $N$ și $P$. Pe a doua linie se află un vector $V$ cu $N$ elemente reprezentând cât porumb este în fiecare parcelă. Pe urmatoarele $N-1$ linii se află câte 2 numere $u_i$ și $v_i$ însemnând că se află un drum între parcelele $u_i$ și $v_i$.

Date de ieșire

Pe prima linie se află valoarea ceruta, $\displaystyle \sum_{i=1}^{N} Fss(i)$ mod $10^9 + 7$.

Restricții și precizări

• $P \leq N \leq 10^5$.
• $V[i] \leq 10^9 \ \ (1 \leq i \leq N)$.
• $dist(D,W)$ = numărul minim de drumuri de pe un lanț de la D la W.

  #	Scor	Restricții
  1	5	$N \leq 6$
  2	10	$N \leq 10$
  3	5	$N \leq 100$
  4	10	$N \leq 10^4$
  5	20	$N \leq 5 * 10^4, P \leq 100$
  6	10	$P = 2$
  7	40	Fără restricții suplimentare

Exemplul 1

stdin

3 2
10 5 9 
2 1
1 3

stdout

58

Explicație

Pentru $D$ = 2 putem alege $W = 1$ cu $Fss(2) = V[1] + V[2] = 10 + 5 = 15$.
Pentru $D$ = 3 putem alege fie $W = 1$ sau $W = 2$, $Fss(3) = V[1] + V[3] + V[1] + V[2] + V[3] = 43$. $Fss(1) + Fss(2) + Fss(3) = 0 + 15 + 43 = 58$.

Exemplul 2

stdin

10 3
679062366 599100597 187934521 236893327 61406391 912961000 46426980 729873627 889249584 650085534 
2 1
7 9
5 7
1 3
8 7
4 2
4 9
10 3
6 7

stdout

396699172

Explicație

Nuj boss, numără-le singur!