Cho số nguyên \(n\) và dãy số nguyên \(a_1,a_2,…,a_n\). Trọng số của bộ bốn chỉ số \(i≤j<k≤t\) là \(w(i,j,k,t)=max⁡(a_i,a_{i+1},…,a_j )×min⁡(a_k,a_{k+1},…,a_t\)).

Yêu cầu: Hãy tính tổng số của tất cả các bộ bốn chỉ số.

Input

• Dòng thứ nhất chứa số nguyên dương \(n\);

• Dòng thứ hai chứa \(n\) số nguyên \( a_1,a_2,…,a_n (1≤ a_i≤ 10^9 )\).

Output

Ghi một số nguyên là tổng trọng số tìm được sau khi chia lấy dư cho \(10^9+7\).

Ràng buộc

• Subtask 1: Có 12% số test với \(n ≤ 20\);

• Subtask 2: Có 28% số test với \(n ≤ 1000\);

• Subtask 3: Có 60% số test với \(n ≤ 10^5\);

Sample Input

6 
3 1 5 3 2 6

Sample Output

773