Weird Array

"Weird doesn't really exist, not because there isn't anything weird out there, but because everything is weird."

Cerință

Fie $a$ un vector cu $N$ elemente. Pentru o subsecvență$^{\dag}$ $a[i,...,j]$ cu $0 \leq i \leq j \leq N-1$ considerăm toate subșirurile nevide al acesteia, iar pentru fiecare calculăm xor-ul elementelor sale. Însumând toate aceste valori (modulo $10^9+7$), obținem puterea subsecvenței. Definimn valoarea vectorului $a$ ca fiind suma puterilor tuturor subsecvențelor sale (modulo $10^9+7$).

Date de intrare

Pe prima linie se va găsi $N$, iar pe a doua linie se vor găsi elementele $a_{0}, a_{1}, ... , a_{N-1}$.

Date de ieșire

Pe prima linie se va afișa suma valorilor tuturor subsecvențelor vectorului $a$, modulo $10^9+7$.

Restricții și precizări

• $1 \leq N \leq 2 \cdot 10^5$;
• $0 \leq a_{i} \leq 10^9$ pentru orice $0 \leq i \leq N-1$.
• $^{\dag}$ Prin subsecvență a unui șir se înțelege o succesiune de elemente aflate pe poziții consecutive în șirul inițial. De exemplu, pentru șirul $[1, 2, 3, 6, 12]$, $[1, 2]$ este o subsecvență, $[2, 3, 6]$ este o subsecvență, dar $[2, 6, 12]$ nu este.
• Pentru teste în valoare de $10$ puncte, $N \leq 10$.
• Pentru teste în valoare de alte $40$ de puncte $N \leq 5000$.
• Pentru teste în valoare de alte $10$ de puncte, avem că $a_{0} = a_{1} = ... = a_{N-1}$.

Exemplul 1

stdin

3
2 3 1

stdout

30

Explicație

Puterea subsecvenței $[0,0]$ este $2 = 2$,
Puterea subsecvenței $[1,1]$ este $3 = 3$,
Puterea subsecvenței $[2,2]$ este $1 = 1$,
Puterea subsecvenței $[0,1]$ este $2 + 3 + (2 \oplus 3) = 6$,
Puterea subsecvenței $[1,2]$ este $3 + 1 + (3 \oplus 1) = 6$,
Puterea subsecvenței $[0,2]$ este $2 + 3 + 1 + (2 \oplus 3) + (3 \oplus 1) + (2 \oplus 1) + (2 \oplus 3 \oplus 1) = 12$,
Valoarea șirului dat este astfel: $2+3+1+6+6+12 = 30$.