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 FenwickTree(object):

    """Interface for Binary-Indexed Tree, which stores
    cumulative frequency tables. Note that original data
    is not preserved in this data structure.
    Construction takes O(n lg n) time;
    Item access takes O(lg n) time;
    Item update takes O(lg n) time."""

    def __init__(self):
        self.tree = [0]

    def __len__(self):
        return len(self.tree) - 1

    def __getitem__(self, key):
        """
        Example: In list [1,2,3,4], FT[3] returns 6.
        :param key: 1-based index
        :return: cumulative sum up to key-th item
        """
        psum = 0
        while key > 0:
            psum += self.tree[key]
            key -= (key & -key)
        return psum

    def add(self, key, value):
        """
        Example: FT.add(3,5) modifies list [1,2,3,4] to [1,2,8,4]
        :param key: 1-based index
        :param value: value to be modified to
        :return: None
        """
        while key <= len(self):
            self.tree[key] += value
            key += (key & -key)

    def append(self, value):
        """
        Example: FT.append(5) turns list [1,2,3,4] to [1,2,3,4,5]
        :param value: value to be appended
        :return: None
        """
        ln = len(self)
        large = self[ln]
        small = self[(ln + 1) - ((ln + 1) & -(ln + 1))]
        self.tree.append(large - small + value)

# Above imported from Common Algorithms library.
n = int(input())
a = sorted(map(int, input().split()))
q = [0] * (a[-1] + 1)
FT = FenwickTree()
for x in q:
    FT.append(x)
for x in a:
    v = FT[x] * x + x
    FT.add(x, v - q[x])
    q[x] = v
print(FT[a[-1]])