Sereja 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)$.