Binh co mot mang số nguyên \(A\) gom \(N\) phan tu. Binh muon tính tong cac giá trị nhỏ nhất cua tat ca cac dãy con (subarray) lien tiep cua mang.

Vi kết quả co the rat lớn, hay in ra kết quả sau khi chia lay du cho \(10^9 + 7\).

định dạng đầu vào

• Dong thu nhất chữa số nguyên duong \(N\) (\(1 \le N \le 10^5\)).
• Dong thu hai chữa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).

định dạng đầu ra

• Mot số nguyên duy nhất la tong cac giá trị nhỏ nhất cua moi subarray, modulo \(10^9 + 7\).

ví dụ

Input:

4
3 1 2 4

Output:

17

Giai thich: Cac subarray va giá trị nhỏ nhất tuong ung:

• \([3]\): 3
• \([3,1]\): 1
• \([3,1,2]\): 1
• \([3,1,2,4]\): 1
• \([1]\): 1
• \([1,2]\): 1
• \([1,2,4]\): 1
• \([2]\): 2
• \([2,4]\): 2
• \([4]\): 4 Tong = \(3 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 2 + 4 = 17\).

ràng buộc

• 100% số diem: \(N \le 10^5\).