#include <bits/stdc++.h>

using namespace std;

int S(vector<int> &A){
    long sum = 0;
    int val = 0;
    size_t size_A = A.size();
    size_t size_SA = size_A;
    size_t size_k = 0;

    for(int k = 1 ; k < size_A ; k++){
        size_k = size_A - k;
        for(int i = 0 ; i < size_k ; i++){
            val = max(A[size_SA - size_k - 1], A[size_SA - size_k]);
            sum += val;
            A.push_back(val);
            size_SA++;
        }
    }
    
    return sum;
}

int solve(vector <int> A) {
    //  Return the sum of S(S(A)) modulo 10^9+7.
    long sum = 0;
    size_t size_A = A.size();
    
    for(int i = 0 ; i < size_A ; i++){
        sum += A[i];
    }
    sum += S(A);
    sum += S(A);
    return sum % 1000000000;
}

int main() {
    int n;
    cin >> n;
    vector<int> A(n);
    for(int A_i = 0; A_i < n; A_i++){
       cin >> A[A_i];
    }
    int result = solve(A);
    cout << result << endl;
    return 0;
}