Sereja has a sequence that consists of n positive integers, a1, a2, ..., an. 

First Sereja took a piece of squared paper and wrote all distinct non-empty non-decreasing subsequences of sequence a. Then for each sequence written on the squared paper, Sereja wrote on a piece of lines paper all sequences that do not exceed it.

A sequence of positive integers x = x1, x2, ..., xr doesn't exceed a sequence of positive integers y = y1, y2, ..., yr, if the following inequation holds: x1 ≤ y1, x2 ≤ y2, ..., xr ≤ yr.

Now Sereja wonders, how many sequences are written on the lines piece of paper. Help Sereja, find the required quantity modulo 1000000007 (109 + 7). 

Input

The first line contains integer n (1 ≤ n ≤ 105). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 106).

Output

In the single line print the answer to the problem modulo 1000000007 (109 + 7).

Examples

Input

1
42


Output

42


Input

3
1 2 2


Output

13


Input

5
1 2 3 4 5


Output

719
import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        //Scanner in = new Scanner(System.in);
        Reader in = new Reader();
        Main solver = new Main();
        solver.solve(out, in);
        out.flush();
        out.close();
 
    }
 
    static long INF = (long)1e16;
    static int maxn = (int)1e6+5;
    static int mod=(int)1e9+7 ;
    static int n,m,k,t,q,x,a,b,y,d;
    static long tree[];
    
    void solve(PrintWriter out, Reader in) throws IOException{
        n = in.nextInt();
        
        int[] arr = new int[n];
        for(int i=0;i<n;i++) arr[i] = in.nextInt();
        
        tree = new long[maxn*4];
        
        long[] dp = new long[maxn];
        
        for(int i=0;i<n;i++){
            dp[arr[i]] = ((query(1,1,maxn,1,arr[i])*(long)arr[i])%mod+arr[i])%mod;
            update(1,1,maxn,arr[i],dp[arr[i]]);
        }
        
        long ans =0;
        for(int i=1;i<maxn;i++) ans = (dp[i]+ans)%mod;
        
        out.println(ans);
    }
    
    //<>
    
    static void update(int idx,int s,int e,int d,long v){
        if(s==e){
            tree[idx] = v;
            return;
        }
        
        int mid = (s+e)/2;
        
        if(s<=d && d<=mid){
            update(idx*2,s,mid,d,v);
        }else {
            update(idx*2+1,mid+1,e,d,v);
        }
        
        tree[idx] = (tree[idx*2]+tree[idx*2+1])%mod;
        return;
    }
    
    static long query(int idx,int s,int e,int l,int r){
        if(r<s || e<l) return 0;
        
        if(l<=s && e<=r) return tree[idx];
        
        int mid = (s+e)/2;
        long q1 = query(idx*2,s,mid,l,r);
        long q2 = query(idx*2+1,mid+1,e,l,r);
        
        return (q1+q2)%mod;
    }
    
    static class Reader {

    private InputStream mIs;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public Reader() {
        this(System.in);
    }

    public Reader(InputStream is) {
        mIs = is;
    }

    public int read() {
        if (numChars == -1) {
            throw new InputMismatchException();

    }
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = mIs.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0) {
                return -1;
            }
        }
        return buf[curChar++];
    }

    public String nextLine() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isEndOfLine(c));
        return res.toString();
    }

    public String next() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    double nextDouble()
    {
        return Double.parseDouble(next());
    }

    public long nextLong() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public int nextInt() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public boolean isEndOfLine(int c) {
        return c == '\n' || c == '\r' || c == -1;
    }

    }
}