Breaking the Cipher

Sherlock Holmes can solve any puzzle, but not every mystery yields at once. Half a year ago a courier brought him a letter written in a cipher. The letter had no key. The return address on the envelope was unusually long: instead of a street and house number, it listed $n$ numbers. Holmes tried everything, and none of it helped.

This morning Inspector Lestrade was waiting at Holmes's door with news. Scotland Yard had caught a member of the gang of the mysterious Professor M., and the man agreed to reveal the cipher used in the criminal network in exchange for a lighter sentence. Like all brilliant things, the cipher turned out to be very simple. The key is the sum, over all subsegments, of the number of distinct subsequences that can be formed using only the numbers of that subsegment.

A subsegment of a sequence of length $n$ is a pair $l, r$ with $1 \le l \le r \le n$, written $[l, r]$. A subsequence of $[l, r]$ is a collection $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ (possibly empty) with $l \le i_1 < i_2 < \ldots < i_k \le r$. Two subsequences $a_i$ and $a_j$ are considered different if they have different lengths, or if there is a $k$ such that $a_{i_k} \ne a_{j_k}$.

Since the number may be very large, output it modulo $1\,000\,000\,007$. Holmes is not strong in mathematics, so he needs your help finding the key.

The first line contains one integer $n$ ($1 \le n \le 100\,000$), the length of the sequence.

The second line contains $n$ integers $a_i$ ($1 \le a_i \le 100\,000$), the elements of the sequence.

Print the key modulo $1\,000\,000\,007$ on a single line.

Explanation of the first sample:

For the multiset $\{1, 1, 2\}$ there are six subsegments.

• Subsegment $[1, 1]$ is $\{1\}$ (2 subsequences: $\{\}$, $\{1\}$).
• Subsegment $[2, 2]$ is $\{1\}$ (2 subsequences: $\{\}$, $\{1\}$).
• Subsegment $[3, 3]$ is $\{2\}$ (2 subsequences: $\{\}$, $\{2\}$).
• Subsegment $[1, 2]$ is $\{1, 1\}$ (3 subsequences: $\{\}$, $\{1\}$, $\{1, 1\}$).
• Subsegment $[2, 3]$ is $\{1, 2\}$ (4 subsequences: $\{\}$, $\{1\}$, $\{2\}$, $\{1, 2\}$).
• Subsegment $[1, 3]$ is $\{1, 1, 2\}$ (6 subsequences: $\{\}$, $\{1\}$, $\{2\}$, $\{1, 1\}$, $\{1, 2\}$, $\{1, 1, 2\}$).

The answer is $2+2+2+3+4+6=19$.