Podciągi zmienne

Limit pamięci: 32 MB

W danym ciągu poszukujemy podciągów zmiennych. Podciąg ciągu otrzymujemy, usuwając z niego dowolną liczbę wyrazów (potencjalnie zero). Formalnie, podciągiem ciągu jest dowolny ciąg , przy czym . Natomiast podciąg zmienny charakteryzuje się tym, że jego każde dwa kolejne wyrazy są różne. Dla przykładu, ciąg jest podciągiem zmiennym ciągu .

Zastanawiamy się, ile różnych i niepustych podciągów zmiennych zawiera dany ciąg. Podciągi uważamy za różne, jeśli zostały wybrane z innych zestawów pozycji w ciągu . Przykładowo, ciąg zawiera dwa różne podciągi zmienne postaci .

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba naturalna (), oznaczająca długość ciągu . Drugi wiersz zawiera liczb całkowitych ().

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę całkowitą: resztę z dzielenia przez liczby niepustych podciągów zmiennych ciągu podanego na wejściu.

Przykład

Dla danych wejściowych:

4
1 2 1 1

poprawną odpowiedzią jest:

9

Wyjaśnienie do przykładu: Szukanymi podciągami ciągu są:

• - wliczany trzykrotnie,
• - wliczany raz,
• - wliczany raz,
• - wliczany dwukrotnie oraz
• - wliczany dwukrotnie.

Autor zadania: Jakub Radoszewski.