Tom và Jerry là một series phim hoạt hình của Mỹ được chiếu trên truyền hình và rạp hát với nhiều thể loại từ phim ngắn cho tới phim dài. Được sản xuất bởi William Hanna và Joseph Barbera cho hãng phim MGM, phim là cuộc đối đầu vô tận giữa chú mèo Tom và chú chuột Jerry mang tới vô vàn tiếng cười cho khán giả. Trong một lần nọ Tom được thầy giáo giao cho bài toán. Tom khá lười nên mon men làm thân với Jerry và nhờ Jerry giải. Bài toán có nội dung như sau: Cho mảng ~A~ gồm ~N~ số nguyên dương, hãy tính tổng bình phương tất cả các dãy con liên tiếp của ~A.~ Nói cách khác, gọi ~sum(l, r)~ là tổng của đoạn ~l..r~. Ta cần tính ~\sum_{L=1}^n \sum_{R=L}^n sum(L,R)^2~.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên ~N~.
• Dòng tiếp theo gồm ~N~ số nguyên ~A[i]~ (~A[i] ≤ 10^9~).

Output

Gồm 1 số nguyên duy nhất là kết quả của bài toán. Vì kết quả có thể rất lớn nên bạn chỉ cần in kết quả của bài toán lấy phần dư cho ~10^9+7~.

Sample input

3
3 2 4

Sample output

171

Ràng buộc:

• 50% số điểm ứng với ~N ≤ 5000;~
• 50% số điểm ứng với ~N ≤ 300000;~