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.*;

public class C {

	class IntervalTree {
		long mod = (long) (1e+9 + 7);
		int n;
		long[] sum;

		public IntervalTree(int n) {
			this.n = n + 1;
			sum = new long[4 * n + 1];
			update(0, 1);
		}

		void update(int pos, long val) {
			update(0, n - 1, pos, 1, val);
		}

		long get(int l, int r) {
			return get(0, n - 1, l, r, 1);
		}

		void update(int l, int r, int pos, int i, long val) {
			if (l == r) {
				sum[i] = val % mod;
				return;
			}
			if (pos <= (l + r) / 2) {
				update(l, (l + r) / 2, pos, i * 2, val);
			} else {
				update((l + r) / 2 + 1, r, pos, i * 2 + 1, val);
			}
			sum[i] = (sum[i * 2] + sum[i * 2 + 1]) % mod;
		}

		long get(int l, int r, int l1, int r1, int i) {
			if (l1 > r) {
				return 0;
			}
			if (r1 < l) {
				return 0;
			}
			if (l1 < l) {
				l1 = l;
			}
			if (r1 > r) {
				r1 = r;
			}
			if (l == l1 && r == r1) {
				return sum[i];
			}
			return (get(l, (l + r) / 2, l1, r1, i * 2) + get((l + r) / 2 + 1,
					r, l1, r1, i * 2 + 1)) % mod;
		}

	}

	class Situation implements Comparable<Situation> {
		int val;
		int pos;

		public int compareTo(Situation arg0) {
			if (val == arg0.val) {
				return pos - arg0.pos;
			}
			return val - arg0.val;
		}

		public Situation(int val, int pos) {
			super();
			this.val = val;
			this.pos = pos;
		}
	}

	void solve() throws IOException {
		int n = nextInt();
		int[] a = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			a[i] = nextInt();
		}
		Situation[] s = new Situation[n];
		for (int i = 1; i <= n; i++) {
			s[i - 1] = new Situation(a[i], i);
		}

		IntervalTree t = new IntervalTree(n);
		Arrays.sort(s);
		for (int i = 0; i < n;) {
			int j = i;
			int prev = 0;
			while (j < n && s[j].val == s[i].val) {
				int cur = s[j].pos;
				t.update(cur, s[j].val * t.get(prev, cur - 1));
				prev = cur;
				j++;
			}
			i = j;
		}
		out.println(t.get(1, n));

	}

	void run() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	public static void main(String[] args) throws IOException {
		new C().run();
	}

	BufferedReader br;
	PrintWriter out;
	StringTokenizer str;

	String next() throws IOException {
		while (str == null || !str.hasMoreTokens()) {
			str = new StringTokenizer(br.readLine());
		}
		return str.nextToken();
	}

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

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

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

}
