Given a sequence containing only integers (where the absolute value of each element does not exceed $10^9$), you need to calculate the number of increasing subsequences that satisfy the following conditions:

1. It is a subsequence of the original sequence.
2. The length is at least 2.
3. All elements are strictly increasing.

If two increasing subsequences are identical, they should only be counted once. For example, the sequence $\{1, 2, 3, 3\}$ has 4 increasing subsequences: $\{1, 2\}$, $\{1, 3\}$, $\{1, 2, 3\}$, and $\{2, 3\}$.

Input

The first line contains an integer $n$, representing the length of the sequence. The next line contains $n$ integers, representing the sequence.

Output

Output a single line containing the number of increasing subsequences. Since the answer can be very large, output the answer modulo $10^9 + 7$.

Constraints

For 30% of the data, $N \le 5000$.

For 100% of the data, $N \le 10^5$.

Examples

Input 1

4
1 2 3 3

Output 1

4