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

输入描述:

The first line contains integer n(1 ≤ n ≤ 105). The second line contains n integers a1, a2, ..., an(1 ≤ ai ≤ 106).

输出描述:

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