Cho dãy ~n~ số nguyên dương ~a_1,a_2,…,a_n~. Hàm ~f(l,r)~ được định nghĩa như sau:

~f(l,r)~ ~=~ ~min(a_l,a_{l+1},…,a_r) \times max(a_l,a_{l+1},…,a_r) \times (r-l+1)~.

Yêu cầu: Hãy tính tổng ~f(l,r)~ với mọi cặp l,r thỏa mãn ~1 \le l \le r \le n~

Input

Dòng đầu tiên chứa số nguyên dương ~n~.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,…,a_n~ (~1 \le a_i \le 10^8~,~\forall~ ~i \in [1,n]~).

Output

In ra một số nguyên dương duy nhất là tổng tìm được theo modulo ~10^9+7~.

Subtask

• 40~\%~ điểm có ~n \le 5000~

• 30~\%~ điểm có ~a_1~ ~\le~ ~a_2~ ~\le~ ~a_3~ ~\le~ ~...~ ~\le~ ~a_n~

• 30~\%~ điểm có ~n~ ~\le~ ~10^5~ ~a_i~ ~\le~ ~500~ ~\forall~ ~i \in [1,n]~

Sample Input 1

3
2 3 9

Sample Output 1

214

Giải thích

• ~f(1,1)=2×2×1=4,f(2,2)=9~,~f(3,3)=81~;
• ~f(1,2)=2×3×2=12~,~f(2,3)=54~;
• ~f(1,3)=54~.

Tổng thu được ~=4+9+81+12+54+54=214~