== include(page="template/taskheader" task_id="countfefete") ==

Romeo Fefetastic locuieşte în cartierul băieţilor buni şi are $N$ prieteni în cartier. Acest cartier este reprezentat ca un arbore cu $N$ noduri, unde în fiecare nod stă câte un prieten. Fiecare dintre prietenii lui are câte o valoare, $v[i], 1 <= i <= N$.

Romeo Fefetastic locuieşte în cartierul băieţilor buni şi are $N$ prieteni în cartier. Acest cartier este reprezentat ca un arbore cu $N$ noduri, unde în fiecare nod stă câte un prieten. Fiecare dintre prietenii lui are câte o valoare, $v[i], 1 ≤ i ≤ N$.

Înainte ca Romeo să plece la plimbare cu motoreta prin cartier, el îşi face o listă cu toţi prietenii pe la care vrea să treacă pentru a-i vizita. Acesta va trece succesiv pe la toţi prietenii săi, de fiecare dată alegând drumul minim. Practic, Romeo se va plimba prin toate nodurile care aparţin subarborelui conex cu număr minim de noduri care include toţi prietenii din lista sa, subarbore notat cu $S$.
El cunoaşte cum arată cartierul şi ştie că în peregrinajul său va trece şi prin faţa caselor unor prieteni care nu apar pe listă, deci nu îi va vizita. După ce a trecut pe la toţi prietenii pe care şi-a propus să îi viziteze, el decide să se oprească la nodul celui mai nevaloros prieten dintre toate nodurile prin care a trecut, pentru a-l învăţa şi pe acesta cum se fac punctele. Prietenul cel mai nevaloros locuieşte în nodul cu cea mai mică valoare din subarborele $S$. În caz că acel prieten se află deja pe lista sa, îl va vizita de două ori.

Dacă Romeo îşi vizitează prietenii din nodurile n{~1~} , n{~2~} , ..., n{~k~} , şi se opreşte în mod excepţional la prietenul cel mai nevaloros care ar sta în nodul n ${~nevaloros~}$ , atunci definim valoarea plimbării efectuate ca fiind $v[n{~1~}] xor v[n{~2~}] xor ... xor v[n{~k~}] xor v[n{~nevaloros~}]$. În caz că sunt mai mulţi prieteni la fel de nevaloroşi, Romeo merge la unul singur dintre
aceştia.

Dacă Romeo îşi vizitează prietenii din nodurile n{~1~} , n{~2~} , ..., n{~k~} , şi se opreşte în mod excepţional la prietenul cel mai nevaloros care ar sta în nodul n ${~nevaloros~}$ , atunci definim valoarea plimbării efectuate ca fiind $v[n{~1~}] ^ v[n{~2~}] ^ ... ^ v[n{~k~}] ^ v[n{~nevaloros~}]$. În caz că sunt mai mulţi prieteni la fel de nevaloroşi, Romeo merge la unul singur dintre aceştia.

Lui Romeo Fefetastic îi place mai mult gânditul decât acţiunea. Aşadar, îşi imaginează că vrea să viziteze toate submulţimile posibile de prieteni şi se întreabă care ar fi suma pentru toate plimbările posibile.

Se cere aşadar găsirea sumei valorilor plimbărilor pentru $toate submulţimile nevide$ de prieteni pe care Romeo le poate vizita şi afişarea acestei sume modulo 10^9^ + 7.

Se cere aşadar găsirea sumei valorilor plimbărilor pentru **toate submulţimile nevide** de prieteni pe care Romeo le poate vizita şi afişarea acestei sume modulo $**10^9^ + 7**$.

h2. Date de intrare
Pe primul rând al fişierului de intrare $countfefete.in$ apare numărul de prieteni din cartier $N$.

Pe al doilea rând apare şirul $v$ format din $N$ numere, unde $v[i]$ reprezintă valoarea prietenului care stă în nodul $i$.

Pe al doilea rând apare şirul $v$ format din $N$ numere, unde $v[i]$ reprezintă valoarea prietenului care stă în nodul $i$.

Pe fiecare dintre următoarele $N – 1$ rânduri se va afla o pereche de numere $x$ şi $y$, cu semnificaţia că de la nodul $x$ la nodul $y$ există un drum direct.
h2. Date de ieşire

h2. Restricţii

