Algorytmy 2
Unikalne podciągi
Dany jest ciąg $a_1, a_2, \ldots, a_n$. Znajdź liczbę jego unikalnych podciągów. 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