Đề bài

Trong một cuộc thi OLP, TrViệt gặp một bài toán tính tổng dãy số khá đơn giản. Sau khi giải xong, TrViệt chợt nảy ra một câu hỏi:

Nếu thay vì tính tổng các phần tử, ta tính tổng giá trị nhỏ nhất của tất cả các dãy con liên tiếp thì sao?

TrViệt quyết định ra một bài toán để thử thách mọi người. Liệu bạn có thể giải bài toán này không?

Cho một mảng A gồm N số nguyên: ~a_0, a_1, \dots, a_{N-1}~.

Một dãy con liên tiếp (subarray) là một đoạn các phần tử nằm kề nhau trong mảng, được xác định bởi hai chỉ số l và r với ~0 \le l \le r < N~.

Ví dụ, với mảng [3, 1, 2], các subarray là: [3], [1], [2], [3, 1], [1, 2], [3, 1, 2].

Yêu cầu: Với mỗi cặp chỉ số (l, r) thỏa mãn ~0 \le l \le r < N~, đặt:

$$f(l, r) = \min(a_l, a_{l+1}, \dots, a_r)$$

Hãy tính:

$$S = \sum_{0 \le l \le r < N} f(l, r)$$

Vì kết quả có thể rất lớn, hãy in kết quả theo modulo ~10^9 + 7~.

Dữ liệu vào (Input)

• Dòng 1: một số nguyên N — số phần tử của mảng.
• Dòng 2: N số nguyên ~a_0, a_1, \dots, a_{N-1}~ — giá trị các phần tử của mảng.

Ràng buộc: ~1 \le N \le 10^6~ và ~1 \le a_i \le 10^9~.
Giới hạn cụ thể của N phụ thuộc vào từng subtask (xem phần Subtask).

Kết quả (Output)

In ra một số nguyên duy nhất là giá trị của ~S~ modulo ~10^9 + 7~.

Ví dụ

Ví dụ 1

Input

4
3 1 2 4

Output

17

Giải thích: Các subarray và giá trị nhỏ nhất tương ứng:

• [3] ⇒ min = 3
• [1] ⇒ min = 1
• [2] ⇒ min = 2
• [4] ⇒ min = 4
• [3, 1] ⇒ min = 1
• [1, 2] ⇒ min = 1
• [2, 4] ⇒ min = 2
• [3, 1, 2] ⇒ min = 1
• [1, 2, 4] ⇒ min = 1
• [3, 1, 2, 4] ⇒ min = 1

Tổng = 3 + 1 + 2 + 4 + 1 + 1 + 2 + 1 + 1 + 1 = 17.

Ví dụ 2

Input

3
1 1 1

Output

6

Giải thích: Mảng có 6 subarray: [1], [1], [1], [1, 1], [1, 1], [1, 1, 1]. Cả 6 đều có min = 1, nên tổng = 6.

Subtask

Bộ test được chia thành 4 subtask: