Cho một mảng gồm ~N~ phần tử. Bạn cần phải tính giá trị sau:

$$\sum\limits_{L=1}^n\sum\limits_{R=1}^n f(L, R).g(L, R)^3$$

với ~f(L, R)~ là tổng các phần tử trên đoạn ~[L, R]~ và ~g(L, R)~ là độ dài của đoạn ~[L, R]~.

Lưu ý:Do kết quả có thể vượt quá giới hạn dữ liệu lưu được, nên hãy in ra kết quả mod ~10^9 + 7~.

Input

• Dòng đầu tiên gồm một số nguyên ~N (1 ≤ N ≤ 105)~ — số lượng phần tử của mảng.
• Dòng tiếp theo gồm N số nguyên ~A_i (1 ≤ Ai ≤ 10^9)~ — giá trị của các phần tử trong mảng.

Output

• In ra một số nguyên duy nhất là kết quả cần tìm.

Sample

Input #1

2
2 3

Output #1

45

Input #2

3
3 4 1

Output #2

320

Input #3

4
99999999 99999999 99999999 99999999

Output #3

999999208

Hint

Ở ví dụ 1:

• ~f[1, 1] = 2; g[1, 1] = 1;~
• ~f[1, 2] = 5; g[1, 2] = 2;~
• ~f[2, 2] = 3; g[2, 2] = 1;~

nên kết quả là ~2 · 1^3 + 5 · 2^3 + 3 · 1^3 = 2 + 40 + 3 = 45

Problem source: Kc97ble - Free Contest