CF314C.Sereja and Subsequences

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 (109 + 7).

谢列亚有一个由 $ n $ 个正整数组成的序列：$ a_1, a_2, \ldots, a_n $。

首先，谢列亚取了一张方格纸，并在上面写下了序列 $ a $ 的所有互不相同、非空、非递减的子序列。接着，对于方格纸上写出的每一个序列，谢列亚又在一张横线纸上写下了所有不超过它的序列。

一个正整数序列 $ x = x_1, x_2, \ldots, x_r $ 不超过另一个正整数序列 $ y = y_1, y_2, \ldots, y_r $，当且仅当满足如下不等式：

$$x_1 \le y_1,\; x_2 \le y_2,\; \ldots,\; x_r \le y_r.$$

现在谢列亚想知道：横线纸上一共写下了多少个序列？请帮助谢列亚求出该数量对 $ 1000000007 $（即 $ 10^9 + 7 $）取模的结果。

The first line contains integer n (1 ≤ n ≤ 105). The second line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 106).

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^6$）。

In the single line print the answer to the problem modulo 1000000007 (109 + 7).

在单行中输出该问题的答案对 1000000007（$10^9 + 7$）取模的结果。