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.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author coderbd
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskC {
    public static long MOD = 1000000007L;
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int[] a = new int[n];
        FenwickTree tree = new FenwickTree(1000001);
        for (int i = 0; i < n; i++) {
            a[i] = in.readInt();
            long cnt = (tree.query(1, a[i]) % MOD * a[i] + a[i]) % MOD;
            tree.update(a[i], a[i], -tree.query(a[i], a[i]));
            tree.update(a[i], a[i], cnt);
        }
        long sum = 0L;
        int prev = -1;
        Arrays.sort(a);
        for (int i = 0; i < n; i++) {
            if (prev == a[i])
                continue;
            prev = a[i];
            sum += tree.query(a[i], a[i]);
            sum %= MOD;
        }
        out.printLine(sum);
    }
}

class InputReader {

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

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

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

    public int readInt() {
        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 static boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    }

class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object...objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0)
                writer.print(' ');
            writer.print(objects[i]);
        }
    }

    public void printLine(Object...objects) {
        print(objects);
        writer.println();
    }

    public void close() {
        writer.close();
    }

    }

class FenwickTree {

    private long[] tree1;
    private long[] tree2;
    private int size;

    public FenwickTree(int size) {
        this.size = size;
        tree1 = new long[size];
        tree2 = new long[size];
        Arrays.fill(tree1, 0L);
        Arrays.fill(tree2, 0L);
    }

    public void update(int start, int end, long delta) {
        update1(start, delta);
        update1(end + 1, -delta);
        update2(start, start * delta);
        update2(end + 1, -delta * (end + 1));
    }

    private void update1(int id, long delta) {
        for (int i = id; i < size; i += i & -i)
            tree1[i] += delta;
    }

    private void update2(int id, long delta) {
        for (int i = id; i < size; i += i & -i)
            tree2[i] += delta;
    }

    private long query(int id) {
        return (id + 1) * query1(id) - query2(id);
    }

    private long query1(int id) {
        long res = 0l;
        for (int i = id; i > 0; i -= i & -i)
            res += tree1[i];
        return res;
    }

    private long query2(int id) {
        long res = 0l;
        for (int i = id; i > 0; i -= i & -i)
            res += tree2[i];
        return res;
    }

    public long query(int start, int end) {
        return query(end) - query(start - 1);
    }

}

