#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(v) (v).begin(),(v).end()

#define PII pair<int,int>
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define lint long long int
#define VI vector<int>

#define debug(x) {cerr <<#x <<" = " <<x <<endl; }
#define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; }
#define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; }
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }}
#define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }}

#define make( x) int (x); scanf("%d",&(x));
#define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y));
#define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z));
#define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);}
#define IOS ios_base::sync_with_stdio(0)
#define HEAP priority_queue

#define read( x) scanf("%d",&(x));
#define read2( x, y) scanf("%d%d",&(x),&(y));
#define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z));
#define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);}


using namespace std;


#define CD complex<double>


int mod = 1e9+7;
const int max_n = 1e6+5;
const double eps = 1e-8;
CD roots[max_n];
CD t1[max_n], t2[max_n];

int N;
int n1, n2; // INPUT
VI A, B;
int ANS[max_n];

void FFT(CD t[]) {
    FOR(i,0,N) {
        int j = 0;
        for (int k=1; k<N; k<<=1, j<<=1) if(k&i) j++;
        j>>=1;
        if(i<j) swap(t[i], t[j]);
    }
    int step = 1, n_step = 0;
    while ((1<<n_step)<N) n_step++;
    for (int step=1; step<N; step<<=1) {
        --n_step;
        for(int i = 0; i<N; i+=2*step) FOR(j,0,step) {
            CD u = t[i+j], v = t[i+j+step];
            t[i+j] = u + v*roots[j<<n_step];
            t[i+j+step] = u-v*roots[j<<n_step];
        }
    }
}

VI conv(VI& v1, VI& v2) {
    n1 = v1.size(); n2 = v2.size();
    N = 1;
    while(N<n1 || N<n2) N<<=1;
    N<<=1;
    FOR(i,0,N) {
        t1[i] = CD(0.0,0.0);
        t2[i] = CD(0.0,0.0);
        roots[i] = CD(cos(2*M_PI*i/N), -sin(2*M_PI*i/N));
    }
    FOR(i,0,n1) t1[i] = CD(v1[i],0.0);
    FOR(i,0,n2) t2[i] = CD(v2[i],0.0);
    FFT(t1); FFT(t2);
    double s = 1.0/N;
    FOR(i,0,N) {
        t1[i] *= t2[i]*s;
        roots[i] = CD(real(roots[i]), -imag(roots[i]));
    }
    FFT(t1);

    FOR(i,0,N) {
        ANS[i] = ((lint) (real(t1[i])+0.5))%mod;
        roots[i] = CD(real(roots[i]), -imag(roots[i]));
    }
    VI ans; FOR(i,0,n1+n2) ans.pb(ANS[i]%mod);
    return ans;
}

VI v;

int SQ = 30000;

VI conv2(VI& v1, VI& v2) {
    VI w1, w2, w3, w4;
    FOR(i,0,v1.size()) w1.pb(v1[i]%SQ), w3.pb(v1[i]/SQ);
    FOR(i,0,v2.size()) w2.pb(v2[i]%SQ), w4.pb(v2[i]/SQ);
    VI ans1 = conv(w1, w2);
    VI ans2 = conv(w1, w4);
    VI ans3 = conv(w3, w2);
    VI ans4 = conv(w3, w4);
    FOR(i,0,ans1.size()) {
        int myns = (ans1[i] + ans2[i] *1LL*SQ + ans3[i] * 1LL * SQ + ans4[i] * 1LL * SQ * 1LL * SQ) % mod;
        ans1[i] = myns;
    }
    return ans1;
}

VI rob(int a, int b) {
    if (a==b) {
        VI ans(2);
        ans[0] = v[a];
        ans[1] = 1;
        return ans;
    } else {
        int mid = (a+b)/2;
        VI v1 = rob(a, mid);
        VI v2 = rob(mid+1, b);
        return conv2(v1, v2);
    }
}




int main() {
    make(myn);
    readv(v, myn);
    VI ans = rob(0, myn - 1);
    int loc = 0;
    FOR(i,0,ans.size()) {
        loc = (loc + (myn-i)*1LL*ans[i])%mod;
    }
    printf("%d\n", loc);
}