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 javax.print.DocFlavor;
import java.awt.*;
import java.io.*;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.*;

public class Main {
    static int[] arr;
    static ArrayList<Integer> arr2;
    static long[] SegTree;
    static int[] Open, Closed;
    static int K;
    static long mod = ((long) 1e9) + 7;
    static String s;

    static class pair {
        long val;
        int app;

        pair(long val, int ind) {
            this.val = val;
            app = ind;
        }
    }

    static void buildSegTree() {
        int n = arr2.size();
        int n2 = (int) (Math.log(n) / Math.log(2));
        if (n != (1 << n2))
            n = 1 << (n2 + 1);
        SegTree = new long[n << 1];
        // build(0, arr.length - 1, 1);
    }

    /*static pair build(int beg, int end, int indxInTree) {

        if (beg == end) {
            SegTree[indxInTree] = new pair(arr[beg],beg);
            return SegTree[indxInTree];
        }

        int mid = (beg + end) >> 1;
        pair l = build(beg, mid, indxInTree << 1);
        pair r = build(mid + 1, end, (indxInTree) << 1 | 1);
        if(l.val<r.val)
            return SegTree[indxInTree]=new pair(l.val,l.ind);
        return SegTree[indxInTree]=r;
    }*/
    static void update(int ind) {
        update2(ind, 0, arr2.size() - 1, 1);

    }

    static long update2(int ind, int beg, int end, int indin) {

        if (beg == end) {
            int a = arr2.get(beg);
            long big=0;
            if(beg<arr2.size()-1)
            big = query(beg + 1, arr2.size() - 1);
            big = (a *(1+big)) % mod;
            long old = SegTree[indin];
            SegTree[indin]=(SegTree[indin]*a)%mod;
            SegTree[indin]=(big+SegTree[indin])%mod;
            long dif= (SegTree[indin] - old)<0?(SegTree[indin] - old)+mod:(SegTree[indin] - old);
            return dif;

        }
        int mid = (beg + end) >> 1;
        if (ind <= mid) {
            long l = update2(ind, beg, mid, indin << 1);
            SegTree[indin] = (SegTree[indin]+l)%mod;
            return l;
        }

        long r = update2(ind, mid + 1, end, (indin << 1) + 1);
        SegTree[indin] = (SegTree[indin]+r)%mod;
        return r;
    }

    static long query(int beg, int end) {
        return query2(beg, end, 0, arr2.size() - 1, 1);
    }

    static long query2(int begq, int endq, int begI, int endI, int indxInTree) {
        int mid = (begI + endI) >> 1;
        if (begI >= begq && endI <= endq) {

            return SegTree[indxInTree];
        }

        if (endq <= mid) {
            //System.out.println(begI+" "+mid+" "+begq+" "+endq);
            return query2(begq, endq, begI, mid, indxInTree << 1);
        }
        if (begq > mid)
            return query2(begq, endq, mid + 1, endI, (indxInTree << 1) | 1);
        long l = query2(begq, mid, begI, mid, indxInTree << 1);
        long r = query2(mid + 1, endq, mid + 1, endI, (indxInTree << 1) + 1);
        return (l + r)%mod;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        PrintWriter out = new PrintWriter(System.out);
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        TreeSet<Integer> ts = new TreeSet<>();
        HashMap<Integer, Integer> hm = new HashMap<>();
        arr2 = new ArrayList<>();
        arr = new int[n];
        st=new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(st.nextToken());
            arr[i] = x;
            ts.add(x);
        }
        // System.out.println(1);
        int ind = 0;
        for (int x : ts) {
            hm.put(x, ind++);
            arr2.add(x);
        }
        buildSegTree();
        for (int i = arr.length - 1; i >= 0; i--) {
            update(hm.get(arr[i]));
        }
        out.println(SegTree[1]);

        out.flush();
    }
}
