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

$$\sum_{L=1}^{N} \sum_{R=L}^{N} f(L, R) \cdot 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~.

Dữ liệu

• Dòng đầu tiên gồm một số nguyên ~N~ ~(1 \le N \le 10^5)~ — số lượng phần tử của mảng.

• Dòng tiếp theo gồm ~N~ số nguyên ~A_i~ ~(1 \le A_i \le 10^9)~ — giá trị của các phần tử trong mảng.

Kết quả

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

Ví dụ

Sample Input 1

2
2 3

Sample Output 1

45

Sample Input 2

3
3 4 1

Sample Output 2

320

Sample Input 3

4
99999999 99999999 99999999 99999999

Sample Output 3

999999208

Giải thích

Ở 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 \cdot 1^3 + 5 \cdot 2^3 + 3 \cdot 1^3 = 2 + 40 + 3 = 45~

Chấm điểm

• Subtask 1 (50% số test): ~N \le 10^3~

• Subtask 2 (50% số test): Không có ràng buộc gì thêm