Turniejem nazywamy graf skierowany, w którym:

• dla dowolnych dwóch różnych wierzchołków u i v istnieje dokładnie jedna krawędź pomiędzy tymi wierzchołkami (tzn. albo u -> v, albo v -> u),
• nie istnieją pętle (tzn. dla dowolnego wierzchołka u nie ma krawędzi u-> u ).

Oznaczmy przez p dowolną permutację zbioru wierzchołków turnieju. (Permutacją skończonego zbioru X nazywamy każdą różnowartościową funkcję z X w X.) Permutację p nazywamy automorfizmem, jeżeli dla dowolnych dwóch różnych wierzchołków u i v zwrot krawędzi pomiędzy u i v jest taki sam, jak pomiędzy p(u) i p(v) (tzn. u -> v jest krawędzią w turnieju wtedy i tylko wtedy, gdy p(u) -> p(v) jest krawędzią w tym turnieju). Dla zadanej permutacji p interesuje nas, dla ilu turniejów jest ona automorfizmem.

Przykład

Weźmy zbiór wierzchołków oznaczonych liczbami 1,...,4 oraz permutację p:

Istnieją tylko cztery turnieje, dla których ta permutacja jest automorfizmem:

Zadanie

Napisz program, który:

• z pliku tekstowego AUT.IN wczyta opis permutacji n-elementowego zbioru wierzchołków,
• obliczy liczbę t różnych n-wierzchołkowych turniejów, dla których ta permutacja jest automorfizmem,
• zapisze w pliku tekstowym AUT.OUT resztę z dzielenia t przez 1000

Wejście

W pierwszym wierszu pliku tekstowego AUT.IN znajduje się jedna liczba naturalna n, 1<=n<= 10000, będąca liczbą wierzchołków. W kolejnych n wierszach znajduje się opis permutacji p. Zakładamy, że wierzchołki są ponumerowane liczbami od 1 do n. W wierszu (k+1)-szym znajduje się wartość permutacji p dla wierzchołka nr k (tzn. wartość p(k)).

Wyjście

W pierwszym i jedynym wierszu pliku tekstowego AUT.OUT powinna znaleźć się jedna liczba całkowita będąca resztą z dzielenia przez 1000 liczby różnych n-wierzchołkowych turniejów, dla których permutacja p jest automorfizmem.

Przykład

Dla pliku wejściowego AUT.IN

4
2
4
3
1

poprawną odpowiedzią jest plik wyjściowy AUT.OUT

4