Arbset

Mioara are un arbore cu $N$ noduri, unde rădăcina este nodul $1$, şi unde fiecare nod $i$ are câte o valoare $v_i$ între $1$ şi $N$. Toate valorile sunt distincte. O submulţime $A$ de noduri se numeşte bună dacă şi numai dacă:

1. Oricare două noduri $i, j ∈ A$, unde $i$ este strămoş al lui $j$, satisfac $v_i < v_j$;
2. Pentru oricare două noduri $i, j ∈ A$, dacă $l$ este cel mai adânc strămos, comun al lui $i$ şi $j$, atunci $l ∈ A$.

Cerință

Mioara este curioasă: care este suma valorilor $|A|$ (adică mărimea lui $A$) pentru toate mulţimile $A$ bune?

Date de intrare

Fişierul de intrare arbset.in conţine pe primul rând numărul $N$. Pe a doua linie se află valorile $v_1, \dots, v_N$. Urmează $N − 1$ rânduri, fiecare conţinând două valori $x$ si $y$, ce indică existenţa unei muchii de la $x$ la $y$.

Date de ieșire

Fişierul de ieşire arbset.out conţine răspunsul cerut, modulo ${10}^{9} + 7$.

Restricții și precizări

Exemplu

arbset.in

4
2 1 3 4
1 2
1 3
1 4

arbset.out

11

Explicație

Mulţimile bune sunt:

• $\emptyset$ (cu mărimea $0$);
• $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$ (cu mărimea $1$);
• $\{1, 3\}$, $\{1, 4\}$ (cu mărimea $2$);
• $\{1, 3, 4\}$ (cu mărimea $3$).

Astfel rezultatul este $11$.