Miyuki o adoră pe Kaguya, deci vrea să îi facă un cadou frumos. Astfel, el îi cumpară o secvenţă $v{~1~}$, . . . , $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

<tex>\sum_{ 1<=i<=j<=N}^{}h(ai, . . . , aj) mod 10^9 + 7  </tex>

<tex>\displaystyle\sum_{1<=i<=j<=N}^{} h(a_i, . . . , a_j) mod 10^9 + 7 </tex>

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

h2. Date de intrare

Fişierul de intrare $hipersum.in$ ...

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

h2. Date de ieşire

În fişierul de ieşire $hipersum.out$ ...

În fişierul de ieşire $hipersum.out$ se va afla un singur număr care reprezintă valoarea cerută.
 
h2. Subtaskuri
 
* *Subtask 1 (20 puncte)*
** 1 ≤ N ≤ 1.000.
 
* *Subtask 2 (20 puncte)*
** $N ≤ 2000$
 
* *Subtask 3 (20 puncte)*
** $N ≤ 300000$
** Oricare nod are cel mult $2$ muchii incidente.

h2. Restricţii

* *Subtask 4 (20 puncte)*
** $N ≤ 300000$
** Cel mult un nod are mai mult de $1$ muchie incidentă.

* $... ≤ ... ≤ ...$

* *Subtask 5 (20 puncte)*
** $N ≤ 300000$
** Oricare nod are cel mult 3 muchii incidente.

h2. Exemplu