//File Name: cf659G.cpp//Created Time: 2016年07月12日 星期二 12时40分28秒

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#define LL long long

using namespace std;

const int MAXN =  + ;

const int MOD = (int)1e9 + ;

LL h[MAXN];

LL f[MAXN][][];

LL solve(int n){

    h[n+] = ;

    memset(f,,sizeof f);

    f[][][] = ;

    for(int i=;i<=n;i++){

        f[i][][] = ;

        (f[i][][] = f[i-][][] + h[i] -  + f[i-][][] * min(h[i]-,h[i-]-) % MOD) %= MOD;

        (f[i][][] = min(h[i],h[i+]) -  + f[i-][][] * min(min(h[i-]-,h[i]-),h[i+]-)) %= MOD;

        //printf("i = %d %lld %lld\n",i,f[i][1][0],f[i][1][1]);

    }

    return f[n][][];

}

int main(){

    int n;

    while(~scanf("%d",&n)){

        for(int i=;i<=n;i++)

            scanf("%d",&h[i]);

        printf("%d\n",(int)solve(n));

    }

    return ;

}