Masala #0386

Uzunligi N ga teng bo’lgan A massiv berilgan. Biz berilgan massivni bir nechta bo’laklarga bo’lib, bo’laklardan B massivni hosil qilishimiz mumkin. Misol uchun agar A = [1, 2, 3] ga teng bo’lsa, biz uni B massivga quyidagi ko’rinishlarda bo’laklab berishimiz mumkin:

• B = [(1), (2), (3)]
• B = [(1, 2), (3)]
• B = [(1), (2, 3)]
• B = [(1,2,3)]

Bitta bo’lakning qiymati (bo’lakdagi elementlar yig’indisi) * (bo’lak elementlari soni) ga teng. B massivning qiymati esa undagi barcha bo’laklarning qiymatlari yig’indisiga teng.

Sizga A massiv berilgan, siz hosil qilinishi mumkin bo’lgan barcha B massivlarining umumiy qiymatini toping. Misol uchun yuqoridagi A = [1, 2, 3] da:

[(1), (2), (3)] ning qiymati 1 * 1 + 2 * 1 + 3 * 1 = 6

[(1, 2), (3)] ning qiymati 3 * 2 + 3 * 1 = 9

[(1), (2, 3)] ning qiymati 1 * 1 + 5 * 2 = 11

[(1, 2, 3)] ning qiymati 6 * 3 = 18

Sizning javobingiz 6+9+11+18 = 44 ga teng bo’lishi kerak.

Kirish faylining dastlabki satrida bitta butun son, N(1 <= N <= 10⁶), A massiv elementlari soni kiritiladi.

Ikkinchi satrda N ta butun son, A (1 <= A_i <= 10⁹) massiv elementlari kiritiladi.

Chiqish faylida yagona butun son, natijaning 10⁹+7 (1000000007) ga bo’lgandagi qoldig’ini chop eting.