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.*;
import java.util.*;
import java.math.*;

public class C implements Runnable {
	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer st;
	static Random rnd;

	final int maxValue = 1000010;
	final static long MOD = 1000000000 + 7;

	static class SegmentTree {
		long[] data;

		public SegmentTree(int size) {
			data = new long[4 * size];
		}

		private static final int left(int v) {
			return (v + v);
		}

		private static final int right(int v) {
			return ((v + v) | 1);
		}

		private static final int middle(int l, int r) {
			return ((l + r) >> 1);
		}

		public long sum(int v, int l, int r, int tl, int tr) {
			if (l == tl && r == tr)
				return data[v];

			int m = middle(l, r);
			long res = 0;

			if (tl <= m) {
				res = sum(left(v), l, m, tl, Math.min(tr, m));
				if (res >= MOD)
					res -= MOD;
			}

			if (tr > m) {
				res += sum(right(v), m + 1, r, Math.max(tl, m + 1), tr);
				if (res >= MOD)
					res -= MOD;
			}

			return res;
		}

		public void add(int v, int l, int r, int ind, long val) {
			if (l == r) {
				data[v] += val;
				if (data[v] >= MOD)
					data[v] -= MOD;
			} else {
				int m = middle(l, r);
				if (ind <= m)
					add(left(v), l, m, ind, val);
				else
					add(right(v), m + 1, r, ind, val);
				data[v] = data[left(v)] + data[right(v)];
				if (data[v] >= MOD)
					data[v] -= MOD;
			}
		}
	}

	void solve() throws IOException {
		int n = nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = nextInt();

		SegmentTree ways = new SegmentTree(maxValue);
		ways.add(1, 0, maxValue - 1, 0, 1);

		for (int i = 0; i < n; i++) {
			long sum = ways.sum(1, 0, maxValue - 1, 0, arr[i]);
			//out.println(sum);
			long diff = safeMod(sum * arr[i]
					- ways.sum(1, 0, maxValue - 1, arr[i], arr[i]));

			ways.add(1, 0, maxValue - 1, arr[i], diff);
		}

		long res = ways.sum(1, 0, maxValue - 1, 1, maxValue - 1);

		out.println(res);

	}

	private long safeMod(long l) {
		l %= MOD;
		l += MOD;
		l %= MOD;
		return l;
	}

	public static void main(String[] args) {
		// final boolean oldChecker = false;
		//
		// if (oldChecker)
		// new Thread(null, new Template(), "yarrr", 1 << 24).start();
		// else
		new C().run();
	}

	public void run() {
		try {
			// final String className = this.getClass().getName().toLowerCase();

			// try {
			// in = new BufferedReader(new FileReader(className + ".in"));
			// out = new PrintWriter(new FileWriter(className + ".out"));
			// in = new BufferedReader(new FileReader("input.txt"));
			// out = new PrintWriter(new FileWriter("output.txt"));
			// } catch (FileNotFoundException e) {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			// }

			rnd = new Random();

			solve();

			out.close();
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	String nextToken() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			String line = in.readLine();

			if (line == null)
				return null;

			st = new StringTokenizer(line);
		}

		return st.nextToken();
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
}