We are looking for variable subsequences of a given sequence $a = (a_{1}, a_{2}, ..., a_{n})$. A subsequence is obtained from a sequence by removing any number of its terms (possibly 0). More formally, a subsequence of the sequence a is any sequence $(a_{i_{1}}, a_{i_{2}}, ..., a_{i_{k}})$, for which $1 ≤ i_{1} < i_{2} < ... < i_{k} ≤ n$ A variable subsequence is a subsequence such that every two its consecutive terms are different. For example, the sequence (1, 3, 1, 2) is a variable subsequence of the sequence (1, 2, 3, 1, 3, 2, 2).
We would like to know how many distinct and nonempty variable subsequences of a given sequence are there. Two subsequences are considered distinct if the sets of positions in a corresponding to them are different. For instance, the sequence (1, 2, 3, 1, 3, 2, 2) contains two distinct variable subsequences of the form (1, 3, 1, 2).
Input Format
The first line of the standard input contains one integer $n$ ($2 ≤ n ≤ 500\,000$), denoting the length of the sequence $a$. The second line contains $n$ integers $a_{i}$ ($1 ≤ a_{i} ≤ 500\,000$).
Output Format
Your program should write to the first and only line of the standard output a single integer: the number of nonempty variable subsequences of the input sequence modulo $10^{9} + 7$.
Example
Input
4 1 2 1 1
Output
9
Notes
The considered subsequences of the sequence (1, 2, 1, 1) are:
- (1) - counted three times,
- (2) - counted once,
- (1, 2) - counted once,
- (2, 1) - counted twice and
- (1, 2, 1) - counted twice.