H. KMP
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Peter has a sequence $$$S$$$ of numbers of length $$$N$$$ and he wonders how many kompakt subsequences are there in his sequence.

A subsequence of $$$S$$$ is a non-empty sequence $$$S_{p_1}, S_{p_2}, \ldots, S_{p_K}$$$ with $$$1 \le p_1 \lt p_2 \lt \ldots \lt p_K \le N$$$ for some $$$1 \le K \le N$$$. Two subsequences $$$S_{p_1}, S_{p_2}, \ldots, S_{p_K}$$$ and $$$S_{q_1}, S_{q_2}, \ldots, S_{q_L}$$$ are different if the sequences $$$p$$$ and $$$q$$$ are different (either $$$K \ne L$$$, of there exists $$$1 \le i \le K$$$ such that $$$p_i \ne q_i$$$).

A sequence is kompakt if it consists only of different values and it contains every integer value between the minimum number in the sequence and the maximum number in the sequence. For example, sequences $$$[1, 2]$$$ and $$$[7, 9, 8]$$$ are kompakt, but sequences $$$[1, 3]$$$ and $$$[7, 9, 6]$$$ are not.

Help Peter count the number of kompakt subsequences in $$$S$$$.

Input

The first line of the input contains $$$1 \le N \le 10^5$$$, the length of the sequence.

The second line of the input contains $$$N$$$ integers, $$$S_1, S_2, \ldots, S_N$$$, representing Peter's sequence.

$$$1 \le S_i \le 10^5$$$ for all $$$1 \le i \le N$$$.

Input

The first line of the input contains $$$1 \le N \le 10^5$$$, the length of the sequence.

The second line of the input contains $$$N$$$ integers, $$$S_1, S_2, \ldots, S_N$$$, representing Peter's sequence.

$$$1 \le S_i \le 10^5$$$ for all $$$1 \le i \le N$$$.

Output

The only line in the output should contain an integer representing the number of kompakt sequences in $$$S$$$. Since the number might be too big, print the answer modulo $$$10^9 + 7$$$.

Examples
Input
6
15 16 18 15 8 19
Output
9
Input
8
7 1 9 11 2 10 8 10
Output
26
Note

The kompakt subsequences in the first example are: $$$[15], [16], [18], [15], [8], [19], [15, 16], [16, 15], [18, 19]$$$