Pentru un șir de numere \( A \) se definește următoarea funcție de cost: \( f(A) = 1 \cdot v_1 + 2 \cdot v_2 + … + k \cdot v_k \), unde \( [v_1, v_2, …, v_k] \) sunt valorile distincte ale lui \( A \), ordonate crescător.

Cerința

Fiind dat un șir de N numere naturale A, să se calculeze suma aplicării funcției f pe toate subsecvențele lui A (i.e. suma după (1 ≤ i ≤ j ≤ N) din f(A[i...j]), unde A[i…j] este subsecvența de la i la j).

Date de intrare

Fișierul sortall.in conține pe prima linie numărul natural N. Linia a doua conține N numere naturale separate prin spațiu, reprezentând elementele șirului A.

Date de ieșire

Fișierul sortall.out va conține răspunsul modulo 1 000 000 007.

Restricții și precizări

• 1 ≤ N ≤ 50 000
• 1 ≤ Vi ≤ N
• Pentru 10 puncte 1 ≤ N ≤ 100
• Pentru alte 15 puncte 1 ≤ N ≤ 1000
• Pentru alte 15 puncte 1 ≤ N ≤ 5000
• Pentru alte 20 de puncte se garanteză că valorile din șir sunt distincte

Exemplu 1:

sortall.in

3
1 3 2

sortall.out

35

Exemplu 2:

sortall.in

8
4 3 4 4 7 1 2 1

sortall.out

861