Kubki

Gra w 3 kubki polega na tym, że osoba organizująca ukrywa kulkę pod jednym z kubków i potem szybko zmienia ustawienia kubków – gracze mają za zadanie odgadnąć, gdzie jest kulka.
Bajtocki Mistrz Gier postanowił tę grę utrudnić. Przede wszystkim używa N ( 1 <= N <= 10^6 ) kubków. Poza tym, pod każdym znajduje się kulka – każda kulka jest jedyna i wyjątkowa. W jednej turze Mistrz zmienia położenia wszystkich kubków. Masz za zadanie zatrzymać grę, gdy wszystkie kulki wrócą na swoje miejsca.

Aby przygotować się do tego wyzwania, obserwowałeś przebieg gry – zauważyłeś, że w każdym ruchu Mistrz zamienia kubki w ten sam sposób. Kubki znajdują się na pozycjach ponumerowanych od 1 do N. Mistrz przesuwa kubek z pozycji i (1 <= i <= N) na pozycję Ki (1 <= Ki <= N). Znasz Ki dla każdego i od 1 do N. Oczywiście, na każdej pozycji stoi zawsze tylko jeden kubek. Napisz program, który obliczy po ilu turach wszystkie kulki w kubkach wróca na pozycję początkową.

Bajtocki Mistrz Gier jest tak pewny swego zwycięstwa, że w testach wartych 60% punktów zmniejszył liczbę kubków poniżej 10000.

Wejście

W pierszej słoniowej linii wejścia znajduje się jedna liczba całkowita N ( 1 <= N <= 10^6 ) oznaczająca liczbę kulek (i kubków). W następnej linii znajduje się N liczb całkowitych Ki (1 <= Ki <= N). i-ta z tych liczb oznacza, że że kubek, który przed zmianą stał na i-tej pozycji po zmianie przesunie się na pozycję Ki.

Wyjście

W jedynej linii wyjścia podaj resztę z dzielenia liczby tur (najmniejszej, ale nie 0), po których wszystkie kulki znajdą się na swoich początkowych miejscach, przez (10^9 + 9).

Przykład


Dla danych:
4                                                                                                                                
1 3 4 2

Poprawnym wyjściem jest:
3

Ustawienie kubków w kolejnych turach prezentuje się tak:
1 2 3 4
1 4 2 3
1 3 4 2
1 2 3 4