Hipersum

Kaguya este interesată de 4 operaţii:

1. Şi-ul pe biţi, notat $a\ \&\ b$, care coincide cu operatorul $\&$ din C++. Ca exemplu, $12\ \&\ 10 = 8$.
2. Sau-ul pe biţi, notat $a\ |\ b$, care coincide cu operatorul $|$ din C++. Ca exemplu, $12\ |\ 10 = 14$.
3. Maximul, notat cu $max(a, b)$. Ca exemplu, $max(2, 3) = 3$.
4. Minimul, notat cu $min(a, b)$. Ca exemplu, $min(2, 3) = 2$.

Cumva a ajuns să defineasca hiper-valoarea şirului $a_1, \dots, a_k$, notat cu $h(a_1, \dots, a_k)$, prin expresia $h(a_1, \dots, a_k) = min(a_1, \dots, a_k) \cdot max(a_1, \dots, a_k) \cdot (a_1\ \&\ \dots\ \&\ a_k) \cdot (a_1\ |\ \dots\ |\ a_k)$.

Cerință

Miyuki o adoră pe Kaguya, deci vrea să îi facă un cadou frumos. Astfel, el îi cumpară o secvenţă $v_1, \dots, v_N$. Dar Kaguya este o fiinţa aparte, deci când primeşte acest şir, tot ce vrea e să cunoască suma hiper-valorilor tuturor subsecvenţelor lui $v$, modulo ${10}^{9} + 7$. Mai exact vrea să afle $\sum_{i=1}^{N} \sum_{j=i}^{N} h(v_i, \dots, v_j)$, modulo ${10}^{9}+7$.

Il puteţi ajuta pe Miyuki să afle această valoare pentru Kaguya?

Date de intrare

Fişierul de intrare hipersum.in conţine pe prima linie numărul $N$. Pe a doua linie se găsesc $N$ numere naturale separate prin spaţiu care reprezintă elementele şirului $V$.

Date de ieșire

În fişierul de ieşire hipersum.out se va afla un singur număr care reprezintă valoarea cerută.

Restricții și precizări

Exemplu

hipersum.in

4
1 2 3 4

hipersum.out

390