Masala #1212

Xotira 256 MB Vaqt 2000 ms
14

Oxirgi yig'indi

Bu masalada sizga NN o'lchamli AA massiv berilgan. Siz esa uni oxirgi elementi qolguncha quyidagi amalni bajarishingiz kerak bo'ladi. Misol uchun sizga 5 ta elementdan iborat quyidagi massiv berilsa[1,2,3,4,5].[1+2,2+3,3+4,4+5] [1,2,3,4,5]. [1+2,2+3,3+4,4+5]  va keyin[3,5,7,9] [3,5,7,9] massivi hosil qilinadi. So'ng yana[3+5,5+7,7+9]=[8,12,16] [3+5,5+7,7+9] = [8,12,16]. Bu amal toki massiv elementi bitta qolguncha davom etadi. [8+12,12+16]=[20,28][8+12,12+16] = [20,28] va oxirida [20+28][20+28] qoladi. Shunda natija 4848teng bo'ladi. Siz ham sizga berilgan massivni oxirgi elementi qolguncha shu amallarni ketma - ket bajarib borasiz. Eng oxirida qolgan elementni ekranga chiqarishingiz kerak bo'ladi.


Kiruvchi ma'lumotlar:

Birinchi qatorda NN soni N(3N106).N(3≤N≤10^6).

Ikkinchi qatorda NN  ta sondan iborat AA massiv A[i](1A[i]109).A[i] (1≤ A[i]≤10^9).


Chiquvchi ma'lumotlar:

Yagona qatorda masala yechimini ekranga chiqaring.


Misollar
# input.txt output.txt
1
5
1 2 3 4 5
48
Izoh:

Masala yechimi juda katta bo'lib ketishi mumkin shuning uchun uni 109+710^9+7 ga bo'lgandagi qoldiqni ekranga chiqarishingiz kerak bo'ladi.