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

class FT:
    def __init__(self):
        self.data = [0] * 1000009
    def add(self, idx, v):
        while idx <= len(self.data):
            self.data[idx] += v
           
            idx += idx & -idx
    def query(self, idx):
        ret = 0
        while idx > 0:
            ret += self.data[idx]
            ret %= MOD
            idx -= idx & -idx
        return ret
    def query_r(self, l, r):
        return query(self, r) - query(self, l - 1)

n = int(input())
MOD = 1000000007
table = FT()
table2 = [0] * 1000009

for i, v in enumerate(map(int, input().split())):
    t = ((1 + table.query(v)) * v - table2[v]) % MOD
    if t < 0: t += MOD
    table.add(v, t)
    table2[v] = t
print(table.query(1000008))