• $1 ≤ N ≤ 200 000$
• $0 ≤ v[x] ≤ 1 000 000 000$, pentru orice $1 ≤ x ≤ N$
• Pentru teste în valoare de $15$ puncte se garantează că $N ≤ 15$
• Pentru alte teste în valoare de $25$ de puncte se garantează că $N ≤ 5 000$
• Pentru alte teste în valoare de $15$ puncte se garantează că $N ≤ 20 000$
• Pentru alte teste în valoare de $15$ de puncte se garantează că $N ≤ 70 000$

* $1 ≤ N ≤ 200 000$
* $0 ≤ v[x] ≤ 1 000 000 000$, pentru orice $1 ≤ x ≤ N$
* Pentru teste în valoare de $15$ puncte se garantează că $N ≤ 15$
* Pentru alte teste în valoare de $25$ de puncte se garantează că $N ≤ 5 000$
* Pentru alte teste în valoare de $15$ puncte se garantează că $N ≤ 20 000$
* Pentru alte teste în valoare de $15$ de puncte se garantează că $N ≤ 70 000$

h2. Exemplu

h3. Explicaţie

Pentru testul 1:
Avem 3 prieteni cu valorile v[1]=7, v[2]=3 şi v[3]=2
Prietenii din cartier formează un lanţ 1 – 2 – 3.

Pentru testul $1$:
Avem $3$ prieteni cu valorile $v[1] = 7, v[2] = 3$ şi $v[3] = 2$.
Prietenii din cartier formează un lanţ $1 – 2 – 3$.

Considerăm toate submulţimile nevide de prieteni şi calculăm valoarea plimbărilor:

Pentru submulţimea {1} va trece prin {1}, deci valoarea plimbării = v[1] ^ v[1] = 0.
Pentru submulţimea {2} va trece prin {2}, deci valoarea plimbării = v[2] ^ v[2] = 0.
Pentru submulţimea {3} va trece prin {3}, deci valoarea plimbării = v[3] ^ v[3] = 0.
Pentru submulţimea {1, 2} va trece prin {1, 2}, iar valoarea minimă este în v[2] = 3, deci valoarea plimbării = v[1] xor v[2] xor v[2] = 7.
Pentru submulţimea {2, 3} va trece prin {2, 3}, iar valoarea minimă este în v[3] = 2, deci valoarea plimbării = v[2] xor v[3] xor v[3] = 3.
Pentru submulţimea {1, 3} va trece prin {1, 2, 3}, iar valoarea minimă este în v[3] = 2, deci valoarea plimbării = v[1] xor v[3] xor v[3] = 7.
Pentru submulţimea {1, 2, 3} va trece prin {1, 2, 3}, iar valoarea minimă este în v[3] = 2, deci valoarea plimbării = v[1] xor v[2] xor v[3] xor v[3] = 4.
Suma valorilor tuturor plimbărilor posibile va fi astfel
0 + 0 + 0 + 7 + 3 + 7 + 4 = 21.

Pentru submulţimea ${1}$ va trece prin ${1}$, deci valoarea plimbării $= v[1] $^$ v[1] = 0$.
Pentru submulţimea ${2}$ va trece prin ${2}$, deci valoarea plimbării $= v[2] $^$ v[2] = 0$.
Pentru submulţimea ${3}$ va trece prin ${3}$, deci valoarea plimbării $= v[3] $^$ v[3] = 0$.
Pentru submulţimea ${1, 2}$ va trece prin ${1, 2}$, iar valoarea minimă este în $v[2] = 3$, deci valoarea plimbării $= v[1] ^ v[2] ^ v[2] = 7$.
Pentru submulţimea ${2, 3}$ va trece prin ${2, 3}$, iar valoarea minimă este în $v[3] = 2$, deci valoarea plimbării $= v[2] ^ v[3] ^ v[3] = 3$.
Pentru submulţimea ${1, 3}$ va trece prin ${1, 2, 3}$, iar valoarea minimă este în $v[3] = 2$, deci valoarea plimbării $= v[1] ^ v[3] ^ v[3] = 7$.
Pentru submulţimea ${1, 2, 3}$ va trece prin ${1, 2, 3}$, iar valoarea minimă este în $v[3] = 2$, deci valoarea plimbării $= v[1] ^ v[2] ^ v[3] ^ v[3] = 4$.
Suma valorilor tuturor plimbărilor posibile va fi astfel $0 + 0 + 0 + 7 + 3 + 7 + 4 = 21$.

== include(page="template/taskfooter" task_id="countfefete") ==