Description

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

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

If two increasing subsequences are identical, count them only once. For example, the sequence $\{1,2,3,3\}$ has $4$ increasing subsequences: $\{1,2\}$, $\{1,3\}$, $\{1,2,3\}$, $\{2,3\}$.

Input Format

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

Output Format

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

4
1 2 3 3

4

Hint

Constraints

For $30\%$ of the testdata, $n \le 5000$.

For $100\%$ of the testdata, $n \le 10^5$.

Translated by ChatGPT 5