Cho dãy ~n~ số nguyên dương ~a_{1}, a_{2}, \ldots, a_{n}~.

Hàm ~f(l, r)~ được định nghĩa như sau:

$$ f(l, r)=\min \left(a_{l}, a_{l+1}, \ldots, a_{r}\right) * \max \left(a_{l}, a_{l+1}, \ldots, a_{r}\right) *(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 \leq l \leq r \leq n~.

Dữ liệu:

• 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}, \ldots, a_{n}\left(1 \leq a_{i} \leq 10^{8}, \forall i \in[1, n]\right)~.

Kết quả:

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

Ví dụ:

Sample Input

3
2 3 9

Sample Output

214

Giải thích:

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

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

Chấm điểm:

• Subtask 1 (~25\%~): ~n \leq 5000~;
• Subtask 2 (~25\%~): ~n \leq 3 \times 10^{5}, a_{1} \leq a_{2} \leq \cdots \leq a_{n}~;
• Subtask 3 (~50\%~): ~n \leq 10^{5}, a_{i} \leq 500, \forall i \in[1, n]~.