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(a_{l},\ a_{l + 1},\ \ldots,\ a_{r})*max(a_{l},\ a_{l + 1},\ \ldots,\ a_{r})*(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 vào:

• 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}\ (1 \leq a_{i} \leq 10^{8},\forall\ i \in \lbrack 1,\ n\rbrack)\).

Kết quả: Ghi một số nguyên dương duy nhất là tổng tìm được theo modulo \(\mathbf{10}^{\mathbf{9}}\mathbf{+ 7}\).

Ví dụ:

Input	Output	Giải thích
3 2 3 9	214	\(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ú ý:

Subtasks	% điểm	Giới hạn
1	40%	\(n \leq 5000\);
2	30%	\(n \leq 3 \times 10^{5},\ a_{1} \leq a_{2} \leq \ldots \leq a_{n}\);
3	30%	\(n \leq 10^{5},a_{i} \leq 500,\ \forall\ i \in \lbrack 1,\ n\rbrack\).