Sereja has a sequence that consists of *n* positive integers, *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>. 

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*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub>, ..., *x*<sub class="lower-index">*r*</sub> doesn't exceed a sequence of positive integers *y* = *y*<sub class="lower-index">1</sub>, *y*<sub class="lower-index">2</sub>, ..., *y*<sub class="lower-index">*r*</sub>, if the following inequation holds: *x*<sub class="lower-index">1</sub> ≤ *y*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub> ≤ *y*<sub class="lower-index">2</sub>, ..., *x*<sub class="lower-index">*r*</sub> ≤ *y*<sub class="lower-index">*r*</sub>.

Now Sereja wonders, how many sequences are written on the lines piece of paper. Help Sereja, find the required quantity modulo 1000000007 (10<sup class="upper-index">9</sup> + 7).
The first line contains integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>). The second line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">6</sup>).
BIT = [0] * (1000001)
dp = [0] * (1000001)
MOD = 1000000007
ans = 0
def query(p):
    ret = 0
    i = p
    while i:
        ret = (ret + BIT[i]) % MOD
        i -= i & -i
    return ret
def update(p, v):
    i = p
    while (i <= 1000000):
        BIT[i] = (BIT[i] + v) % MOD
        i += i & -i
N = int(input())
arr = list(map(int, input().split()))
for i in range(N):
    cur = ((query(arr[i]) + 1) * arr[i]) % MOD
    #print(cur, dp[arr[i]], cur - dp[arr[i]])
    update(arr[i], (cur - dp[arr[i]]) % MOD)
    dp[arr[i]] = cur
    
print(query(1000000))
