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 Zhipeng Jia
 */
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 {
	private static final int modulo = 1000000007;
	private long[] sum;
	private long[] delta;

	private void pushDown(int i, int l, int r) {
		if (delta[i] == 0) return;
		int mid = (l + r) / 2;
		sum[i * 2] = (sum[i * 2] + (mid - l) * delta[i]) % modulo;
		delta[i * 2] = (delta[i * 2] + delta[i]) % modulo;
		sum[i * 2 + 1] = (sum[i * 2 + 1] + (r - mid) * delta[i]) % modulo;
		delta[i * 2 + 1] = (delta[i * 2 + 1] + delta[i]) % modulo;
		delta[i] = 0;
	}

	private void change(int i, int l, int r, int x, long val) {
		if (l + 1 == r) {
			sum[i] = val;
			return;
		}
		pushDown(i, l, r);
		int mid = (l + r) / 2;
		if (x < mid) {
			change(i * 2, l, mid, x, val);
		} else {
			change(i * 2 + 1, mid, r, x, val);
		}
		sum[i] = (sum[i * 2] + sum[i * 2 + 1]) % modulo;
	}

	private void increaseRange(int i, int l, int r, int l0, int r0, long d) {
		if (l0 <= l && r <= r0) {
			delta[i] = (delta[i] + d) % modulo;
			sum[i] = (sum[i] + (r - l) * d) % modulo;
			return;
		}
		pushDown(i, l, r);
		int mid = (l + r) / 2;
		if (l0 < mid) increaseRange(i * 2, l, mid, l0, r0, d);
		if (r0 > mid) increaseRange(i * 2 + 1, mid, r, l0, r0, d);
		sum[i] = (sum[i * 2] + sum[i * 2 + 1]) % modulo;
	}

	private long getValue(int i, int l, int r, int x) {
		if (l + 1 == r) return sum[i];
		pushDown(i, l, r);
		int mid = (l + r) / 2;
		if (x < mid) {
			return getValue(i * 2, l, mid, x);
		} else {
			return getValue(i * 2 + 1, mid, r, x);
		}
	}

	public void solve(int testNumber, InputReader in, OutputWriter out) {
		int n = in.readInt();
		int[] a = in.readIntArray(n);
		sum = new long[1 << 21];
		Arrays.fill(sum, 0);
		delta = new long[1 << 21];
		Arrays.fill(delta, 0);
		boolean[] have = new boolean[1000001];
		Arrays.fill(have, false);
		long ans = 0;
		for (int i = 0; i < n; i ++) {
			long tmp = getValue(1, 0, 1000001, a[i]);
			if (! have[a[i]]) {
				have[a[i]] = true;
				tmp = (tmp + 1) % modulo;
			}
			tmp = tmp * a[i] % modulo;
			ans = (ans + tmp) % modulo;
			change(1, 0, 1000001, a[i], tmp);
			if (a[i] < 1000000) {
				increaseRange(1, 0, 1000001, a[i] + 1, 1000001, tmp);
			}
		}
		out.printLine(ans);
	}
}

class InputReader {
	private InputStream stream;
	private byte[] buf = new byte[1000];
	private int curChar;
	private int numChars;

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

	private int read() {
		if (numChars == -1)
			throw new UnknownError();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new UnknownError();
			}
			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 int[] readIntArray(int length) {
		int[] res = new int[length];
		for (int i = 0; i < length; i ++) res[i] = readInt();
		return res;
	}

	private 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();
	}
}

