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.*;
import java.awt.geom.*;

import static java.lang.Math.*;

public class Solution implements Runnable {
	
	static final int MOD = 1000000007;
	
	class SegmentTree {
		
		class Node {
			
			int sum;
			Node left, right;
			
			public Node(int sum) {
				this.sum = sum;
			}
			
			public Node (Node left, Node right) {
				this.left = left;
				this.right = right;
				this.sum = (left.sum + right.sum) % MOD;
			}
			
		}

		int n;
		ArrayList<Node> versions = new ArrayList<>();
		
		private Node build (int tl, int tr) {
			if (tl == tr) {
				if (tl == 0) return new Node (1);
				return new Node (0);
			} else {
				int tm = (tl + tr) >> 1;
				Node left = build (tl, tm);
				Node right = build (tm + 1, tr);
				return new Node (left, right);
			}
		}
		
		private Node update (Node t, int tl, int tr, int pos, int val) {
			if (tl == tr) {
				return new Node ((val + t.sum) % MOD);
			} else {
				int tm = (tl + tr) >> 1;
				if (pos <= tm) {
					Node left = update (t.left, tl, tm, pos, val);
					return new Node (left, t.right);
				} else {
					Node right = update (t.right, tm + 1, tr, pos, val);
					return new Node (t.left, right);
				}
			}
		}
		
		public void update (int version, int pos, int val) {
			versions.add(update (versions.get(version), 0, n - 1, pos, val));
		}
		
		private int get (Node t, int tl, int tr, int l, int r) {
			if (l > r) return 0;
			if (l == tl && r == tr)
				return t.sum;
			int tm = (tl + tr) >> 1;
			return (get (t.left, tl, tm, l, min (r, tm)) + get (t.right, tm + 1, tr, max (l, tm + 1), r)) % MOD;
		}
		
		public int get (int version, int l, int r) {
			return get (versions.get(version), 0, n - 1, l, r);
		}
		
		public SegmentTree(int n) {
			this.n = n;
			versions.add(build(0, n - 1));
		}
		
	}
	
	public void solve() throws Exception {
		int n = sc.nextInt();
		int pos [] = new int [1000001];
		Arrays.fill(pos, -1);
		SegmentTree tree = new SegmentTree(1000001);
		long ans = 0;
		for (int i = 1; i <= n; i++) {
			int num = sc.nextInt();
			long sum = tree.get(i - 1, 0, num);
			if (pos[num] != -1) {
				sum = (sum - tree.get(pos[num] - 1, 0, num) + MOD) % MOD;
			}
			pos[num] = i;
			long multi = sum * num;
			multi %= MOD;
			ans = (ans + multi) % MOD;
			tree.update(i - 1, num, (int) multi);
		}
		out.println(ans);
	}

	BufferedReader in;
	PrintWriter out;
	FastScanner sc;

	static Throwable uncaught;

	@Override
	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			sc = new FastScanner(in);
			solve();
		} catch (Throwable t) {
			Solution.uncaught = t;
		} finally {
			out.close();
		}
	}

	public static void main(String[] args) throws Throwable {
		Thread t = new Thread(null, new Solution(), "", (1 << 26));
		t.start();
		t.join();
		if (uncaught != null) {
			throw uncaught;
		}
	}

}

class FastScanner {

	BufferedReader reader;
	StringTokenizer strTok;

	public FastScanner(BufferedReader reader) {
		this.reader = reader;
	}

	public String nextToken() throws IOException {
		while (strTok == null || !strTok.hasMoreTokens()) {
			strTok = new StringTokenizer(reader.readLine());
		}
		return strTok.nextToken();
	}

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

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

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

}
