Cerința

Se consideră un vector cu n elemente numere naturale. Calculați suma sumelor tuturor subsecvențelor ce se pot forma cu elementele vectorului. Pentru că suma poate fi foarte mare, afișați suma modulo 1.000.000.007.

Date de intrare

Fișierul de intrare easy_sum.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire easy_sum.out va conține pe prima linie numărul S, reprezentând suma sumelor tuturor subsecvențelor modulo 1.000.000.007.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi cuprinse în intervalul [1,1.000.000]
• prin subsecvență înțelegem orice înșiruire de elemente din vector aflate pe poziții consecutive.

Exemplu:

easy_sum.in

3
1 2 3

easy_sum.out

20

Explicație

Subsecvențele formate: {1}, {2}, {3}, {1,2}, {2,3}, {1,2,3}.
Suma sumelor tuturor subsecvențelor este 20.