Codeforces Round #416 (Div. 2) has been moved to start on 27.05.2017 09:05 (UTC).
×

No tag edit access

C. Sereja and Subsequences

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputSereja has a sequence that consists of *n* positive integers, *a*_{1}, *a*_{2}, ..., *a*_{n}.

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* = *x*_{1}, *x*_{2}, ..., *x*_{r} doesn't exceed a sequence of positive integers *y* = *y*_{1}, *y*_{2}, ..., *y*_{r}, if the following inequation holds: *x*_{1} ≤ *y*_{1}, *x*_{2} ≤ *y*_{2}, ..., *x*_{r} ≤ *y*_{r}.

Now Sereja wonders, how many sequences are written on the lines piece of paper. Help Sereja, find the required quantity modulo 1000000007 (10^{9} + 7).

Input

The first line contains integer *n* (1 ≤ *n* ≤ 10^{5}). The second line contains *n* integers *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 10^{6}).

Output

In the single line print the answer to the problem modulo 1000000007 (10^{9} + 7).

Examples

Input

1

42

Output

42

Input

3

1 2 2

Output

13

Input

5

1 2 3 4 5

Output

719

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/26/2017 06:33:18 (c2).

Desktop version, switch to mobile version.
User lists

Name |
---|