P6570 [NOI Online #3 Senior] Excellent Subsequences

Given a non-negative integer sequence $A=\{a_1,a_2,\cdots,a_n\}$ of length $n$. For a subsequence of $A$, $B=\{a_{b_1},a_{b_2},\cdots,a_{b_m}\}$ ($0\le m\le n$, $1\le b_1

The first line contains a positive integer $n$, denoting the length of the sequence. The second line contains $n$ non-negative integers separated by spaces, denoting $a_1,a_2,\cdots,a_n$.

Only one line with one integer, denoting the result of the answer modulo $10^9+7$.

#### Explanation for Sample 1 The valid subsequences are: $\emptyset$, $\{1\}$, $\{2\}$, $\{2\}$, $\{3\}$, $\{1,2\}$, $\{1,2\}$. Their values are $1$, $1$, $2$, $2$, $2$, $2$, $2$, respectively, and the total sum is $12$. #### Constraints - For $10\%$ of the testdata, it is guaranteed that $a_i\le 1$. - For $30\%$ of the testdata, it is guaranteed that $a_i\le 1000$. - For $60\%$ of the testdata, it is guaranteed that $a_i\le 30000$. - There is another $10\%$ of the testdata where it is guaranteed that $n\le 20$. - For $100\%$ of the testdata, it is guaranteed that $1\le n\le 10^6$ and $0\le a_i\le 2\times 10^5$. Translated by ChatGPT 5