Fişierul intrare/ieşire:	hipersum.in, hipersum.out	Sursă	Science on 2021, baraj
Autor	Tamio-Vesa Nakajima	Adăugată de	Nicola Alexandra Mihaela •Nicolaalexandra
Timp execuţie pe test	2.5 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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₁, . . . , a_k, notat cu h(a₁, . . . , a_k), prin expresia
h(a₁, . . . , a_k) = min(a₁, . . . , a_k) × max(a₁, . . . , a_k) × (a₁& . . . &a_k) × (a₁| . . . |a_k).

Miyuki o adoră pe Kaguya, deci vrea să îi facă un cadou frumos. Astfel, el îi cumpară o secvenţă v₁, . . . , 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⁹ + 7. Mai exact vrea să afle

modulo 10⁹ + 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ă.

Subtaskuri

• Subtask 1 (20 puncte)
  • 1 ≤ N ≤ 1000
  • 1 ≤ v_i ≤ 2²⁰

• Subtask 2 (20 puncte)
  • 1 ≤ N ≤ 50000
  • 1 ≤ v_i ≤ 2²⁰
  • Valorile din şir sunt generate în mod aleatoriu.

• Subtask 3 (20 puncte)
  • 1 ≤ N ≤ 100000
  • 1 ≤ v_i ≤ 2³⁰
  • Valorile din şir sunt generate în mod aleatoriu.

• Subtask 4 (20 puncte)
  • 1 ≤ N ≤ 50000
  • 1 ≤ v_i ≤ 2²⁰

• Subtask 5 (20 puncte)
  • 1 ≤ N ≤ 100000
  • 1 ≤ v_i ≤ 2³⁰

Exemplu

Cum se trimit solutii?