Algorytmy 2
Unikalne podciągi
Dany jest ciąg $A = (a_1, a_2, \ldots, a_n)$. Znajdź liczbę jego różnych podciągów.
Formalnie, niech $\textrm{Subseq}(A)$ będzie zbiorem wszystkich podciągów $A$. Znajdź $|\textrm{Subseq}(A)|$.
Podciągiem nazwiemy ciąg powstały poprzez usunięcie pewnej liczby (być może $0$ lub $n$) elementów z oryginalnego ciągu.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $n$. Drugi wiersz zawiera $n$ liczb całkowitych $a_i$.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą – resztę z dzielenia liczby unikalnych podciągów ciągu $a_i$ przez $10^9+7$.
Ograniczenia
- $1 \le n \le 10^6$
- $0 \le a_i \le 10^5$
Przykłady
Wejście 1
3
1 1 2
Wyjście 1
6