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

h3. Explicaţie
Pentru testul $1$:

Avem $3$ prieteni cu valorile $v[1]=7, v[2]=3$ şi $v[3]=2$

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") ==