P3970 [TJOI2014] Increasing Subsequences

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\}$.

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

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$.

### Constraints For $30\%$ of the testdata, $n \le 5000$. For $100\%$ of the testdata, $n \le 10^5$. Translated by ChatGPT 5