Blocaje

Cerință

Se dă $N$ precum și un șir $A$ de $N$ elemente.

Se definește costul unei subsecvente $[st,dr]$ ca fiind rezultatul următorului program:

costul(st,dr):
	inițializează variabila S cu un șir vid
	pentru i de la st la dr:
		Cat timp S nu este vid și ultimul element din S este strict mai mare ca A[i]:
			scoate ultimul element din S
		adaugă A[i] la finalul lui S
	returnează lungimea lui S

Avem posibilitatea să blocăm un element din șir. Notăm cu $A_i$ șirul $A$ cu elementul de pe poziția $i$ blocat.
Daca blocăm elementul $i$ și vrem să calculăm costul unei subsecvențe, dacă cumva $i$ ajunge la sfârșitul lui $S$, acesta nu va putea fi scos de nimeni (este blocat).

Se definește frumusețea unui șir $A$ ca fiind suma costurilor tuturor subsecvențelor din $A$ și se notează cu $F(A)$.
Formal: $F(A) = \sum_{i=1}^N \sum_{j=i}^N costul(i,j)$

Se cere să se calculeze $F(A_1) + F(A_2) + ... + F(A_N)$.

Date de intrare

Pe prima linie se găsește un număr natural $N$.
Pe următorul rând se găsesc elementele șirului $A$.

Date de ieșire

Se va afișa un număr natural reprezentând suma dorită. Deoarece această valoare poate fi foarte mare, se cere afișarea restului împărțirii acesteia la $1 \ 000 \ 000 \ 007$.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$;
• $0 \leq A_i \leq 1 \ 000 \ 000$;
• Pentru teste în valoare de 20 de puncte: $1 \leq N \leq 50$;
• Pentru teste în valoare de 30 de puncte: $1 \leq N \leq 200$;
• Pentru teste în valoare de 20 de puncte: $1 \leq N \leq 5000$;
• Pentru teste în valoare de 30 de puncte: fară restricții suplimentare.

Exemplul 1

stdin

7
6 9 2 7 3 5 4

stdout

395