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.

Î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] \text{ \textasciicircum } v[n_2] \text{ \textasciicircum } … \text{ \textasciicircum } v[n_k] \text{ \textasciicircum } v[n_{nevaloros}],$ , unde ^ reprezintă operația XOR. Î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$.

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 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.

Date de ieșire

În fișierul de ieșire countfefete.out se va scrie suma cerută modulo $10^9 + 7$.

Restricții și precizări

• 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

Exemplu

countfefete.in

3
7 3 2
1 2
2 3

countfefete.out

21

Explicație

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] ^ 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.

countfefete.in

3
1 1 1
1 3
2 3

countfefete.out

3 

Explicație

Suma valorilor tuturor plimbărilor este 3.

countfefete.in

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

countfefete.out

98 

Explicație

Suma valorilor tuturor plimbărilor este 98.